✦ LIBER ✦

Intersections of longest cycles in grid graphs

✍ Scribed by Menke, B.; Zamfirescu, T.; Zamfirescu, C.

Publisher: John Wiley and Sons
Year: 1997
Tongue: English
Weight: 292 KB
Volume: 25
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199705)25:1<37::aid-jgt2>3.0.co;2-j

No coin nor oath required. For personal study only.

✦ Synopsis

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) class of graphs which, on the contrary, admits no such example.

📜 SIMILAR VOLUMES

Longest cycles in tough graphs

✍ Jung, H.A.; Wittmann, P. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 347 KB 👁 1 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.

Hamilton cycles in block-intersection gr

Hamilton cycles in block-intersection graphs of triple systems

✍ Peter Horák; David A. Pike; Michael E Raines 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 336 KB 👁 1 views

Given a BIBD S = (V, B), its 1-block-intersection graph GS has as vertices the elements of B; two vertices B1, B2 ∈ B are adjacent in GS if |B1 ∩ B2| = 1. If S is a triple system of arbitrary index λ, it is shown that GS is hamiltonian.

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

Proof of a conjecture on cycles in a bip

Proof of a conjecture on cycles in a bipartite graph

✍ Wang, Hong 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 244 KB 👁 2 views

It was conjectured in [Wang, to appear in The Australasian Journal of Combinatorics] that, for each integer k ≥ 2, there exists . This conjecture is also verified for k = 2, 3 in [Wang, to appear; Wang, manuscript]. In this article, we prove this conjecture to be true if n ≥ 3k, i.e., M (k) ≤ 3k. W

Edge disjoint Hamilton cycles in sparse

Edge disjoint Hamilton cycles in sparse random graphs of minimum degree at leastk

✍ Bollob�s, B.; Cooper, C.; Fenner, T. I.; Frieze, A. M. 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 175 KB 👁 2 views

Let G n,m,k denote the space of simple graphs with n vertices, m edges, and minimum degree at least k, each graph G being equiprobable. Let G have property A k , if G contains (k -1)/2 edge disjoint Hamilton cycles, and, if k is even, a further edge disjoint matching of size n/2 . We prove that, for

On weights of induced paths and cycles i

On weights of induced paths and cycles in claw-free and K1,r-free graphs

✍ J. Harant; M. Voigt; S. Jendrol; B. Randerath; Z. Ryjáček; I. Schiermeyer 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 175 KB 👁 1 views