Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Is the number of edges in the 3-connected graph with the minimum number of spanning trees always $\lceil {\frac{3}{2}}n\rceil$?

share|improve this question
1  
What are some examples of such 3c-min-span graphs? Presumably you know some classes that achieve the min... –  Joseph O'Rourke Oct 14 '10 at 19:40
    
It seems there are no classes which achieve the minimum always. An example of a class which achieve a low number of spanning trees are Prism Graphs, but they do not always have the minimum number of spanning trees. –  utdiscant Oct 14 '10 at 20:50
    
For what values of n do you know this to be true? –  j.c. Oct 15 '10 at 0:18
add comment

1 Answer 1

Are the minimally 3-connected graphs (edge removal pushes you into a 2-connected graph) the same as the class of 3-connected graphs with the minimal number of spanning trees? There is a nice classification of the minimal 3-connected graphs (or maximal not-3-connected graphs, I forget which direction he does it in) in Jonsson's book "Simplicial Complexes of Graphs".

I think there's also a classification of minimal 3-connected graphs inside a paper by David Fisher, Kathryn Fraughnaugh, and Larry Langley which could help ["3-connected graphs of minimal size".] At the very least, they note that all 3-connected graphs on n vertices have at least 3/2(n-2) edges, and produce graphs achieving this bound. All of your graphs with the minimal number of spanning trees must be one of these minimal 3-connected graphs (as if your hypothetical "minimal spanning tree" graph wasn't also a minimal 3-connected graph, removing edges to a minimal 3-connected graph would reduce the number of spanning trees.)

share|improve this answer
    
It is true that the 3-connected graph(s) with the minimum number of spanning trees must be found among the 3-connected graphs with the minimal number of edges, but this is not enough to draw a conclusion, since it is easy to find examples showing that minimal 3-connected graphs have more than ceil(3n/2) edges. For instance the Wheel Graph on 6 vertices is a minimal 3-connected graph, but has 10 edges. –  utdiscant Oct 15 '10 at 1:57
    
Also, I can't seem to find the paper ["3-connected graphs of minimal size".] which you are referring too, do you have a link? –  utdiscant Oct 15 '10 at 2:01
    
The actual title appears to be "P_3 - connected graphs of minimal size" in Ars Combinatorica. I found this by putting one of the author's names into my favorite search engine. This led me to the personal website of the author, which included a CV, which included a list of papers. (MathSciNet would have been even quicker.) –  JBL Oct 15 '10 at 2:31
    
Yeah, that's a good point. Since the complex of not 3-connected graphs is homotopic to a wedge of spheres of the same dimension, I was under the impression that all of the minimal 3-connected graphs were of the same size - not the case. The critical graphs left over after an appropriately chosen discrete Morse matching are though... Do you have these graphs classified for small n? –  Gwyn Whieldon Oct 15 '10 at 5:00
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.