✦ LIBER ✦

Generation of trees of a graph with the use of decomposition

✍ Scribed by Jacek Wojciechowski

Publisher: Elsevier Science
Year: 1984
Tongue: English
Weight: 1015 KB
Volume: 318
Category: Article
ISSN: 0016-0032
DOI: 10.1016/0016-0032(84)90011-5

No coin nor oath required. For personal study only.

✦ Synopsis

The method of tree generation of a graph decomposed into any number of parts is described in this paper. The decomposition of a graph is dejined. Theformulafor the generation of trees of a decomposed graph is given in Theorem I. The necessary and suflcient conditions which a graph decomposition must satisfy to avoid duplications in the generated set of trees are discussed and results are summarized in Theorems I1 and III. A criterion for existence of such a decomposition is formulated in Theorem IV and also an appropriate algorithm for the graph decomposition is suggested.

📜 SIMILAR VOLUMES

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.

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

Decompositions of graphs into trees

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

Generation of all possible trees of a gr

Generation of all possible trees of a graph in independent groups

✍ R. Hashemian; M.S. Bakhtiar 📂 Article 📅 1975 🏛 Elsevier Science 🌐 English ⚖ 268 KB

A special graph, the PS graph, is introduced and an algorithm is developed to generate all trees of such graphs. It is proved that for any given graph, G there exists certain number of PS graphs, obtained from G, such that the collection of all trees of all such PS graph span all trees of G with no

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

Some results on tree decomposition of gr

Some results on tree decomposition of graphs

✍ Guoli Ding; Bogdan Oporowski 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 968 KB

## Abstract We investigate tree decompositions (__T__,(__X__~t~)~tϵV(T)~) whose width is “close to optimal” and such that all the subtrees of __T__ induced by the vertices of the graph are “small.” We prove the existence of such decompositions for various interpretations of “close to optimal” and “