On Hamiltonian cycle extension in cubic Hamiltonian graphs

摘要

A Hamiltonian graph G is said to be l-path-Hamiltonian, where l is a positive integer less than or equal to the order of G, if every path of order £ in G is a subpath of some Hamiltonian cycle in G. The Hamiltonian cycle extension number of G is the maximum positive integer L for which G is l-path-Hamiltonian for every integer t with 1 ≤ l ≤ L. Hamiltonian cycle extension numbers are determined for several well-known cubic Hamiltonian graphs. It is shown that if G is a cubic Hamiltonian graph with girth g, where 3 ≤ g ≤ 7, then G is l-path-Hamiltonian only if 1 ≤ l ≤ g.