2023/11/01 by Li Xia, Weihua Yang, Li, Xia +5
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2311.05505
openalex publication_date 2023/11/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Kronk introduced the l-path hamiltonianicity of graphs in 1969. A graph is l-path Hamiltonian if every path of length not exceeding l is contained in a Hamiltonian cycle. We have shown that if P=uvz is a 2-path of a 2-connected, k-regular graph on at most 2k vertices and G - V(P) is connected, then there must exist a Hamiltonian cycle in G that contains the 2-path P. In this paper, we characterize a class of graphs that illustrate the sharpness of the bound 2k. Additionally, we show that by excluding the class of graphs, both 2-connected, k-regular graphs on at most 2k + 1 vertices and 3-connected, k-regular graphs on at most 3k-6 vertices satisfy that there is a Hamiltonian cycle containing the 2-path P if G∖ V(P) is connected.