✦ LIBER ✦

Covering the vertices of a graph by cycles of prescribed length

✍ Scribed by D. Amar; I. Fournier; A. Germa

Publisher: John Wiley and Sons
Year: 1989
Tongue: English
Weight: 321 KB
Volume: 13
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190130307

No coin nor oath required. For personal study only.

✦ Synopsis

The main theorem of that paper is the following: let G be a graph of order n, of size at least (nZ -3n + 6 ) / 2 . For any integers k, n,, n2,. . . , nk such that n = n, + n2 + ... + nk and n, 2 3, there exists a covering of the vertices of G by disjoint cycles (C,),=,..,k with ICjl = n,, except when n = 6, n, = 3, n2 = 3, and G is isomorphic to G,, the complement of G, consisting of a C, and a stable set of three vertices, or when n = 9, n, = n2 = n3 = 3, and G is isomorphic to G2, the complement of G2 consisting of a complete graph on four vertices and a stable set of five vertices.

We prove an analogous theorem for bipartite graphs: let G be a bipartite balanced graph of order 2n, of size a t least n2 -n + 2. For any integers s, n,, n2,. . . , n, with n, z 2 and n = n, + n2 + ... + n,, there exists a covering of the vertices of G by s disjoint cycles C,, with IC,l = 2n,.

📜 SIMILAR VOLUMES

Covering the Edges of a Graph by a Presc

Covering the Edges of a Graph by a Prescribed Tree with Minimum Overlap

✍ Noga Alon; Yair Caro; Raphael Yuster 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 360 KB

Let H=(V H , E H ) be a graph, and let k be a positive integer. A graph G=(V G , E G ) is H-coverable with overlap k if there is a covering of the edges of G by copies of H such that no edge of G is covered more than k times. Denote by overlap(H, G) the minimum k for which G is H-coverable with over

Graphs with a Cycle of Length Divisible

Graphs with a Cycle of Length Divisible by Three

✍ G.T. Chen; A. Saito 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 468 KB

In this paper, we will prove that every graph \(G\) with minimum degree \(\delta(G) \geqslant 3\) contains a cycle of length divisible by three. This was conjectured to be true by Barefoot, Clark, Douthett, and Entringer. 11994 Academic Press, Inc.

Maximum packings of the complete graph w

Maximum packings of the complete graph with uniform length cycles

✍ Daniel Horsley 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 86 KB

In this paper we find the maximum number of pairwise edgedisjoint m-cycles which exist in a complete graph with n vertices, for all values of n and m with 3 ≤ m ≤ n.

On the number of cycles of length 4 in a

On the number of cycles of length 4 in a maximal planar graph

✍ Ahmad Fawzi Alameddine 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 148 KB 👁 2 views

## Abstract Let __p__ and __C__~4~ (__G__) be the number of vertices and the number of 4‐cycles of a maximal planar graph __G__, respectively. Hakimi and Schmeichel characterized those graphs __G__ for which __C__~4~ (__G__) = 1/2(__p__^2^ + 3__p__ ‐ 22). This characterization is correct if __p__ ≥

Covering the Edges of a Connected Graph

Covering the Edges of a Connected Graph by Paths

✍ L. Pyber 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 316 KB

We prove that every connected graph on n vertices can be covered by at most nÂ2+O(n 3Â4 ) paths. This implies that a weak version of a well-known conjecture of Gallai is asymptotically true.

Partitions of a graph into paths with pr

Partitions of a graph into paths with prescribed endvertices and lengths

✍ Hikoe Enomoto; Katsuhiro Ota 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 95 KB 👁 3 views

For a graph G, let ' 2 (G ) denote the minimum degree sum of a pair of nonadjacent vertices. We conjecture that if |V(G)| n i 1 k a i and ' 2 (G ) ! n k À 1, then for any k vertices v 1 , v 2 , F F F , v k in G, there exist vertex-disjoint paths P 1 , P 2 , F F F , P k such that |V (P i )| a i and v