✦ LIBER ✦

Intersections of Longest Cycles in k-Connected Graphs

✍ Scribed by Guantao Chen; Ralph J Faudree; Ronald J Gould

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 279 KB
Volume: 72
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1997.1802

No coin nor oath required. For personal study only.

✦ Synopsis

Let G be a connected graph, where k 2. S. Smith conjectured that every two longest cycles of G have at least k vertices in common. In this note, we show that every two longest cycles meet in at least ck 3Â5 vertices, where cr0.2615.

1998 Academic Press

In this note, we provide a lower bound on the number of vertices in the intersection of any two longest cycles in a k-connected graph (k 2). This work is inspired by the following conjecture due to Scott Smith; see [2,6].

Conjecture 1. In a k-connected graph, two longest cycles meet in at least k vertices.

According to Gro tchel [6], the conjecture has been verified up to k=10. Theorem 1.2(a) of [6] showed the conjecture is true up to k=6. Further, Gro tchel and Nemhauser [7] studied the properties of two longest cycles meeting in exactly 2 vertices in 2-connected graphs and Gro tchel [6] studied the properties of two longest cycles meeting in k vertices for k=3, 4, 5. For Article No. TB971802 143 0095-8956Â98 25.00

📜 SIMILAR VOLUMES

Intersections of longest cycles in grid

Intersections of longest cycles in grid graphs

✍ Menke, B.; Zamfirescu, T.; Zamfirescu, C. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 292 KB 👁 3 views

It is well-known that the largest cycles of a graph may have empty intersection. This is the case, for example, for any hypohamiltonian graph. In the literature, several important classes of graphs have been shown to contain examples with the above property. This paper investigates a (nontrivial) cl

Nonseparating cycles in K-Connected grap

Nonseparating cycles in K-Connected graphs

✍ Carsten Thomassen 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 192 KB 👁 1 views

## Abstract We show that every __k__‐connected graph with no 3‐cycle contains an edge whose contraction results in a __k__‐connected graph and use this to prove that every (__k__ + 3)‐connected graph contains a cycle whose deletion results in a __k__‐connected graph. This settles a problem of L. Lo

Toughness and longest cycles in 2-connec

Toughness and longest cycles in 2-connected planar graphs

✍ B�hme, T.; Broersma, H. J.; Veldman, H. J. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 390 KB 👁 2 views

Let G be a planar graph on n vertices, let c(G) denote the length of a longest cycle of G, and let w(G) denote the number of components of G. By a well-known theorem of Tutte, c(G) = n (i.e., G is hamiltonian) if G is 4-connected. Recently, Jackson and Wormald showed that c(G) 2 ona for some positiv

Longest cycles in 3-connected graphs con

Longest cycles in 3-connected graphs contain three contractible edges

✍ Nathaniel Dean; Robert L. Hemminger; Katsuhiro Ota 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 221 KB 👁 1 views

We show that if G is a 3-connected graph of order at least seven, then every longest path between distinct vertices in G contains at least two contractible edges. An immediate corollary is that longest cycles in such graphs contain at least three contractible edges. We consider only finite undirect

Relative length of longest paths and cyc

Relative length of longest paths and cycles in 3-connected graphs

✍ Rao Li; Akira Saito; R.H. Schelp 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 184 KB 👁 2 views

## Abstract For a graph __G__, let __p(G)__ denote the order of a longest path in __G__ and __c(G)__ the order of a longest cycle in __G__, respectively. We show that if __G__ is a 3‐connected graph of order __n__ such that $\textstyle{\sum^{4}\_{i=1}\,{\rm deg}\_{G}\,x\_{i} \ge {3\over2}\,n + 1}$

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.