𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Maximum nonhamiltonian tough graphs

✍ Scribed by A. Marczyk; Z. Skupień

Publisher
Elsevier Science
Year
1991
Tongue
English
Weight
700 KB
Volume
96
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

Tough nonhamiltonian n-vertex graphs with n 2 3 are known to exist only for n 3 7. The maximum size among them is shown to be 6 + (n -3)(n -4)/2. All corresponding maximum graphs are K,*(3K,*+ K,_,) for n 5 7 (unique if n #9) and, additionally, K,*Kp(3K,*+ KS)

if n = 9, where + stands for the non-associative join and 3K,*+ K, with t z 3 denotes the complete graph K, together with three disjoint hanging edges (and vertices).

📜 SIMILAR VOLUMES

All nonhamiltonian tough graphs satisfyi
All nonhamiltonian tough graphs satisfying a 3-degree sum and fan-type conditions
✍ W. Frydrych 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 819 KB

Frydrych, W., All nonhamiltonian tough graphs satisfying a 3-degree sum and Fan-type conditions, Discrete Mathematics 121 (1993) 93-104. It is shown that if G is a l-tough nonhamiltonian graph on even number vertices n>4 such that d(x)+d(y)+d(z)>n for every triple of mutually distinct and nonadjace

Arc reversal in nonhamiltonian circulant
Arc reversal in nonhamiltonian circulant oriented graphs
✍ Jozef Jirásek 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 108 KB

## Abstract Locke and Witte described infinite families of nonhamiltonian circulant oriented graphs. We show that for infinitely many of them the reversal of any arc produces a hamiltonian cycle. This solves an open problem stated by Thomassen in 1987. We also use these graphs to construct countere

A nonhamiltonian five-regular multitrian
A nonhamiltonian five-regular multitriangular polyhedral graph
✍ Hansjoachim Walther 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 189 KB

In the class of all 5-regular multitriangular polyhedral graphs there exists a nonhamiltonian member with 1728 vertices, and moreover, this class has a shortness exponent smaller than one.

Longest cycles in tough graphs
Longest cycles in tough graphs
✍ Jung, H.A.; Wittmann, P. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 347 KB 👁 2 views

In this article, we establish bounds for the length of a longest cycle C in a 2-connected graph G in terms of the minimum degree δ and the toughness t. It is shown that C is a Hamiltonian cycle or |C| ≥ (t + 1)δ + t.

Circumferences in 1-tough graphs
Circumferences in 1-tough graphs
✍ Hao Li 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 270 KB

Bauer, Morgana, Schmeichel and Veldman have conjectured that the circumference c(G) of any 1-tough graph G of order n >t 3 with minimum degree 6 >/n/3 is at least min{n,(3n+ 1)/4+6/2} ~>(lln+ 3)/12. They proved that under these conditions, c(G)>~min{n,n/2+6}>15n/6. Then Bauer, Schmeichei and Veldman