✦ LIBER ✦

Sparsity-certifying Graph Decompositions

✍ Scribed by Ileana Streinu; Louis Theran

Publisher: Springer Japan
Year: 2009
Tongue: English
Weight: 467 KB
Volume: 25
Category: Article
ISSN: 0911-0119
DOI: 10.1007/s00373-008-0834-4

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Perfect graph decompositions

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

Graph decompositions without isolates

✍ Nathan Linial 📂 Article 📅 1984 🏛 Elsevier Science 🌐 English ⚖ 546 KB

Low diameter graph decompositions

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

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

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

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