A note on $k$-critically $n$-connected graphs
HTML articles powered by AMS MathViewer
- by R. C. Entringer and Peter J. Slater PDF
- Proc. Amer. Math. Soc. 66 (1977), 372-375 Request permission
Abstract:
A graph G is said to be $({n^\ast },k)$-connected if it has connectivity n and every set of k vertices is contained in an n-cutset. It is shown that an $({n^\ast },k)$-connected graph G contains an n-cutset C such that G — C has a component with at most $n/(k + 1)$ vertices, thereby generalizing a result of Chartrand, Kaugars and Lick. It is conjectured, however, that $n/(k + 1)$ can be replaced with $n/2k$ and this is shown to be best possible.References
- Mehdi Behzad and Gary Chartrand, Introduction to the theory of graphs, Allyn and Bacon, Inc., Boston, Mass., 1971. MR 0432461
- Gary Chartrand, Agnis Kaugars, and Don R. Lick, Critically $n$-connected graphs, Proc. Amer. Math. Soc. 32 (1972), 63–68. MR 290999, DOI 10.1090/S0002-9939-1972-0290999-1
- R. C. Entringer and P. J. Slater, A theorem on critically $3$-connected graphs, Nanta Math. 11 (1978), no. 2, 141–145. MR 532972 Stephen Maurer and Peter J. Slater, On n-connected and k-critical graphs, Discrete Math. (to appear).
- Ladislav Nebeský, On induced subgraphs of a block, J. Graph Theory 1 (1977), no. 1, 69–74. MR 505873, DOI 10.1002/jgt.3190010113
Additional Information
- © Copyright 1977 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 66 (1977), 372-375
- MSC: Primary 05C99
- DOI: https://doi.org/10.1090/S0002-9939-1977-0476580-4
- MathSciNet review: 0476580