Back to Search
Start Over
Group connectivity of graphs satisfying the Chvátal-condition.
- Source :
-
Discrete Applied Mathematics . Dec2023, Vol. 341, p212-217. 6p. - Publication Year :
- 2023
-
Abstract
- Let G be a (simple) graph on n ≥ 3 vertices and (d 1 , ... , d n) be the degree sequence of G with d 1 ≤ ⋯ ≤ d n . The classical Chvátal's theorem states that if d m ≥ m + 1 or d n − m ≥ n − m for each m with 1 ≤ m < n 2 (called the Chvátal-condition), then G is hamiltonian. Similarly, let G be a (simple) balanced bipartite graph on n ≥ 4 vertices and (d 1 , ... , d n) be the degree sequence of G with d 1 ≤ ⋯ ≤ d n . The classical Chvátal's theorem states that if d m ≥ m + 1 or d n 2 ≥ n 2 − m + 1 for each m with 1 ≤ m ≤ n 4 (called the Chvátal-condition), then G is hamiltonian. In this paper, for an abelian group A of order at least 4, we show that if a graph G satisfies the Chvátal-condition, then G is A -connected if and only if G ≠ C 4 , where C ℓ is a cycle of length ℓ. Moreover, for an abelian group A of order at least 5, we also show that if a balanced bipartite graph G satisfies the Chvátal-condition, then G is A -connected if and only if G ≠ C 6 . [ABSTRACT FROM AUTHOR]
- Subjects :
- *GRAPH connectivity
*BIPARTITE graphs
*ABELIAN groups
Subjects
Details
- Language :
- English
- ISSN :
- 0166218X
- Volume :
- 341
- Database :
- Academic Search Index
- Journal :
- Discrete Applied Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 173233551
- Full Text :
- https://doi.org/10.1016/j.dam.2023.08.008