Hamiltonicity and Degrees of Adjacent Vertices in Claw‐Free Graphs |
| |
Authors: | Zhi‐Hong Chen |
| |
Institution: | DEPARTMENT OF COMPUTER SCIENCE AND SOFTWARE ENGINEERING, BUTLER UNIVERSITY, INDIANAPOLIS, IN |
| |
Abstract: | For a graph H , let for every edge . For and , let be a set of k‐edge‐connected K3‐free graphs of order at most r and without spanning closed trails. We show that for given and ε, if H is a k‐connected claw‐free graph of order n with and , and if n is sufficiently large, then either H is Hamiltonian or the Ryjác?ek's closure where G is an essentially k‐edge‐connected K3‐free graph that can be contracted to a graph in . As applications, we prove: - (i) For
, if and if and n is sufficiently large, then H is Hamiltonian. - (ii) For
, if and n is sufficiently large, then H is Hamiltonian. These bounds are sharp. Furthermore, since the graphs in 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. |
| |
Keywords: | degree of adjacent vertices dominating closed trail Hamiltonian cycle |
|
|