✦ LIBER ✦

Some remarks on packing trees

✍ Scribed by Béla Bollobás

Publisher: Elsevier Science
Year: 1983
Tongue: English
Weight: 63 KB
Volume: 46
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(83)90254-6

No coin nor oath required. For personal study only.

✦ Synopsis

The graphs Gt, G2 ..... Gt are said to be packed into a graph G if G has edge disjoint subgraphs G'~, G~ ..... G~ such that G'~ ~ G~, i = 1 ..... I. For simplicity one usuaUy identifies G~ with G~. (See [1,Ch. VIII] for a number of packing results.) Gyfirf~is and Lehel conjectured ([3], see also [1, Conjecture 23, p. 436]) that if T~ is a tree of order i for i = 2, 3 ..... n then the graphs T2, T.~ ..... T, can be packed into K". Gyfirffis and Lehel proved their conjecture in the ca~c when all but at most two of the trees are stars. Furthermore, Straight [4] verified the conjecture for n <~7. The aim of this note is to point out that a fair number of trees of different order can be packed into K" provided the trees are not t(x) large.

📜 SIMILAR VOLUMES

Some remarks on channelling and on radia

Some remarks on channelling and on radial dispersion in packed beds

✍ E. Tsotsas; E.U. Schlünder 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 397 KB

On packing trees into complete bipartite

On packing trees into complete bipartite graphs

✍ Raphael Yuster 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 124 KB

Some remarks on domination

✍ D. Archdeacon; J. Ellis-Monaghan; D. Fisher; D. Froncek; P.C.B. Lam; S. Seager; 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 49 KB

## Abstract We prove a conjecture of Favaron et al. that every graph of order __n__ and minimum degree at least three has a total dominating set of size at least __n__/2. We also present several related results about: (1) extentions to graphs of minimum degree two, (2) examining graphs where the bo

Some considerations on permutation trees

✍ A. Panayotopoulos 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 456 KB

This paper deals with the determination of subsets of permutations, which satisfy certain conditions. Two new methods are proposed; one for the permutations that correspond to a given pattern, and one for the triple T = (A, M, CM) as it has been introduced by Viennot [S]. Both these two methods, can

Some Remarks on Toroidal Problems

✍ F. Cap 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 414 KB 👁 1 views

Some remarks on indiscernible sequences

✍ Enrique Casanovas 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 84 KB

## Abstract We prove a property of generic homogeneity of tuples starting an infinite indiscernible sequence in a simple theory and we use it to give a shorter proof of the Independence Theorem for Lascar strong types. We also characterize the relation of starting an infinite indiscernible sequence