Regular homogeneously traceable nonhamiltonian graphs

DOI10.1016/J.DAM.2021.12.022MaRDI QIDQ2074356zbMATH OpenOpenAlexFDO

Authors Yanan Hu, Xingzhi Zhan

Publication date 9 February 2022

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2107.11561

zbMATH Keywords

circumferencehomogeneously traceableregular graph

Mathematics Subject Classification ID

Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45)

Abstract: A graph is called homogeneously traceable if every vertex is an endpoint of a Hamilton path. In 1979 Chartrand, Gould and Kapoor proved that for every integer $nge9,$ there exists a homogeneously traceable nonhamiltonian graph of order $n.$ The graphs they constructed are irregular. Thus it is natural to consider the existence problem of regular homogeneously traceable nonhamiltonian graphs. We prove two results: (1) For every even integer $nge10,$ there exists a cubic homogeneously traceable nonhamiltonian graph of order $n;$ (2) for every integer $pge18,$ there exists a $4$-regular homogeneously traceable graph of order $p$ and circumference $p-4.$ Unsolved problems are posed.

Recommendations

• Pairs of forbidden induced subgraphs for homogeneously traceable graphs
• scientific article; zbMATH DE number 554191
• On a problem of Hendry
• Hamiltonicity of k-traceable graphs
• scientific article; zbMATH DE number 3959473

Cites work

• Degrees in Homogeneously Traceable Graphs
• scientific article; zbMATH DE number 3937205 (Why is no real title available?)
• scientific article; zbMATH DE number 3754737 (Why is no real title available?)

Cited in

(7)

• scientific article; zbMATH DE number 3845629 (Why is no real title available?)
• Extremal traceable graphs with non-traceable edges
• scientific article; zbMATH DE number 3959473 (Why is no real title available?)
• scientific article; zbMATH DE number 125496 (Why is no real title available?)
• Hamiltonicity of k-traceable graphs
• Construction of regular homogeneously traceable nonhamiltonian graphs
• Graphs with many Hamiltonian paths

This page was built for publication: Regular homogeneously traceable nonhamiltonian graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2074356)