2022/02/25 by Xia Li, Weihua Yang, Li, Xia +1
Computer Science · Engineering · Neuroscience · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Nuclear Receptors and Signaling #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2203.04345
openalex publication_date 2022/02/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A graph G is l-path Hamiltonian if every path of length not exceeding l is contained in a Hamiltonian cycle. It is well known that a 2-connected, k-regular graph G on at most 3k-1 vertices is edge-Hamiltonian if for every edge uv of G, \u,v\ is not a cut-set. Thus G is 1-path Hamiltonian if G∖ \u,v\ is connected for every edge uv of G. Let P=uvz be a 2-path of a 2-connected, k-regular graph G on at most 2k vertices. In this paper, we show that there is a Hamiltonian cycle containing the 2-path P if G∖ V(P) is connected. Therefore, the work implies a condition for a 2-connected, k-regular graph to be 2-path Hamiltonian. An example shows that the 2k is almost sharp, i.e., the number is at most 2k+1.