✦ LIBER ✦

Circumferences in 1-tough graphs

✍ Scribed by Hao Li

Publisher: Elsevier Science
Year: 1995
Tongue: English
Weight: 270 KB
Volume: 146
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(94)00064-6

No coin nor oath required. For personal study only.

✦ Synopsis

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 improved this result by getting c(G)>lmin{n,n/2+6+ 1} >/5n/6+ 1. We show in this paper that c(G) >! min {n, (2n + 1 + 26)/3, (3n + 26 -2)/4} >/min {(8n + 3)/9, (1 In -6)/12}.

📜 SIMILAR VOLUMES

A sharp lower bound for the circumferenc

A sharp lower bound for the circumference of 1-tough graphs with large degree sums

✍ Vu Dinh Hoa 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 207 KB 👁 1 views

## Abstract We show that every 1‐tough graph __G__ on __n__ ≥ 3 vertices with σ~3~≧ __n__ has a cycle of length at least min{__n, n__ + (σ~3~/3 ) − α + 1}, where σ~3~ denotes the minimum value of the degree sum of any 3 pairwise nonadjacent vertices and α the cardinality of a miximum independent se

1-Tough cocomparability graphs are hamil

1-Tough cocomparability graphs are hamiltonian

✍ Jitender S. Deogun; Dieter Kratsch; George Steiner 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 413 KB

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.

Maximum nonhamiltonian tough graphs

✍ A. Marczyk; Z. Skupień 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 700 KB

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

Disjoint T-paths in tough graphs

✍ Tomáš Kaiser 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 120 KB

## Abstract Let __G__ be a graph and __T__ a set of vertices. A __T‐path__ in __G__ is a path that begins and ends in __T__, and none of its internal vertices are contained in __T__. We define a __T‐path covering__ to be a union of vertex‐disjoint __T__‐paths spanning all of __T__. Concentrating on

Circumference of a regular graph

✍ Min Aung 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 251 KB