Hamiltonian path saturated graphs with small size

DOI10.1016/j.dam.2005.05.035zbMath1090.05035MaRDI QIDQ2492212

Gyula Y. Katona, Adam Paweł Wojda, Aneta Dudek

Publication date: 9 June 2006

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

Full work available at URL: https://doi.org/10.1016/j.dam.2005.05.035

zbMATH Keywords

extremal graph; path-cover

Mathematics Subject Classification ID

05C35: Extremal problems in graph theory

05C38: Paths and cycles

05C45: Eulerian and Hamiltonian graphs

Related Items

Hamilton-chain saturated hypergraphs, Hamiltonian Chains in Hypergraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Large Isaacs' graphs are maximally non-Hamilton-connected
• Smallest claw-free, 2-connected, nontraceable graphs and the construction of maximal nontraceable graphs
• Smallest maximally nonhamiltonian graphs
• Smallest maximally nonhamiltonian graphs. II
• A method in graph theory
• Not every 2-tough graph is Hamiltonian
• Tough graphs and Hamiltonian circuits.
• Saturated graphs with minimal number of edges
• Hamiltonian circuits and path coverings of vertices in graphs
• Infinite Families of Nontrivial Trivalent Graphs Which are Not Tait Colorable
• Hamiltonian shortage, path partitions of vertices, and matchings in a graph
• Graphs maximal with respect to absence of hamiltonian paths
• The $L(2,1)$-Labeling Problem on Graphs