Critically $n$-connected graphs
HTML articles powered by AMS MathViewer
- by Gary Chartrand, Agnis Kaugars and Don R. Lick PDF
- Proc. Amer. Math. Soc. 32 (1972), 63-68 Request permission
Abstract:
The following result is proved. Every n-connected graph contains either a vertex whose removal results in a graph which is also n-connected or a vertex of degree less than $(3n - 1)/2$.References
- G. Chartrand and F. Harary, Graphs with prescribed connectivities, Theory of Graphs (Proc. Colloq., Tihany, 1966) Academic Press, New York, 1968, pp. 61–63. MR 0236048
- G. A. Dirac, Minimally $2$-connected graphs, J. Reine Angew. Math. 228 (1967), 204–216. MR 216975, DOI 10.1515/crll.1967.228.204
- Frank Harary, Graph theory, Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London 1969. MR 0256911
- R. Halin, A theorem on $n$-connected graphs, J. Combinatorial Theory 7 (1969), 150–154. MR 248042 A. Kaugars, A theorem on the removal of vertices from blocks, Senior Thesis, Kalamazoo College, Kalamazoo, Mich. 1968. D. R. Lick, Connectivity preserving subgraphs, Math. Report #1, Western Michigan University, Kalamazoo, Mich., 1968.
- Michael D. Plummer, On minimal blocks, Trans. Amer. Math. Soc. 134 (1968), 85–94. MR 228369, DOI 10.1090/S0002-9947-1968-0228369-8
- Hassler Whitney, Congruent Graphs and the Connectivity of Graphs, Amer. J. Math. 54 (1932), no. 1, 150–168. MR 1506881, DOI 10.2307/2371086
Additional Information
- © Copyright 1972 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 32 (1972), 63-68
- MSC: Primary 05C99
- DOI: https://doi.org/10.1090/S0002-9939-1972-0290999-1
- MathSciNet review: 0290999