✦ LIBER ✦

Long cycles passing through a specified path in a graph

✍ Scribed by Hirohata, Kazuhide

Publisher: John Wiley and Sons
Year: 1998
Tongue: English
Weight: 247 KB
Volume: 29
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199811)29:3<177::aid-jgt5>3.0.co;2-n

No coin nor oath required. For personal study only.

✦ Synopsis

For a graph G and an integer

an independent set of vertices in G}. Enomoto proved the following theorem. Let s ≥ 1 and let G be a (s + 2)-connected graph. Then G has a cycle of length ≥ min{|V (G)|, σ 2 (G) -s} passing through any path of length s. We generalize this result as follows. Let k ≥ 3 and s ≥ 1 and let G be a (k+s-1)-connected graph. Then G has a cycle of length ≥ min{|V (G)|, 2 k σ k (G) -s} passing through any path of length s.

📜 SIMILAR VOLUMES

Long cycles passing through a specified

Long cycles passing through a specified edge in a 3-connected graph

✍ Enomoto, Hikoe; Hirohata, Kazuhide; Ota, Katsuhiro 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 80 KB 👁 2 views

We prove the following theorem: For a connected noncomplete graph Then through each edge of G there passes a cycle of length ≥ min{|V (G)|, τ(G) -1}.

Covering a graph with cycles passing thr

Covering a graph with cycles passing through given edges

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

We propose a conjecture: for each integer k ≥ 2, there exists N (k) such that if G is a graph of order n ≥ N (k) and d(x) + d(y) ≥ n + 2k -2 for each pair of nonadjacent vertices x and y of G, then for any k independent edges e 1 , . . . , e k of G, there exist If this conjecture is true, the condi

Long paths through four vertices in a 2-

Long paths through four vertices in a 2-connected graph

✍ Barovich, Mark V. 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 252 KB 👁 2 views

Let G be a 2-connected graph, let u and v be distinct vertices in V (G), and let X be a set of at most four vertices lying on a common (u

On the diameter ofi-center in a graph wi

On the diameter ofi-center in a graph without long induced paths

✍ Dong, Jinquan 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 117 KB 👁 2 views

A graph G is said to be P t -free if it does not contain an induced path on t vertices. The i-center C i (G) of a connected graph G is the set of vertices whose distance from any vertex in G is at most i. Denote by I(t) the set of natural numbers i, t/2 ≤ i ≤ t -2, with the property that, in every c