Skip to main content
revised
Source Link
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

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). For now define the trunk to be the largest induced subgraph with all vertices having degree greater then 1Any edge whose removal (alternately, repeatedly delete any vertices of degree 1 until there are nonekeeping its endpoints). Then the rest of disconnects the graph is a collection of trees rooted at verticesmust be in the trunkevery spanning tree. The partition restricted to each trees is eitherSo its two ends will be in the trivial onesame or the bipartitionopposite parts of that treethe partition according as the trunk has antotal number of spanning trees is even or odd. So we may delete all these edges since the number of spanning trees. I'd guess that trunk "usually" (in some sense) gets for the trivial partitiongiven graph will be the same as the number of maximal spanning forests of the reduced graph. This is true for any cycle The reduced graph has one or more connected components each without degree one vertices or bridges. The trunkEach of these components is either 2two connected or has 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 rest of the trunk gets the trivial partition. Any component that gets the trivial partition when considered as a graph on its own will get the trivial partition when looking at all spanning trees of the entire reduced graph. I think that if there is an automorphism of the trunk fixing at least one point and exchanging two adjacent ones then again the trunk 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)

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). For now define the trunk to be the largest induced subgraph with all vertices having degree greater then 1 (alternately, repeatedly delete any vertices of degree 1 until there are none). Then the rest of the graph is a collection of trees rooted at vertices in the trunk. The partition restricted to each trees is either the trivial one or the bipartition of that tree according as the trunk has an even or odd number of spanning trees. I'd guess that trunk "usually" (in some sense) gets the trivial partition. This is true for any cycle. The trunk is either 2 connected or has one or more cutpoints separating it into maximal 2 connected components. If any of those components has an even number of spanning trees then the rest of the trunk gets the trivial partition. Any component that gets the trivial partition when considered as a graph on its own will get the trivial partition when looking at all spanning trees of the entire graph. I think that if there is an automorphism of the trunk fixing at least one point and exchanging two adjacent ones then again the trunk 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)

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)

Source Link
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

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). For now define the trunk to be the largest induced subgraph with all vertices having degree greater then 1 (alternately, repeatedly delete any vertices of degree 1 until there are none). Then the rest of the graph is a collection of trees rooted at vertices in the trunk. The partition restricted to each trees is either the trivial one or the bipartition of that tree according as the trunk has an even or odd number of spanning trees. I'd guess that trunk "usually" (in some sense) gets the trivial partition. This is true for any cycle. The trunk is either 2 connected or has one or more cutpoints separating it into maximal 2 connected components. If any of those components has an even number of spanning trees then the rest of the trunk gets the trivial partition. Any component that gets the trivial partition when considered as a graph on its own will get the trivial partition when looking at all spanning trees of the entire graph. I think that if there is an automorphism of the trunk fixing at least one point and exchanging two adjacent ones then again the trunk 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)