Packing of graphs

Woźniak Mariusz

GDML_Books, (1997), p.

Résumé

PrefaceThere are two basic reference texts on packing theory: the last chapter of Bollobás's book [6] (1978) and the 4th chapter of Yap's book [85] (1986). They still remain the main references to packing problems. However, many papers related to these problems have recently been published and the reason for writing this survey is to gather in a systematic form results scattered throughout the literature.I wish I could name all who deserve my thanks. I am particularly grateful to A. P. Wojda for introducing me to graph theory, and to Z. Skupień for his interest in my research and for many stimulating conversations.During my work, I had the opportunity to stay for some time at Laboratoire de Recherche en Informatique (Orsay, Université Paris-Sud), where a part of this survey was written. I would like to thank all members of Equipe Graphes from Orsay for the invitation and hospitality. This stay was partially supported by TEMPUS grant IMG-93-PL-1220.Finally, I wish to express my deep gratitude to the referee for numerous helpful comments.

CONTENTSPreface............................................................................51. Introduction.................................................................5  1.1. Basic graph-theoretic terms...................................6  1.2. Some families of graphs.........................................8  1.3. Edge-disjoint placements of graphs.......................92. Embeddings of graphs................................................9  2.1. Basic result............................................................9  2.2. Self-complementary permutations........................10  2.3. Embeddings without fixed points...........................15  2.4. Graphs without small cycles..................................18  2.5. Uniquely embeddable graphs...............................233. Packing of two graphs...............................................23  3.1. Packing of two graphs of small size......................23  3.2. Packing an undense and a dense graph.............25  3.3. Products of sizes and degrees.............................26  3.4. Sum of sizes.........................................................28  3.5. Erdős-Sós Conjecture..........................................31    3.5.1. Special families of trees...................................31    3.5.2. Particular values of parameters.......................37    3.5.3. Special families of graphs................................39  3.6. Other problems related to trees and forests.........40  3.7. Some generalizations...........................................414. Packing of three graphs............................................45  4.1. Triple placement of graphs...................................45  4.2. Permutation structure...........................................50  4.3. 3-placement of a tree...........................................52  4.4. Packing three trees..............................................54  4.5. Packing three trees - general case......................58  4.6. Packing three forests...........................................585. Some special problems.............................................59  5.1. Packing a graph with its square...........................59  5.2. Careful packing of a graph...................................62  5.3. Packing of sequences of trees.............................66    5.3.1. Tree Packing Conjecture.................................66    5.3.2. Not too large trees...........................................69  5.4. Bipartite graphs....................................................70  5.5. Packing of digraphs..............................................72Bibliography...................................................................75

1991 Mathematics Subject Classification: 05C70, 05C35.

Détail

Zbl 0884.05069

EUDML-ID : urn:eudml:doc:271750