Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-27T09:21:06.477Z Has data issue: false hasContentIssue false
  • English
  • Français

On Vertices of Degree n in Minimally n-Edge-Connected Graphs

Published online by Cambridge University Press:  12 September 2008

W. Mader
W. Mader
Affiliation:
Institut fur Mathematik, Universität Hannover, Welfengarten 1, D-30167 Hannover
Get access Rights & Permissions [Opens in a new window]

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
Combinatorics, Probability and Computing , Volume 4 , Issue 1 , March 1995 , pp. 81 - 95
Copyright
Copyright © Cambridge University Press 1995

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Bollobás, B., Goldsmith, D. L. and Woodall, D. R. (1981) Indestructive deletions of edges from graphs. J. Combinatorial Theory (B) 30 263–275.CrossRefGoogle Scholar
[2]Mao-Cheng, Cai (1992) A remark on the number of vertices of degree k in a minimally k-edge-connected graph. Discrete Math. 104 221–226.Google Scholar
[3]Mao-Cheng, Cai (1993) The number of vertices of degree k in a minimally k-edge-connected graph. J. of Combinatorial Theory (B) 58 225–239.Google Scholar
[4]Lick, D. R. (1972) Minimally n-line-connected graphs. J. Reine Angew. Math. 252 178–182.Google Scholar
[5]Mader, W. (1971) Minimale n-fach kantenzusammenhängende Graphen. Math. Ann. 191 21–28.CrossRefGoogle Scholar
[6]Mader, W. (1974) Kantendisjunkte Wege in Graphen. Monatshefte für Mathematik 78 395–404.CrossRefGoogle Scholar
[7]Mader, W. (1978) A reduction method for edge-connectivity in graphs. Annals of Discrete Mathematics 3 145–164.CrossRefGoogle Scholar
[8]Mader, W. (1979) Zur Struktur minimal n-fach zusammenhängende Graphen. Abh. Math. Sem. Universität Hamburg 49 49–69.CrossRefGoogle Scholar
[9] Zhu Biwen (1983) Critically 2-edge-connected graphs. Acta Math. Appl. Sinica 6 292–301.Google Scholar