Back to Search
Start Over
Graphs with Many Independent Vertex Cuts.
- Source :
-
Graphs & Combinatorics . Aug2024, Vol. 40 Issue 4, p1-5. 5p. - Publication Year :
- 2024
-
Abstract
- Cycles are the only 2-connected graphs in which any two nonadjacent vertices form a vertex cut. We generalize this fact by proving that for every integer k ≥ 3 there exists a unique graph G satisfying the following three conditions: (1) G is k-connected; (2) the independence number of G is greater than k; (3) any independent set of cardinality k is a vertex cut of G. However, the edge version of this result does not hold. We also consider the problem when replacing independent sets by the periphery. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 09110119
- Volume :
- 40
- Issue :
- 4
- Database :
- Academic Search Index
- Journal :
- Graphs & Combinatorics
- Publication Type :
- Academic Journal
- Accession number :
- 178055856
- Full Text :
- https://doi.org/10.1007/s00373-024-02811-7