Back to Search
Start Over
On [formula omitted]-Hamilton-connected graphs.
- Source :
-
Discrete Applied Mathematics . Jan2024, Vol. 343, p288-299. 12p. - Publication Year :
- 2024
-
Abstract
- A graph G is called (k 1 , k 2) -Hamilton-connected, if for any two vertex disjoint subsets X = { x 1 , x 2 , ... , x k 1 } and U = { u 1 , u 2 , ... , u k 2 } , G contains a spanning family F of k 1 k 2 internally vertex disjoint paths such that for 1 ≤ i ≤ k 1 and 1 ≤ j ≤ k 2 , F contains an x i u j path. Let σ 2 (G) be the minimum value of deg (u) + deg (v) over all pairs { u , v } of non-adjacent vertices in G. In this paper, we prove that an n -vertex graph G is (2 , k) -Hamilton-connected if G is (5 k − 4) -connected with σ 2 (G) ≥ n + k − 2 where k ≥ 2. We also prove that if σ 2 (G) ≥ n + k 1 k 2 − 2 with k 1 , k 2 ≥ 2 , then G is (k 1 , k 2) -Hamilton-connected. Moreover, these requirements of σ 2 are tight. • This paper is motivated by k -fan connected graphs, we define (k 1 , k 2) -Hamilton-connected graphs. • This paper gives a sufficient condition for a graph to be (2 , k) -Hamilton-connected. • The results provide tight, sufficient, σ 2 (G) -conditions. • We extend the properties of Hamilton-connectedness and being k -linked. [ABSTRACT FROM AUTHOR]
- Subjects :
- *HAMILTONIAN graph theory
*MOTIVATION (Psychology)
*GRAPH connectivity
*FAMILIES
Subjects
Details
- Language :
- English
- ISSN :
- 0166218X
- Volume :
- 343
- Database :
- Academic Search Index
- Journal :
- Discrete Applied Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 174036581
- Full Text :
- https://doi.org/10.1016/j.dam.2023.11.014