Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

Critically $ n$-connected graphs


Authors: Gary Chartrand, Agnis Kaugars and Don R. Lick
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
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] 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 38 #4346. MR 0236048 (38:4346)
  • [2] G. A. Dirac, Minimally 2-connected graphs, J. Reine Angew. Math. 228 (1967), 204-216. MR 36 #70. MR 0216975 (36:70)
  • [3] F. Harary, Graph theory, Addison-Wesley, Reading, Mass., 1969. MR 41 #1566. MR 0256911 (41:1566)
  • [4] R. Halin, A theorem on n-connected graphs, J. Combinatorial Theory 7 (1969), 150-154. MR 40 #1297. MR 0248042 (40:1297)
  • [5] A. Kaugars, A theorem on the removal of vertices from blocks, Senior Thesis, Kalamazoo College, Kalamazoo, Mich. 1968.
  • [6] D. R. Lick, Connectivity preserving subgraphs, Math. Report #1, Western Michigan University, Kalamazoo, Mich., 1968.
  • [7] M. D. Plummer, On minimal blocks, Trans. Amer. Math. Soc. 134 (1968), 85-94. MR 37 #3950. MR 0228369 (37:3950)
  • [8] H. Whitney, Congruent graphs and the connectivity of graphs, Amer. J. Math. 54 (1932), 150-168. MR 1506881

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 05C99

Retrieve articles in all journals with MSC: 05C99


Additional Information

DOI: https://doi.org/10.1090/S0002-9939-1972-0290999-1
Keywords: Graph, connectivity, critically n-connected
Article copyright: © Copyright 1972 American Mathematical Society

American Mathematical Society