Efficient computation of a vertex-partition for graphs

A finite simple connected graph $\Gamma$ with vertices $V(\Gamma)$ has a partition of its vertices into (at most) two subsets defined as follows: Given a spanning tree $T\subset \Gamma$, chose a function $\varphi_T:V(\Gamma)\longrightarrow \lbrace \pm 1\rbrace$ such that $\varphi(s)\varphi(t)=-1$ if $s,t\in V(\Gamma)$ are adjacent vertices of $T$. The product $\psi=\prod_T\varphi_T$ over all spanning trees of $\Gamma$ is well defined up to a global sign and induces a partition $\psi^{-1}(1)\cup\psi^{-1}(-1)$ of $V(\Gamma)$.

Is there an efficient way for computing this partition for an arbitrary graph?

Remark: The best way I can think of for a general graph is to consider all partitions $A\cup B$ of $V(\Gamma)$ which induce a connected bipartite subgraph (obtained by removing all edges having either both endpoints in $A$ or in $B$) of odd complexity.

• Does this partition have a name ? :-) – Nathann Cohen Sep 13 '10 at 11:50
• Just a minor point: Your function appears to be defined on $V(\Gamma) \times V(\Gamma)$, as $\phi_T$ only has a meaningful output when given two vertices. – Austin Mohr Sep 13 '10 at 13:06
• Concerning the name of this bipartition, I ignore the answer. Concernings Austin Mohr's remark: Of course, the function is only used for defining an equivalence relation with at most two classes on the set of vertices. – Roland Bacher Sep 13 '10 at 13:48
• @Roland, in English "to ignore" means "to refuse to notice; to disregard" -- to convey "to not know" one can write "to be ignorant of." – JBL Sep 13 '10 at 14:19
• Maybe it is easier to reformulate in the following way: two vertices $u, v$ are in the same partition iff $\sum_T d_T(u, v)$ is even, where the inner expression is the distance in the tree. Is there a nice way to compute this distance sum mod 2? – Dave Pritchard Oct 11 '10 at 13:58

As you note, for a bipartite graph you get either the bipartition or the trivial partition (according as the number of spanning trees is even or odd). Any edge whose removal (keeping its endpoints) disconnects the graph must be in every spanning tree. So its two ends will be in the same or opposite parts of the partition according as the total number of spanning trees is even or odd. So we may delete all these edges since the number of spanning trees for the given graph will be the same as the number of maximal spanning forests of the reduced graph. The reduced graph has one or more connected components each without degree one vertices or bridges. Each of these components is either two connected or has one or more cutpoints separating it into maximal 2 connected components. If any of those 2 connected components has an even number of spanning trees then the reduced graph gets the trivial partition.

I think it might be more interesting to have each spanning tree vote if each pair of vertices are "the same" or "opposite" (so "neutral" is a possible outcome)

• So I suspect that "usually" (in some sense) the reduced graph has only the trivial partition. This is true for cycles. – Aaron Meyerowitz Mar 1 '11 at 5:13

This is effectively creating the bipartite coloring of a graph $G=(V,E)$, if it is bipartite. There can be no bipartite coloring if there are odd length cycles in the graph which you are considering.

You can check to see if a graph is bipartite in $O(|V|\cdot |E|)$, i.e. time proportional to the product of the number of edges and vertices.

If your graph is a single component connected finite graph, start by pick any vertex as a starting point and assign it the distance $0$ (or equivalently the label $(-1)$. Then iterate the following two steps alternately until every vertex is labeled, or until you end up attempting to assign two different labels to the same vertex (i.e. you find two different paths to the same vertex which are not the same length modulo $2$.

• follow every edge from your vertices labeled $0$ to get the next set of vertices and see if any of them are already labeled $0$, if there are then no such bipartition exists. If not, label them with the distance $1$ or alternately $(+1)$

• follow every edge from the vertices labeled $1$ to get the next set of vertices and see if any of them are already labeled $1$, if there are then no such bipartition exists. If not, label them $0$ and continue to iterate.

If you end up attempting to label the same vertex with both labels/colors, then the graph is not bipartite. Otherwise, you end up with every vertex labeled with the parity ($0$=even, $1$=odd) of their distance from the initial vertex chosen for this labeling.

• This partition is not necessarily creating the bipartite coloring if $\Gamma$ is bipartite: It is trivial for a bipartite connected graph with even complexity. It gives however the bipartition otherwise. Bipartite graphs are however not very interesting for this invariant: I am interested in arbitrary general graphs. – Roland Bacher Sep 13 '10 at 13:46
• "Doing a bipartite partitioning of one of the spanning trees of an arbitrary single-component connected general graph" appears to be what you are asking for. If there are odd cycles in your graph, different spanning trees will yield different partitions. Then, you would like to take all of the possible spanning trees and multiply them, so that any vertex which has an odd number of ($-1$) labels will still be labeled ($-1$). Example: $C_3$ has three spanning trees yielding the ordered label lists (-1,1,-1) (1,-1,-1) (-1,-1,1), whose product yields (1,1,1) which is not a partition. – sleepless in beantown Sep 14 '10 at 0:43
• continued comment @Roland Bacher, any vertex in an odd cycle in an arbitrary general graph will have one path which yields a (+1) labeling and one path which yields a (-1) labeling. Am I interpreting your question correctly now? In that case, I'm not sure that your partitioning will yield anything of interest for arbitrary general graphs. It should yield (1) if there are an even number of spanning trees in which the vertex has distance has odd parity. Each $\varphi_{T_i}$ is a bipartite coloring of spanning tree $T_i$, with two possible colorings. $k$ spanning trees -> $2^k$ $\Pi\varphi$ – sleepless in beantown Sep 14 '10 at 0:50
• I shall have to explore this a little further and try to modify my answer, Roland. – sleepless in beantown Sep 14 '10 at 0:51
• A triangle with an edge attached to one vertex is a simple example of a non-bipartite graph where Roland Bacher's partition is not trivial. The vertex with 3 edges is in one element of the partition, the other three vertices in the other. – Bill Thurston Dec 20 '10 at 16:49