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

Hello,

Does anyone know if there is a result that relates a quantity such as an average degree to the fact the a (simple and connected graph) has no cut vertices?

e.g. if a graph has a Hamiltoninan cycle then it has not cut vertex. By Ore's theorem, if deg(v) >= n/2 for each vertex v (n is the number of vertices of a graph), then the graph is Hamiltoninan. Hence deg(v) >= n/2 implies no cut vertices (non-separable).

I am looking for a result similar to Ore's theorem, but w.r.t. non-separability e.g. something like if the deg(v) >= f(n) for each v (or some statement about the average degree), then the number of cut vertices is zero.

Thank you.

share|improve this question
add comment

2 Answers

up vote 6 down vote accepted

I do not think you can do anything better than $\frac{n}{2}$. Consider the following construction: Take two complete graphs of equal size $\frac{n-1}{2}$. Add one vertex $v$ and connect this vertex to all vertices of the two complete graphs. Each vertex has degree at least $\frac{n-1}{2}$ and this graph has a cut vertex.

share|improve this answer
    
wow, I didn't expect the bound to be so tight for separability. thanks for the example. –  Alexey Feb 6 '13 at 15:06
add comment

If you look for special graph classes, similar statements are possible, e.g., if each vertex of a self-complementary graph has degree at least two then the graph has no cut-vertex.

share|improve this answer
    
thank you. I am looking at a non-special case. Just a simple and connected graph. Given the example above I wonder if there are any other features (like Hamiltonian property) that imply non-separability. May be something in terms of, say, min/max degree (δ(G),Δ(G)). There are some results on the upper bound of the number of cut vertices in terms of δ(G)/Δ(G) but none are directly useful as I am interested in the case of zero cut vertices. –  Alexey Feb 6 '13 at 15:25
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.