Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Cover of the book
Tytuł książki

Packing of graphs

Seria
Rozprawy Matematyczne tom/nr w serii: 362 wydano: 1997
Zawartość
Warianty tytułu
Abstrakty
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
Miejsce publikacji
Warszawa
Copyright
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
  • Instytut Matematyki, Akademia Górniczo-Hutnicza, Al. Mickiewicza 30, 30-059 Kraków, Poland
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.
Identyfikator YADDA
bwmeta1.element.zamlynska-b3a7d237-fb32-41fe-a7ec-fd4f3663ca9e
Identyfikatory
ISSN
0012-3862
Kolekcja
DML-PL
Zawartość książki

rozwiń roczniki

JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.