✦ LIBER ✦

Minimum cycle covers of graphs

✍ Scribed by Fan, Genghua

Publisher: John Wiley and Sons
Year: 1997
Tongue: English
Weight: 145 KB
Volume: 25
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199707)25:3<229::aid-jgt6>3.0.co;2-n

No coin nor oath required. For personal study only.

✦ Synopsis

Some new results on minimum cycle covers are proved. As a consequence, it is obtained that the edges of a bridgeless graph G can be covered by cycles of total length at most |E(G)| + 25 24 (|V (G)| -1), and at most |E(G)| + |V (G)| -1 if G contains no circuit of length 8 or 12.

📜 SIMILAR VOLUMES

Minimum-weight cycles in 3-separable gra

Minimum-weight cycles in 3-separable graphs

✍ Coullard, Collette R.; Gardner, L. Leslie; Wagner, Donald K. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 136 KB 👁 1 views

This paper presents a polynomial-time algorithm for the minimum-weight-cycle problem on graphs that decompose via 3-separations into well-structured graphs. The problem is NP-hard in general. Graphs that decompose via 3-separations into well-structured graphs include Halin, outer-facial, deltawye, w

Minimum bandwidth problem for embedding

Minimum bandwidth problem for embedding graphs in cycles

✍ Lin, Yixun 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 98 KB 👁 1 views

For the bandwidth B(G) and the cyclic bandwidth B c (G) of a graph G, it is known that 1 2 B(G) °Bc (G) °B(G). In this paper, the criterion conditions for two extreme cases B c (G) Å B(G) and B c (G) Å 1 2 B(G) are studied. From this, some exact values of B c (G) for special graphs can be obtained.

Covering a graph with cycles passing thr

Covering a graph with cycles passing through given edges

✍ Wang, Hong 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 91 KB 👁 1 views

We propose a conjecture: for each integer k ≥ 2, there exists N (k) such that if G is a graph of order n ≥ N (k) and d(x) + d(y) ≥ n + 2k -2 for each pair of nonadjacent vertices x and y of G, then for any k independent edges e 1 , . . . , e k of G, there exist If this conjecture is true, the condi

Edge disjoint Hamilton cycles in sparse

Edge disjoint Hamilton cycles in sparse random graphs of minimum degree at leastk

✍ Bollob�s, B.; Cooper, C.; Fenner, T. I.; Frieze, A. M. 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 175 KB 👁 1 views

Let G n,m,k denote the space of simple graphs with n vertices, m edges, and minimum degree at least k, each graph G being equiprobable. Let G have property A k , if G contains (k -1)/2 edge disjoint Hamilton cycles, and, if k is even, a further edge disjoint matching of size n/2 . We prove that, for

Enumeration of connected graph coverings

✍ Kwak, Jin Ho; Lee, Jaeun 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 207 KB 👁 1 views

The number of the isomorphism classes of n-fold coverings of a graph G is enumerated by the authors (Canad.

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 👁 1 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