7
$\begingroup$

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.

Improve this question
$\endgroup$
9
  • $\begingroup$ Does this partition have a name ? :-) $\endgroup$
    – Nathann Cohen
    Commented Sep 13, 2010 at 11:50
  • $\begingroup$ 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. $\endgroup$
    – Austin Mohr
    Commented Sep 13, 2010 at 13:06
  • $\begingroup$ 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. $\endgroup$
    – Roland Bacher
    Commented Sep 13, 2010 at 13:48
  • $\begingroup$ @Roland, in English "to ignore" means "to refuse to notice; to disregard" -- to convey "to not know" one can write "to be ignorant of." $\endgroup$
    – JBL
    Commented Sep 13, 2010 at 14:19
  • 2
    $\begingroup$ 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? $\endgroup$
    – Dave Pritchard
    Commented Oct 11, 2010 at 13:58

2 Answers 2

Reset to default
1
$\begingroup$

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)

Improve this answer
$\endgroup$
1
  • $\begingroup$ So I suspect that "usually" (in some sense) the reduced graph has only the trivial partition. This is true for cycles. $\endgroup$
    – Aaron Meyerowitz
    Commented Mar 1, 2011 at 5:13
0
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – Roland Bacher
    Commented Sep 13, 2010 at 13:46
  • $\begingroup$ "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. $\endgroup$
    – sleepless in beantown
    Commented Sep 14, 2010 at 0:43
  • $\begingroup$ 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$ $\endgroup$
    – sleepless in beantown
    Commented Sep 14, 2010 at 0:50
  • $\begingroup$ I shall have to explore this a little further and try to modify my answer, Roland. $\endgroup$
    – sleepless in beantown
    Commented Sep 14, 2010 at 0:51
  • 1
    $\begingroup$ 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. $\endgroup$
    – Bill Thurston
    Commented Dec 20, 2010 at 16:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .