✦ LIBER ✦

A degree sum condition for longest cycles in 3-connected graphs

✍ Scribed by Tomoki Yamashita

Publisher: John Wiley and Sons
Year: 2007
Tongue: English
Weight: 110 KB
Volume: 54
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20210

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

For a graph G, we denote by d~G~(x) and κ(G) the degree of a vertex x in G and the connectivity of G, respectively. In this article, we show that if G is a 3‐connected graph of order n such that d~G~(x) + d~G~(y) + d~G~(z) ≥ d for every independent set {x, y, z}, then G contains a cycle of length at least min{d − κ(G), n}. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 277–283, 2007

📜 SIMILAR VOLUMES

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

Connected subgraphs with small degree su

Connected subgraphs with small degree sums in 3-connected planar graphs

✍ Enomoto, Hikoe; Ota, Katsuhiro 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 213 KB 👁 2 views

It is well-known that every planar graph has a vertex of degree at most five. Kotzig proved that every 3-connected planar graph has an edge xy such that deg(x) + deg(y) ≤ 13. In this article, considering a similar problem for the case of three or more vertices that induce a connected subgraph, we sh

Degree sums for edges and cycle lengths

Degree sums for edges and cycle lengths in graphs

✍ Brandt, Stephan; Veldman, Henk Jan 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 71 KB 👁 3 views

Let G be a graph of order n satisfying d(u) + d(v) ≥ n for every edge uv of G. We show that the circumference-the length of a longest cycle-of G can be expressed in terms of a certain graph parameter, and can be computed in polynomial time. Moreover, we show that G contains cycles of every length be

A Degree Sum Condition for the Existence

A Degree Sum Condition for the Existence of a Contractible Edge in a κ-Connected Graph

✍ Matthias Kriesell 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 184 KB

It is known that a noncomplete }-connected graph of minimum degree of at least w 5} 4 x contains a }-contractible edge, i.e., an edge whose contraction yields again a }-connected graph. Here we prove the stronger statement that a noncomplete }-connected graph for which the sum of the degrees of any

Degree sum for a triangle in a graph

✍ Genghua Fan 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 379 KB 👁 1 views

Let %(n; e) denote the class of graphs on n vertices and e edges. Define f(n, e) = min max{C:=, d(u,):{u,, up, uJ} induces a triangle in G}, where the maximum is taken over all triangles in the graph G and the minimum is taken over all G in %(n; e). From Turan's theorem, f(n, e) = 0 if e 5 n 2 / 4 ;