Preferencje
Język
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł książki

Packing of graphs

Autorzy
Seria
Rozprawy Matematyczne tom/nr w serii: 362 wydano: 1997
Zawartość
Warianty tytułu
Abstrakty
EN
Preface
There 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.
EN
CONTENTS
Preface............................................................................5
1. Introduction.................................................................5
1.1. Basic graph-theoretic terms...................................6
1.2. Some families of graphs.........................................8
1.3. Edge-disjoint placements of graphs.......................9
2. 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...............................23
3. 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...........................................41
4. 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...........................................58
5. 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..............................................72
Bibliography...................................................................75
Słowa kluczowe
Tematy
Kategoryzacja MSC:
Miejsce publikacji
Warszawa
Seria
Rozprawy Matematyczne tom/nr w serii: 362
Liczba stron
78
Liczba rozdzia³ów
Opis fizyczny
Dissertationes Mathematicae, Tom CCCLXII
Daty
wydano
1997
otrzymano
1995-08-07
poprawiono
1996-02-26
Twórcy
autor
• Instytut Matematyki, Akademia Górniczo-Hutnicza, Al. Mickiewicza 30, 30-059 Kraków, Poland, mwozniak@uci.agh.edu.pl
Bibliografia
• [1] M. Aigner and S. Brandt, Embedding arbitrary graphs of maximum degree two, J. London Math. Soc. (2) 48 (1993), 39-51.
• [2] M. Behzad, G. Chartrand and L. Lesniak-Foster, Graphs and Digraphs, Wadsworth, Belmont, 1979.
• [3] A. Benhocine, H. J. Veldman and A. P. Wojda, Packing of digraphs, Ars Combin. 22 (1986), 43-49.
• [4] A. Benhocine and A. P. Wojda, On self-complementation, J. Graph Theory 8 (1985), 335-341.
• [5] B. Bollobás, Graph Theory, Springer, New York, 1979.
• [6] B. Bollobás, Extremal Graph Theory, Academic Press, London, 1978.
• [7] B. Bollobás, Some remarks on packing trees, Discrete Math. 46 (1983), 203-204.
• [8] B. Bollobás and S. E. Eldridge, Packings of graphs and applications to computational complexity, J. Combin. Theory Ser. B 25 (1978), 105-124.
• [9] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, North-Holland, New York, 1976.
• [10] M. Borowiecki and P. Vaderlind, On graphs which contain all caterpillars with one leg, Reports of Dept. of Math. 4, Univ. of Stockholm, 1993.
• [11] S. Brandt, Embedding graphs without short cycles in their complements, in: Y. Alavi and A. Schwenk (eds.), Graph Theory, Combinatorics, and Applications of Graphs, Vol. 1, Wiley, 1995, 115-121.
• [12] S. Brandt, Subtrees and subforests of graphs, J. Combin. Theory Ser. B 61 (1994), 63-70.
• [13] S. Brandt, An extremal result for subgraphs with few edges, J. Combin. Theory Ser. B 64 (1995), 288-299.
• [14] S. Brandt, Sufficient conditions for graphs to contain all subgraphs of a given type, Ph.D. thesis, FU Berlin, 1994.
• [15] S. Brandt and E. Dobson, The Erdős-Sós conjecture for graphs of girth 5, Discrete Math. 150 (1996), 411-414.
• [16] D. Burns and S. Schuster, Every (p,p-2) graph is contained in its complement, J. Graph Theory 1 (1977), 277-279.
• [17] D. Burns and S. Schuster, Embedding (p,p-1) graphs in their complements, Israel J. Math. 30 (1978), 313-320.
• [18] Y. Caro and Y. Roditty, A note on packing trees into complete bipartite graphs and on Fishburn's conjecture, Discrete Math. 82 (1990), 323-326.
• [19] P. A. Catlin, Subgraphs of graphs, I, Discrete Math. 10 (1974), 225-233.
• [20] P. A. Catlin, Embedding subgraphs under extremal degree conditions, in: Proc. 8th Southeastern Conf. on Combinatorics, Graph Theory and Computing, Congr. Numer. 19, Utilitas Math., Winnipeg, MB, 1977, 139-145.
• [21] P. A. Catlin, On the Hajnal-Szemerédi theorem on disjoint cliques, Utilitas Math. 17 (1980), 163-177.
• [22] Y. Cheng, On graphs which do not contain certain trees, Ars Combin. 19 (1985), 119-152.
• [23] C. R. J. Clapham, Graphs self-complementary in Kₙ - e, Discrete Math. 81 (1990), 229-235.
• [24] C. R. J. Clapham and J. Sheehan, All trees are 1-embeddable and all except stars are 2-embeddable, Discrete Math. 120 (1993), 253-259.
• [25] K. Corrádi and A. Hajnal, On the maximal number of independent circuits in a graph, Acta Math. Acad. Sci. Hungar. 14 (1963), 423-439.
• [26] E. Dobson, Trees in graphs with large girth, manuscript, 1994.
• [27] E. Dobson, personal communication.
• [28] E. Dobson, Packing almost stars into the complete graph, to appear.
• [29] P. Erdős and T. Gallai, On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hungar. 10 (1959), 337-356.
• [30] G. Fan and H. A. Kierstead, Hamiltonian square-paths, J. Combin. Theory Ser. B 67 (1996), 167-182.
• [31] R. J. Faudree, C. C. Rousseau, R. H. Schelp and S. Schuster, Embedding graphs in their complements, Czechoslovak Math. J. 31 (106) (1981), 53-62.
• [32] P. C. Fishburn, Balanced integer arrays: a matrix packing theorem, J. Combin. Theory Ser. A 34 (1983), 98-101.
• [33] P. C. Fishburn, Packing graphs with odd and even trees, J. Graph Theory 7 (1983), 369-383.
• [34] J.-L. Fouquet and A. P. Wojda, Mutual placement of bipartite graphs, Discrete Math. 121 (1993), 85-92.
• [35] B. Ganter, J. Pelikan and L. Teirlinck, Small sprawling systems of equicardinal sets, Ars Combin. 4 (1977), 133-142.
• [36] R. A. Gibbs, Self-complementary graphs, J. Combin. Theory Ser. B 16 (1974), 106-123.
• [37] A. Gyárfás and J. Lehel, Packing trees of different order into Kₙ, in: Colloq. Math. Soc. János Bolyai 18, North-Holland, 1976, 463-469.
• [38] P. Hajnal and M. Szegedy, On packing bipartite graphs, Combinatorica 12 (3) (1992), 295-301.
• [39] A. Hajnal and E. Szemerédi, Proof of a conjecture of Erdős, in: Combinatorial Theory and Its Applications, Vol. II, P. Erdős, A. Renyi and V. T. Sós (eds.), Colloq. Math. Soc. János Bolyai 4, North-Holland, 1970, 601-623.
• [40] F. Harary, R. W. Robinson and N. C. Wormald, Isomorphic factorisations, I: Complete graphs, Trans. Amer. Math. Soc. 242 (1978), 243-260.
• [41] T. Hasunuma and Y. Shibata, Remarks on the placeability of isomorphic trees in a complete graph, J. Graph Theory 21 (1) (1996), 41-42.
• [42] S. M. Hedetniemi, S. T. Hedetniemi and P. J. Slater, A note on packing two trees into $K_N$, Ars Combin. 11 (1981), 149-153.
• [43] A. M. Hobbs, Packing trees, Congr. Numer. 33 (1981), 63-73.
• [44] A. M. Hobbs, B. A. Bourgeois and J. Kasiraj, Packing trees in complete graphs, Discrete Math. 67 (1987), 27-42.
• [45] C. Huang and A. Rosa, Decomposition of complete graphs into trees, Ars Combin. 5 (1978), 26-63.
• [46] J. Komlós, G. N. Sárközy and E. Szemerédi, Proof of a packing conjecture of Bollobás, to appear.
• [47] L. Lesniak, Independent cycles in graphs, J. Combin. Math. Combin. Comput. 17 (1995), 55-63.
• [48] M. Mahéo, J.-F. Saclé and M. Woźniak, Edge-disjoint placement of three trees, European J. Combin. 17 (1996), 543-563.
• [49] W. Moser and J. Pach, Recent developments in combinatorial geometry, in: New Trends in Discrete and Computational Geometry, Springer, 1993, 283-302.
• [50] B. Orchel, Placing bipartite graphs of small size I, Zeszyty Nauk. Politech. Rzeszowskiej Mat. Fiz. 118 (1993), 53-60.
• [51] G. Ringel, Selbstkomplementäre Graphen, Arch. Math. (Basel) 14 (1963), 354-358.
• [52] H. Sachs, Über selbstkomplementäre Graphen, Publ. Math. Debrecen 9 (1970), 270-288.
• [53] J.-F. Saclé, personal communication.
• [54] J.-F. Saclé and M. Woźniak, A note on packing of three forests, Discrete Math. 164 (1997), 265-274.
• [55] J.-F. Saclé and M. Woźniak, A note on the Erdős-Sós conjecture for graphs without C₄, Rapport de Recherche 964, L.R.I., Université de Paris-Sud, Centre d'Orsay, 1995.
• [56] J.-F. Saclé and M. Woźniak, A note on graphs which contain each tree of given size, Discrete Math. 165-166 (1997), 589-595.
• [57] N. Sauer and J. Spencer, Edge disjoint placement of graphs, J. Combin. Theory Ser. B 25 (1978), 295-302.
• [58] G. Schuster, Über Systeme von disjunkten Kreisen und Wäldern in Graphen, eine Verallgemeinerung eines Satzes von K. Corrádi und A. Hajnal, Diplom Thesis, Universität Hamburg, 1993.
• [59] S. Schuster, Fixed-point-free embeddings of graphs in their complements, Internat. J. Math. Math. Sci. 1 (1978), 335-338.
• [60] S. Schuster, Packing a tree of order p with a (p,p) graph, in: Graph Theory with Applications to Algorithms and Computer Science, Wiley, New York, 1985, 697-712.
• [61] A. F. Sidorenko, Asymptotic solution for a new class of forbidden r-graphs, Combinatorica 9 (2) (1989), 207-215.
• [62] Z. Skupień, The complete graph t-packings and t-coverings, Graphs Combin. 9 (1993), 353-363.
• [63] P. J. Slater, S. K. Teo and H. P. Yap, Packing a tree with a graph of the same size, J. Graph Theory 9 (1985), 213-216.
• [64] H. J. Straight, Packing trees of different size into the complete graph, Ann. New York Acad. Sci. 328 (1979), 190-192.
• [65] H. J. Straight, unpublished.
• [66] S. K. Teo and H. P. Yap, Packing two graphs of order n having total size at most 2n-2, Graphs Combin. 6 (1990), 197-205.
• [67] S. K. Teo and H. P. Yap, Two theorems on packing of graphs, European J. Combin. 8 (1987), 199-207.
• [68] S. Tokunaga, On a straight-line embedding problem of graphs, to appear.
• [69] H. Wang, Packing two forests into a bipartite graph, J. Graph Theory 23 (1996), 209-213.
• [70] H. Wang, Packing two bipartite graphs into a bipartite graph, to appear.
• [71] H. Wang and N. Sauer, Packing three copies of a tree into a complete graph, European J. Combin. 14 (1993), 137-142.
• [72] H. Wang and N. Sauer, Packing of three copies of a graph, J. Graph Theory 21 (1) (1996), 71-80.
• [73] A. P. Wojda, Research problems (Problem 69), Discrete Math. 57 (1985), 209-210.
• [74] A. P. Wojda and P. Vaderlind, Packing bipartite graphs, Discrete Math. 164 (1997), 303-311.
• [75] A. P. Wojda and M. Woźniak, Packing and extremal digraphs, Ars Combin. 20 B (1985), 71-73.
• [76] A. P. Wojda and I. Zioło, Embedding digraphs of small size, Discrete Math. 165-166 (1997), 621-638.
• [77] M. Woźniak, Embedding of graphs in the complements of their squares, Fourth Czechoslovakian Sympos. on Combinatorics, Graphs and Complexity, J. Nesetril and M. Fiedler (eds.), North-Holland, 1992, 345-349.
• [78] M. Woźniak, A note on embedding graphs without small cycles, in: Colloq. Math. Soc. János Bolyai 60, North-Holland, 1991, 727-732.
• [79] M. Woźniak, Embedding graphs of small size, Discrete Appl. Math. 51 (1994), 233-241.
• [80] M. Woźniak, Packing three trees, Discrete Math. 150 (1996), 393-402.
• [81] M. Woźniak, On the Erdős-Sós conjecture, J. Graph Theory 21 (2) (1996), 229-234.
• [82] M. Woźniak, A note on careful packing of a graph, Discuss. Math. Graph Theory Ser. 15 (1995), 43-50.
• [83] M. Woźniak, A note on uniquely embeddable graphs, Report de Recherche 1039, L.R.I. Université de Paris-Sud, Centre d'Orsay, 1996.
• [84] M. Woźniak and A. P. Wojda, Triple placement of graphs, Graphs Combin. 9 (1993), 85-91.
• [85] H. P. Yap, Some Topics in Graph Theory, London Math. Soc. Lecture Note Ser. 108, Cambridge Univ. Press, Cambridge, 1986.
• [86] H. P. Yap, Packing of graphs - a survey, Discrete Math. 72 (1988), 395-404.
• [87] S. Zaks and C. L. Liu, Decompositions of graphs into trees, in: Proc. 8th Southeastern Conf. on Combinatorics, Graphs and Computing, Congr. Numer. 19, Utilitas Math., Winnipeg, MB, 1977, 643-654.
• [88] B. Zhou, A note on the Erdős-Sós conjecture, Acta Math. Sci. (English Ed.) 4 (3) (1984), 287-289.
Języki publikacji
 EN
Uwagi
1991 Mathematics Subject Classification: 05C70, 05C35.