Hamiltonian path saturated graphs with small size

DOI10.1016/J.DAM.2005.05.035MaRDI QIDQ2492212zbMATH OpenOpenAlexFDO

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

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 graphpath-cover

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45)

Review text

A graph \(G\) is Hamiltonian path saturated if \(G\) has no Hamiltonian path and any addition of a new edge in \(G\) creates a Hamiltonian path in \(G\). The authors establish a lower bound for the minimum size of a Hamiltonian path saturated graph for a given order. Small size path-cover saturated graphs are also considered.

Recommendations

• Hamilton saturated hypergraphs of essentially minimum size
• On the minimum size of Hamilton saturated hypergraphs
• Small cycles in Hamiltonian graphs
• scientific article; zbMATH DE number 4091550
• On minimum degree in Hamiltonian path graphs
• Hamilton paths in graphs whose vertices are graphs
• Upper bounds on the minimum size of Hamilton saturated hypergraphs
• scientific article; zbMATH DE number 1439406
• Graphs with few Hamiltonian cycles
• Hamiltonian paths and hamiltonian connectivity in graphs

Cites work

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

Cited in

(4)

• Hamiltonian Chains in Hypergraphs
• P_m-saturated bipartite graphs with minimum size
• On minimum degree in Hamiltonian path graphs
• Hamilton-chain saturated hypergraphs

This page was built for publication: Hamiltonian path saturated graphs with small size

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