3
$\begingroup$

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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ wow, I didn't expect the bound to be so tight for separability. thanks for the example. $\endgroup$
    – Alexey Kvashchuk
    Commented Feb 6, 2013 at 15:06
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Alexey Kvashchuk
    Commented Feb 6, 2013 at 15:25

You must log in to answer this question.

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