scientific article; zbMATH DE number 19172

MaRDI QIDQ3976600zbMATH OpenFDO

Authors E. Schmeichel, D. Bauer

Publication date 26 June 1992

zbMATH Keywords

Hamiltonian

Mathematics Subject Classification ID

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

Review text

[For the entire collection see Zbl 0734.00014.] A graph \(G\) is 1-tough if for any separating set of vertices \(S\) of \(G\), the number of components of \(G-S\) does not exceed \(| S|\). The main result is that if \(G\) is a 1-tough graph on \(n\geq 3\) vertices with \(\delta(G)\geq(n+\kappa-2)/3\), then \(G\) is Hamiltonian. This corresponds to a result of \textit{R. Häggkvist} [J. Comb. Theory, Ser. B 30, 118-120 (1981; Zbl 0462.05046)] that any 2-connected graph on \(n\geq 3\) vertices with \(\delta(G)\geq(n+\kappa)/3\) is Hamiltonian.

Recommendations

• scientific article; zbMATH DE number 861334
• Hamiltonian cycles in 1-tough graphs
• A Remark on Hamiltonian Cycles

Cited in

(8)

• Edge-connectivity and edge-disjoint spanning trees
• On a theorem of {G}alvin and {N}agy
• Toughness in graphs -- a survey
• Hamilton-connectivity of interconnection networks modeled by a product of graphs
• scientific article; zbMATH DE number 1892910 (Why is no real title available?)
• scientific article; zbMATH DE number 837058 (Why is no real title available?)
• Graph invariants and large cycles: a survey
• A simple proof of a theorem of Jung

This page was built for publication:

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