✦ LIBER ✦

Packing and covering dense graphs

✍ Scribed by Noga Alon; Yair Caro; Raphael Yuster

Publisher: John Wiley and Sons
Year: 1998
Tongue: English
Weight: 498 KB
Volume: 6
Category: Article
ISSN: 1063-8539
DOI: 10.1002/(sici)1520-6610(1998)6:6<451::aid-jcd6>3.0.co;2-e

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Subdivisions, parity and well-covered gr

Subdivisions, parity and well-covered graphs

✍ Caro, Yair 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 121 KB 👁 2 views

A graph is well-covered if every maximal independent set is maximum. This concept, introduced by Plummer in 1970 (J. Combin. Theory 8 (1970)), is the focal point of much interest and current research. We consider well-covered 2-degenerate graphs and supply a structural (and polynomial time algorithm

Packing complete multipartite graphs wit

Packing complete multipartite graphs with 4-cycles

✍ Elizabeth J. Billington; Hung-Lin Fu; C.A. Rodger 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 394 KB

Well covered simplicial, chordal, and ci

Well covered simplicial, chordal, and circular arc graphs

✍ Prisner, Erich; Topp, Jerzy; Vestergaard, Preben Dahl 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 427 KB 👁 2 views

A graph G is called well covered if every two maximal independent sets of G have the same number of vertices. In this paper, we,characterize well covered simplicial, chordal and circular arc graphs.

Packing two bipartite graphs into a comp

Packing two bipartite graphs into a complete bipartite graph

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

For two integers a and b, we say that a bipartite graph G admits an (a, b)bipartition if G has a bipartition (X, Y ) such that |X| = a and |Y | = b. We say that two bipartite graphs G and H are compatible if, for some integers a and b, both G and H admit (a, b)-bipartitions. In this paper, we prove

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