✦ LIBER ✦

Pentagons and cycle coverings

✍ Scribed by Hong Wang

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

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Let G be a graph of order n ≥ 5__k__ + 2, where k is a positive integer. Suppose that the minimum degree of G is at least ⌈(n + k)/2⌉. We show that G contains k pentagons and a path such that they are vertex‐disjoint and cover all the vertices of G. Moreover, if n ≥ 5__k__ + 7, then G contains k + 1 vertex‐disjoint cycles covering all the vertices of G such that k of them are pentagons. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 194–208, 2007

📜 SIMILAR VOLUMES

Cycle and cocycle coverings of graphs

✍ Sean McGuinness 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 161 KB

In this article, we show that for any simple, bridgeless graph G on n vertices, there is a family C of at most n-1 cycles which cover the edges of G at least twice. A similar, dual result is also proven for cocycles namely: for any loopless graph G on n vertices and edges having cogirth g \* ≥ 3 and

Minimum cycle coverings and integer flow

Minimum cycle coverings and integer flows

✍ Cun-Quan Zhang 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 421 KB

## Abstract It was conjectured by Fan that if a graph __G__ = (__V,E__) has a nowhere‐zero 3‐flow, then __G__ can be covered by two even subgraphs of total size at most |__V__| + |__E__| ‐ 3. This conjecture is proved in this paper. It is also proved in this paper that the optimum solution of the C

Closure, 2-factors, and cycle coverings

Closure, 2-factors, and cycle coverings in claw-free graphs

✍ Ryj�?ek, Zden?k; Saito, Akira; Schelp, R. H. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 239 KB 👁 3 views

In this article, we study cycle coverings and 2-factors of a claw-free graph and those of its closure, which has been defined by the first author (On a closure concept in claw-free graphs, J Combin Theory Ser B 70 (1997), 217-224). For a claw-free graph G and its closure cl(G), we prove: ( 1 (2) G

Degree Sums and Covering Cycles

✍ Hikoe Enomoto; Atsushi Kaneko; Mekkia Kouider; Zsolt Tuza 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 194 KB

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

Vertex coverings by monochromatic paths

Vertex coverings by monochromatic paths and cycles

✍ A. Gyárfás 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 254 KB

We survey some results on covering the vertices of 2-colored complete graphs by t w o paths or by t w o cycles Qf different color. W e show the role of these results i n determining path Ramsey numbers and in algorithms for finding long monochromatic paths or cycles in 2-colored complete graphs. ##

Cycle-cocycle partitions and faithful cy

Cycle-cocycle partitions and faithful cycle covers for locally finite graphs

✍ Henning Bruhn; Reinhard Diestel; Maya Stein 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 112 KB

## Abstract By a result of Gallai, every finite graph __G__ has a vertex partition into two parts each inducing an element of its cycle space. This fails for infinite graphs if, as usual, the cycle space is defined as the span of the edge sets of finite cycles in __G__. However, we show that, for t