✦ LIBER ✦

Long paths, long cycles, and their relative length

✍ Scribed by Saito, Akira

Publisher: John Wiley and Sons
Year: 1999
Tongue: English
Weight: 117 KB
Volume: 30
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199902)30:2<91::aid-jgt3>3.0.co;2-8

No coin nor oath required. For personal study only.

✦ Synopsis

Let p(G) and c(G) be the order of a longest path and a longest cycle in a graph G, respectively. Let σ 3 (G) = min{deg G x + deg G y + deg G z : {x, y, z} is an independent set of vertices of G}. Extending the result by Enomoto et al. (J Graph Th 20 (1995), 213-225) on the difference p(G) -c(G), we prove that a 2-connected graph G of order n satisfies (

Then, using the above result, we give a new lower bound for p(G). This bound corresponds to the bound on c(G) given by Bauer et al.

📜 SIMILAR VOLUMES

On relative length of longest paths and

On relative length of longest paths and cycles

✍ Kenta Ozeki; Masao Tsugaki; Tomoki Yamashita 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 144 KB 👁 1 views

## Abstract For a graph __G__, __p__(__G__) and __c__(__G__) denote the order of a longest path and a longest cycle of __G__, respectively. In this paper, we prove that if __G__ is a 3 ‐connected graph of order __n__ such that the minimum degree sum of four independent vertices is at least __n__+ 6

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}$

Long dominating cycles and paths in grap

Long dominating cycles and paths in graphs with large neighborhood unions

✍ H. J. Broersma; H. J. Veldman 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 413 KB 👁 1 views

## Abstract Let __G__ be a graph of order __n__ and define __NC(G)__ = min{|__N__(__u__) ∪ __N__(__v__)| |__uv__ ∉ __E__(__G__)}. A cycle __C__ of __G__ is called a __dominating cycle__ or __D__‐__cycle__ if __V__(__G__) ‐ __V__(__C__) is an independent set. A __D__‐__path__ is defined analogously.

Long cycles passing through a specified

Long cycles passing through a specified path in a graph

✍ Hirohata, Kazuhide 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 247 KB 👁 2 views

## 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 ≥

Long lesion length assessment

✍ Dixon, S. R. ;Ormiston, J. A. ;Webster, M. W. I. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 63 KB

Fig. 1. A: Radiopaque end of a Balance guidewire (30 mm) positioned across a lesion in left anterior descending artery. B: Cineangiogram taken after deployment of a 35 mm length ACS Multilink stent.

Long cycles in critical graphs

✍ Noga Alon; Michael Krivelevich; Paul Seymour 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 57 KB 👁 3 views