𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Tree decompositions for a class of graphs

✍ Scribed by Minyong Shi; Yanjun Li; Feng Tian

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
915 KB
Volume
189
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

For a graph G, if E(G) can be partitioned into several pairwise disjoint sets as {EI,& . . . , El} such that for any i with 1 3. We prove that (i) for any %-graph of order n 23, it has both a {n,n -2}tree-decomposition and a {n -1,n -1}-tree-decomposition, and moreover, these two kinds of tree-decompositions can be transformed to each other; (ii) for any Y3-graph of order n 24, it has three kinds of tree-decompositions: {n, n

πŸ“œ SIMILAR VOLUMES

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

Tree decomposition of graphs
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.

Decompositions of graphs into trees
Decompositions of graphs into trees
✍ Zbigniew Lonc πŸ“‚ Article πŸ“… 1989 πŸ› John Wiley and Sons 🌐 English βš– 460 KB
Packing and Decomposition of Graphs with
Packing and Decomposition of Graphs with Trees
✍ Raphael Yuster πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 214 KB

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