Revisiting the Hamiltonian Theme in the Square of a Block: The Case of\n DT-Graphs

2017/06/14 by Gek L. Chia, Chia, Gek L., Jan Ekstein +3
Computer Science · Engineering · Mathematics · #05C38 #05C45 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1706.04414

openalex publication_date 2017/06/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The square of a graph G, denoted G², is the graph obtained from G by joining\nby an edge any two nonadjacent vertices which have a common neighbor. A graph G\nis said to have the F_k property if for any set of k distinct vertices x₁,\nx₂, ..., x_k in G, there is a hamiltonian path from x₁ to x₂ in G²\ncontaining k-2 distinct edges of G of the form x_iz_i, i = 3, ..., k. It was\nproved many years ago that every 2-connected graph has the F₃ property. In the\nfirst part of this work, we extend this result by proving that every\n2-connected DT-graph has the F₄ property (Theorem 2) and will show in the\nsecond part that this generalization holds for arbitrary 2-connected graphs,\nand that there exist 2-connected graphs which do not have the F_k property for\nany natural number k >= 5. Altogether, this answers a problem raised before in\nthe affirmative.\n

Related

• Revisiting the Hamiltonian Theme in the Square of a Block: The General\n Case
• A Best Possible Result for the Square of a 2-Block to be Hamiltonian
• Characterizing forbidden pairs for hamiltonian squares
• On a conjecture of Faudree and Schelp
• On the regular 2-connected 2-path Hamiltonian graphs