The Hamiltonian problem and t-path traceable graphs

DOI10.2140/INVOLVE.2017.10.801MaRDI QIDQ2357671zbMATH OpenOpenAlexFDO

Authors Kashif Bari, Michael E. O'Sullivan

Publication date 14 June 2017

Published in Involve (Search for Journal in Brave)

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

zbMATH Keywords

\(t\)-path traceablegraph theoryHamiltonianmaximal non-Hamiltonian

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45)

Abstract: The problem of characterizing maximal non-Hamiltonian graphs may be naturally extended to characterizing graphs that are maximal with respect to non-traceability and beyond that to $t$-path traceability. We show how traceability behaves with respect to disjoint union of graphs and the join with a complete graph. Our main result is a decomposition theorem that reduces the problem of characterizing maximal $t$-path traceable graphs to characterizing those that have no universal vertex. We generalize a construction of maximal non-traceable graphs by Zelinka to $t$-path traceable graphs.

Recommendations

• Hamiltonicity of k-traceable graphs
• Lower bound for the size of maximal nontraceable graphs
• Maximal nontraceable graphs with toughness less than one
• scientific article; zbMATH DE number 2077642
• Extremal traceable graphs with non-traceable edges

Cites work

• A catalogue of small maximal nonhamiltonian graphs
• Arc coverings of graphs
• Covering the vertices of a graph by vertex-disjoint paths
• Graphs maximal with respect to absence of hamiltonian paths
• Maximum nonhamiltonian tough graphs
• Tough graphs and Hamiltonian circuits.

Cited in

(12)

• Maximal nontraceable graphs with toughness less than one
• A note on the Hamiltonian circuit problem on directed path graphs
• Time-free solution to Hamilton path problems using P systems with \(d\)-division
• Scenic graphs. I: Traceable graphs
• The Hamiltonian Augmentation Problem and Its Applications to Graph Drawing
• scientific article; zbMATH DE number 1210362 (Why is no real title available?)
• scientific article; zbMATH DE number 1334643 (Why is no real title available?)
• scientific article; zbMATH DE number 1735783 (Why is no real title available?)
• scientific article; zbMATH DE number 2077642 (Why is no real title available?)
• scientific article; zbMATH DE number 6850346 (Why is no real title available?)
• The Hamiltonian Cycle and Travelling Salesman Problems in cP Systems
• Covering 3‐uniform hypergraphs by vertex‐disjoint tight paths

This page was built for publication: The Hamiltonian problem and \(t\)-path traceable graphs

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