Hamiltonian cycles in 1-tough graphs

DOI10.1007/BF01858471MaRDI QIDQ2563428zbMATH OpenFDO

Authors Bing Wei

Publication date 20 July 1997

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01858471

zbMATH Keywords

1-tough graphHamiltonian cycle

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45)

Review text

For a graph \(G\) let \(\sigma_3= \min \{d(u_1) +d(u_2) +d(u_3)\}\) and \(\overline \sigma_3= \min \{d(u_1)+ d(u_2)+ d(u_3)- |N(u_1) \cap N(u_2) \cap N(u_3) |\}\) where \(\{u_1,u_2,u_3\}\) ranges over all 3-element independent sets of \(G\). It is proved that if \(G\) is a 1-tough graph of order \(n\) such that \(\sigma_3\geq n\) and \(\overline\sigma_3\geq n-4\) then \(G\) is hamiltonian. This generalizes results of \textit{B. Fassbender} [Ars Comb. 33, 300-304 (1992; Zbl 0764.05050)], \textit{E. Flandrin} et al. [Discrete Math. 90, No. 1, 41-52 (1991; Zbl 0746.05038)] and \textit{H. A. Jung} [Ann. Discrete Math. 3, 129-144 (1978; Zbl 0399.05039)].

Recommendations

• A sufficient condition for Hamiltonian cycles in tough graphs
• Long cycles in 1-tough graphs with large degree sums
• Hamilton cycles in 1-tough triangle-free graphs
• scientific article; zbMATH DE number 822747

Cites work

• A generalization of a result of Bauer and Schmeichel
• Hamiltonism, degree sum and neighborhood intersections
• scientific article; zbMATH DE number 4208106 (Why is no real title available?)
• Long cycles in graphs with large degree sums
• On Maximal Circuits in Finite Graphs
• The binding number of a graph and its Anderson number

Cited in

(18)

• A sufficient condition for Hamiltonian cycles in tough graphs
• Hamiltonian cycles in T-graphs
• Hamilton cycles in 1-tough triangle-free graphs
• Tough graphs and Hamiltonian circuits. (Reprint)
• Tough graphs and Hamiltonian circuits.
• Hamiltonian cycles in 7-tough \((P_3 \cup 2P_1)\)-free graphs
• scientific article; zbMATH DE number 19172 (Why is no real title available?)
• scientific article; zbMATH DE number 68362 (Why is no real title available?)
• A Remark on Hamiltonian Cycles
• A sharp lower bound for the circumference of 1‐tough graphs with large degree sums
• scientific article; zbMATH DE number 861334 (Why is no real title available?)
• More relations between -labeling and Hamiltonian paths with emphasis on line graph of bipartite multigraphs
• On hamiltonicity of 1-tough triangle-free graphs
• On the pancyclicity of 1-tough graphs
• Hamiltonian cycles in 2‐tough 2K2 $2{K}_{2}$‐free graphs
• Hamiltonicity of 1-tough (P₂ KP₁)-free graphs
• Long cycles in 1-tough graphs with large degree sums
• Every 2k-connected (P₂ kP₁)-free graph with toughness greater than one is Hamiltonian-connected

This page was built for publication: Hamiltonian cycles in 1-tough graphs

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