Hamiltonian Cycle Properties in k-Extendable Non-bipartite Graphs with High Connectivity

• Published in: Graphs and combinatorics 2020-07, Vol.36 (4), p.1043-1058
• Main Authors: Gan, Zhiyong, Lou, Dingjun, Xu, Yanping
• Format: Article
• Language: English
• Subjects: Apexes; Combinatorics; Engineering Design; Graph matching; Graph theory; Graphs; Mathematics; Mathematics and Statistics; Original Paper; Traveling salesman problem
• ISSN: 0911-0119; 1435-5914
• DOI: 10.1007/s00373-020-02164-x

Let G be a graph, ν the order of G and k a positive integer such that k ≤ ( ν - 2 ) / 2 . Then G is said to be k -extendable if it has a matching of size k and every matching of size k extends to a perfect matching of G . A graph G is Hamiltonian if it contains a Hamiltonian cycle. A graph G is Hamiltonian-connected if, for any two of its vertices, it contains a spanning path joining the two vertices. In this paper, we discuss k -extendable nonbipartite graphs with κ ( G ) ≥ 2 k + r where k ≥ 1 and r ≥ 0 . It is shown that if ν ≤ 6 k + 2 r , then G is Hamiltonian; and if ν > 6 k + 2 r , then G has a longest cycle C such that | V ( C ) | ≥ 6 k + 2 r ; and if ν < 6 k + 2 r , then G is Hamiltonian-connected; and if ν ≥ 6 k + 2 r , then for each pair of vertices z 1 and z 2 of G , there is a path P of G joining z 1 and z 2 such that | V ( P ) | ≥ 6 k + 2 r - 2 . All the bounds are sharp and all results can be extended to 2 k -factor-critical graphs.