Cubic maximal nontraceable graphs

DOI10.1016/J.DISC.2005.11.039MaRDI QIDQ868358zbMATH OpenOpenAlexFDO

Authors Marietjie Frick, Joy Singleton

Publication date 2 March 2007

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

Hamiltonian cycleHamiltonian pathmaximal nonhamiltonian

Mathematics Subject Classification ID

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

Abstract: We determine a lower bound for the number of edges of a 2-connected maximal nontraceable graph, and present a construction of an infinite family of maximal nontraceable graphs that realize this bound.

Review text

The authors determine a lower bound for the number of edges of a 2-connected maximal nontraceable graph and present a construction of an infinite family of maximal nontraceable graphs that realizes this bound. The construction proposed by the authors yields maximal nontraceable graphs of girth 5, 6 and 7. The problem of the existence of maximal nontraceable graphs of girth bigger than 7 remains open.

Recommendations

• On cubic non-Cayley vertex-transitive graphs
• scientific article; zbMATH DE number 2076930
• On the cubicity of certain graphs
• Maximal nontraceable graphs with toughness less than one
• On non-planarity of cubic graphs
• scientific article; zbMATH DE number 26492
• Decompositions of cubic traceable graphs
• On measures of nonplanarity of cubic graphs
• The cubicity of hypercube graphs
• Cubicity of threshold graphs

Cites work

• Graphs maximal with respect to absence of hamiltonian paths
• scientific article; zbMATH DE number 3652373 (Why is no real title available?)
• scientific article; zbMATH DE number 1409195 (Why is no real title available?)
• On generating snarks
• Smallest claw-free, 2-connected, nontraceable graphs and the construction of maximal nontraceable graphs
• Smallest maximally nonhamiltonian graphs
• Smallest maximally nonhamiltonian graphs. II
• Variations on the Hamiltonian Theme
• Vertices missed by longest paths or circuits

Cited in

(5)

• Towards obtaining a 3-decomposition from a perfect matching
• A note on the smallest connected non-traceable cubic bipartite planar graph
• Lower bound for the size of maximal nontraceable graphs
• Degree sums of adjacent vertices for traceability of claw-free graphs
• Further results on maximal nontraceable graphs of smallest size

This page was built for publication: Cubic maximal nontraceable graphs

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