✦ LIBER ✦

On relative length of longest paths and cycles

✍ Scribed by Kenta Ozeki; Masao Tsugaki; Tomoki Yamashita

Publisher: John Wiley and Sons
Year: 2009
Tongue: English
Weight: 144 KB
Volume: 62
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20403

No coin nor oath required. For personal study only.

✦ Synopsis

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, then p(G)−c(G)⩽2. By considering our result and the results in [J Graph Theory 20 (1995), 213–225; Amer Math Monthly 67 (1950), 55], we propose a conjecture which is a generalization of Bondy's conjecture. Furthermore, using our result, for a graph satisfying the above conditions, we obtain a new lower bound of the circumference and establish Thomassen's conjecture. © 2009 Wiley Periodicals, Inc. J Graph Theory 62, 279–291, 2009

📜 SIMILAR VOLUMES

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 paths, long cycles, and their relat

Long paths, long cycles, and their relative length

✍ Saito, Akira 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 117 KB 👁 1 views

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

Longest paths and cycles in bipartite or

Longest paths and cycles in bipartite oriented graphs

✍ Zhang Ke Min 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 430 KB 👁 1 views

In this paper we obtain two sufficient conditions, Ore type (Theorem 1) and Dirac type (Theorem 2). on the degrees of a bipartite oriented graph for ensuring the existence of long paths and cycles. These conditions are shown to be the best possible in a sense. An oriented graph is a digraph without

Longest paths and cycles in K1,3-free gr

Longest paths and cycles in K1,3-free graphs

✍ Manton M. Matthews; David P. Sumner 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 383 KB 👁 2 views

In this article w e show that the standard results concerning longest paths and cycles in graphs can be improved for K,,,-free graphs. We obtain as a consequence of these results conditions for the existence of a hamiltonian path and cycle in K,,,-free graphs.

A bound on the chromatic number using th

A bound on the chromatic number using the longest odd cycle length

✍ Sreyash Kenkre; Sundar Vishwanathan 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 120 KB 👁 1 views

## Abstract Let __G__ be a non‐bipartite graph with ℓ as the length of the longest odd cycle. Erdös and Hajnal proved that χ(__G__) ≤ ℓ + 1. We show that the only graphs for which this is tight are those that contain __K__~ℓ~ + 1 and further, if __G__ does not contain __K__~ℓ~ then χ(__G__) ≤ ℓ −1.

On longest cycles and strongly linking v

On longest cycles and strongly linking vertex sets

✍ Bert Fassbender 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 245 KB 👁 1 views

Let G be a simple non-hamiltonian graph, let C be a longest cycle in G, and let p be a positive integer. By considering a special form of connectivity, we obtain a sufficient condition on degrees for the nonexistence of ( p -1)-path-connected components in G -C.