z-logo
Premium
Hamiltonicity and Degrees of Adjacent Vertices in Claw‐Free Graphs
Author(s) -
Chen ZhiHong
Publication year - 2017
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22120
Subject(s) - combinatorics , mathematics , graph , discrete mathematics , hamiltonian (control theory) , mathematical optimization
For a graph H , letσ ¯ 2 ( H ) = min { d ( u ) + d ( v )|for every edge u v ∈ E ( H ) } . For r > 0 and k ∈ { 2 , 3 } , letQ 0 ( r , k )be a set of k ‐edge‐connected K 3 ‐free graphs of order at most r and without spanning closed trails. We show that for given p > 0 and ε, if H is a k ‐connected claw‐free graph of order n with δ ( H ) ≥ 3 andσ ¯ 2 ( H ) ≥ ( 2 n + ε ) / p , and if n is sufficiently large, then either H is Hamiltonian or the Ryjác̆ek's closure c l ( H ) = L ( G ) where G is an essentially k ‐edge‐connected K 3 ‐free graph that can be contracted to a graph inQ 0 ( 5 p − 10 , k ) . As applications, we prove: (i) For k = 2 , if δ ( H ) ≥ 3 and ifσ ¯ 2 ( H ) > 2 n − 6 3and n is sufficiently large, then H is Hamiltonian. (ii) For k = 3 , ifσ ¯ 2 ( H ) > 2 n + 10 10and n is sufficiently large, then H is Hamiltonian. These bounds are sharp. Furthermore, since the graphs inQ 0 ( 5 p − 10 , k )are fixed for given p and can be determined in a constant time, any improvement to (i) or (ii) by increasing the value of p and so enlarging the number of exceptions can be obtained computationally.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here