✦ LIBER ✦

Graph decompositions without isolates

✍ Scribed by Nathan Linial

Publisher: Elsevier Science
Year: 1984
Tongue: English
Weight: 546 KB
Volume: 36
Category: Article
ISSN: 0095-8956
DOI: 10.1016/0095-8956(84)90010-8

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Graph Decompositions without Isolated Ve

Graph Decompositions without Isolated Vertices

✍ H. Enomoto 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 405 KB

We prove the following conjecture of A. Frank (Fifth British Combinatorial Conference, Aberdeen, Scotland, 1975): Let \(G\) be a connected simple graph of order \(n\), and \(n=n_{1}+\cdots+n_{k}\) be a partition of \(n\) with \(n_{i} \geqslant 2\). Suppose that the minimum degree of \(G\) is at leas

Graph decompositions without isolated ve

Graph decompositions without isolated vertices III

✍ Enomoto, Hikoe; Matsunaga, Shinsuke 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 135 KB 👁 1 views

Let G be a graph of order n, and n = k i=1 a i be a partition of n with a i ≥ 2. In this article we show that if the minimum degree of G is at least 3k -2, then for any distinct and ``the subgraph induced by A i contains no isolated vertices'' for all i, 1 ≤ i ≤ k. Here, the bound on the minimum de

Perfect graph decompositions

✍ Zsolt Tuza 📂 Article 📅 1991 🏛 Springer Japan 🌐 English ⚖ 291 KB

Low diameter graph decompositions

✍ Nathan Linial; Michael Saks 📂 Article 📅 1993 🏛 Springer-Verlag 🌐 English ⚖ 916 KB

Sparsity-certifying Graph Decompositions

✍ Ileana Streinu; Louis Theran 📂 Article 📅 2009 🏛 Springer Japan 🌐 English ⚖ 467 KB

On graph decompositions modulo k

✍ A.D. Scott 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 153 KB

We prove that, for every integer k >~ 2, every graph has an edge-partition into 5k 2 log k sets, each of which is the edge-set of a graph with all degrees congruent to 1 mod k. This answers a question of Pyber. Pyber proved that every graph G has an edge-partition into four sets, each of which is