Article contents
On Vertices of Degree n in Minimally n-Edge-Connected Graphs
Published online by Cambridge University Press: 12 September 2008
Abstract
Let G be a minimally n-edge-connected finite simple graph with vertex number |G| ≥ 2n + 2 + [3/n] and let n ≥ 3 be odd. It is proved that the number of vertices of degree n in G is at least ((n − 1 − ∈n)/(2n + 1))|G| + 2 + 2∈n, where ∈n = (3n + 3)/(2n2 − 3n − 3), and that for every n ≡ 3 (mod 4) this lower bound is attained by infinitely many minimally n-edge-connected finite simple graphs.
- Type
- Research Article
- Information
- Copyright
- Copyright © Cambridge University Press 1995
References
- 3
- Cited by