For some fixed $n\in\mathbb N$ let $G$ be a graph on the vertex set $\{1,\dots,n\}$ with a total number of $k$ edges $e_1,\dots, e_k$. For any vertex colouring $c(i)$ of the graph, $\delta_e$ is defined to be $1$ if the vertices that are connected by the edge $e$ have the same colour, and $0$ otherwise. A colouring is given a weight of $1$ if the number of edges connecting two vertices of the same colour is even and $-1$ otherwise. If I have a total of, say, 3 colours available I am interested in the weighted sum over all possible colourings

$$f(G):=3^{-n}\sum_{c(1)=1}^3\dots\sum_{c(n)=1}^3 (-1)^{k+\delta_{e_1}+\dots+\delta_{e_k}}$$

measuring the mean parity of the number of edges connecting vertices of the same colour.

It is clear that for a graph without edges $f(G)=1$, and that if all edges are disjoint $f(G)=(-1/3)^{k}$. For the complete graph the result seems to be $$f(G)=\frac{3^{1-n}}{2}(1+(-3)^{n-1}).$$

Question: How $f(G)$ be described in terms of properties of the graph?

Edit: See below for a table of $f(G)$ for all graphs on 3 and 4 vertices. f(G) for all graphs on 3 vertices f(G) for all graphs on 4 vertices

It seems to me that for all trees the result is $(-1/3)^{k}$. It also seems more generally, that adding a new edges to a so far not connected vertex yields a division by $-3$.



You must log in to answer this question.

Browse other questions tagged .