✦ LIBER ✦

Degree Sums and Covering Cycles

✍ Scribed by Hikoe Enomoto; Atsushi Kaneko; Mekkia Kouider; Zsolt Tuza

Publisher: John Wiley and Sons
Year: 1995
Tongue: English
Weight: 194 KB
Volume: 20
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190200405

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

It is shown that if in a simple graph G of order n the sum of degrees of any three pairwise non‐adjacent vertices is at least n, then there are two cycles (or one cycle and an edge or a vertex) of GF that contain all the vertices. © 1995 John Wiley & Sons, Inc.

📜 SIMILAR VOLUMES

Degree sums and graphs that are not cove

Degree sums and graphs that are not covered by two cycles

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

For a graph G, let σ 3 (G) = min{deg G x + deg G y + deg G z: {x, y, z} is an independent set in G}. Enomoto et al. [Enowoto et al., J Graph Theory 20 (1995), 419-422] have proved that the vertex set of a 2-connected graph G of order n with σ 3 (G) ≥ n is covered by two cycles, edges or vertices. Ex

Long cycles in graphs with large degree

Long cycles in graphs with large degree sums and neighborhood unions

✍ Van den Heuvel, J. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 801 KB

We present and prove several results concerning the length of longest cycles in 2connected or I-tough graphs with large degree sums. These results improve many known results on long cycles in these graphs. We also consider the sharpness of the results and discuss some possible strengthenings.

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 longest cycle

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

✍ Tomoki Yamashita 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 110 KB 👁 1 views

## 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__~__

Covering a graph with cycles

✍ Hong Wang 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 444 KB

## Abstract Let __k__ and __n__ be two integers such that __k__ ≥ 0 and __n__ ≥ 3(__k__ + 1). Let __G__ be a graph of order __n__ with minimum degree at least ⌈(__n__ + __k__)/2⌉. Then __G__ contains __k__ + 1 independent cycles covering all the vertices of __G__ such that __k__ of them are triangl

Complete subgraphs with large degree sum

Complete subgraphs with large degree sums

✍ Ralph J. Faudree 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 368 KB

## Abstract Let __t__(__n, k__) denote the Turán number—the maximum number of edges in a graph on __n__ vertices that does not contain a complete graph __K__~k+1~. It is shown that if __G__ is a graph on __n__ vertices with __n__ ≥ __k__^2^(__k__ – 1)/4 and __m__ < __t__(__n, k__) edges, then __G__