✦ LIBER ✦

Packing and Decomposition of Graphs with Trees

✍ Scribed by Raphael Yuster

Publisher: Elsevier Science
Year: 2000
Tongue: English
Weight: 214 KB
Volume: 78
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1999.1934

No coin nor oath required. For personal study only.

✦ Synopsis

Let H be a tree on h 2 vertices. It is shown that if n is sufficiently large and G=(V, E ) is an n-vertex graph with $(G) wnÂ2x , then there are w |E |Â(h&1)x edge-disjoint subgraphs of G which are isomorphic to H. In particular, if h&1 divides |E | then there is an H-decomposition of G. This result is best possible as there are infinitely many examples of trees on h vertices and graphs G with m(h&1) edges, $(G) wnÂ2x&1, for which G has no H-decomposition.

📜 SIMILAR VOLUMES

Packing trees into planar graphs

✍ A. García; C. Hernando; F. Hurtado; M. Noy; J. Tejel 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 108 KB

## Abstract In this study, we provide methods for drawing a tree with __n__ vertices on a convex polygon, without crossings and using the minimum number of edges of the polygon. We apply the results to obtain planar packings of two trees in some specific cases. © 2002 Wiley Periodicals, Inc. J Grap

Tree decomposition of graphs

✍ Raphael Yuster 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 207 KB 👁 1 views

with ␦ G G V r2 q 10 h V log V , and h y 1 divides E , then there is a decomposition of the edges of G into copies of H. This result is asymptotically the best possible for all trees with at least three vertices.

Orthogonal Decomposition and Packing of

Orthogonal Decomposition and Packing of Complete Graphs

✍ Yair Caro; Raphael Yuster 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 165 KB

An H-decomposition of a graph G is a partition of the edge-set of G into subsets, where each subset induces a copy of the graph H. A k-orthogonal H-decomposition of a graph G is a set of k H-decompositions of G, such that any two copies of H in distinct H-decompositions intersect in at most one edge

Decompositions of graphs into trees

✍ Zbigniew Lonc 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 460 KB

Packing the Steiner trees of a graph

✍ L. Petingi; M. Talafha 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 127 KB

On resolvable tree-decompositions of com

On resolvable tree-decompositions of complete graphs

✍ Zbigniew Lonc 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 355 KB 👁 1 views

A partition of the edge set of a graph H into subsets inducing graphs H,, . . . , H, isomorphic to a graph G is said to be a G-decomposition of H. A G-decomposition of H is resolvable if the set {H,, . . . , H,} can be partitioned into subsets, called resolution classes, such that each vertex of H