Structural and computational results on platypus graphs

DOI10.1016/J.AMC.2020.125491MaRDI QIDQ2656702zbMATH OpenOpenAlexFDO

Authors Jan Goedgebeur, Addie Neyt, Carol T. Zamfirescu

Publication date 16 March 2021

Published in Applied Mathematics and Computation (Search for Journal in Brave)

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

zbMATH Keywords

computationscubic graphgirthhypohamiltonianhypotraceablemaximally non-Hamiltonian graphnon-Hamiltoniantraceable

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: A platypus graph is a non-hamiltonian graph for which every vertex-deleted subgraph is traceable. They are closely related to families of graphs satisfying interesting conditions regarding longest paths and longest cycles, for instance hypohamiltonian, leaf-stable, and maximally non-hamiltonian graphs. In this paper, we first investigate cubic platypus graphs, covering all orders for which such graphs exist: in the general and polyhedral case as well as for snarks. We then present (not necessarily cubic) platypus graphs of girth up to 16---whereas no hypohamiltonian graphs of girth greater than 7 are known---and study their maximum degree, generalising two theorems of Chartrand, Gould, and Kapoor. Using computational methods, we determine the complete list of all non-isomorphic platypus graphs for various orders and girths. Finally, we address two questions raised by the third author in [J. Graph Theory extbf{86} (2017) 223--243].

Recommendations

• On non-Hamiltonian graphs for which every vertex-deleted subgraph is traceable
• On cubic planar hypohamiltonian and hypotraceable graphs
• Hypohamiltonian planar cubic graphs with girth 5
• On almost hypohamiltonian graphs
• Planar Hypohamiltonian Graphs on 40 Vertices

Cites work

• A theorem on tait colorings with an application to the generalized Petersen graphs
• Component connectivity of generalized Petersen graphs
• Construction of planar triangulations with minimum degree 5
• Fast generation of planar graphs
• Generation and properties of snarks
• House of Graphs: a database of interesting graphs
• scientific article; zbMATH DE number 3754737 (Why is no real title available?)
• scientific article; zbMATH DE number 227006 (Why is no real title available?)
• I-graphs and the corresponding configurations
• Improved bounds for hypo-Hamiltonian graphs
• Infinitely many hypohamiltonian cubic graphs of girth 7
• On hypohamiltonian snarks and a theorem of Fiorini
• On non-Hamiltonian graphs for which every vertex-deleted subgraph is traceable
• Practical graph isomorphism. II.
• Self-dual configurations and regular graphs
• Smallest maximally nonhamiltonian graphs
• The classification of Hamiltonian generalized Petersen graphs
• The smallest non-Hamiltonian 3-connected cubic planar graphs have 38 vertices
• Variations on the Hamiltonian Theme

Cited in

(7)

• Vertex degrees and 2-cuts in graphs with many Hamiltonian vertex-deleted subgraphs
• Graph models for PLA folding problems
• On non-Hamiltonian graphs for which every vertex-deleted subgraph is traceable
• Generation and new infinite families of \(K_2\)-hypohamiltonian graphs
• On platypus graphs and the Steiner-Deogun property
• On non-Hamiltonian polyhedra without cubic vertices and their vertex-deleted subgraphs
• Network fault costs based on minimum leaf spanning trees

Describes a project that uses

Uses Software

• Traces
• nauty
• plantri
• GenHypohamiltonian

This page was built for publication: Structural and computational results on platypus graphs

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