Zawartość
Pełne teksty:
Warianty tytułu
Abstrakty
CONTENTS
1. Introduction...........................................................................5
1.1. Purpose and scope..........................................................5
1.2. Probability-theoretic preliminaries....................................6
1.3. Graphs............................................................................11
1.4. Random graphs..............................................................13
2. Vertex-degrees....................................................................15
2.1. A general approach........................................................15
2.2. Model K(n,p)...................................................................18
2.3. Extreme degrees and global properties of K(n,p)...........42
2.4. Other models..................................................................48
3. Induced subgraphs..............................................................68
3.1. Greedy algorithm............................................................68
3.2. Complete subgraphs......................................................71
3.3. Bipartite complete subgraphs.........................................80
3.4. Trees..............................................................................86
References............................................................................102
Symbols.................................................................................105
Appendix: Updated notes.......................................................106
Słowa kluczowe
Tematy
Miejsce publikacji
Warszawa
Copyright
Seria
Rozprawy Matematyczne
tom/nr w serii:
275
Liczba stron
109
Liczba rozdzia³ów
Opis fizyczny
Dissertationes Mathematicae, Tom CCLXXV
Daty
wydano
1988
Twórcy
autor
- Institute of Mathematics, Adam Mickiewicz University, Matejki 48/49, Poznań, Poland
Bibliografia
- [1] M. Ajtai, J. Komlós, E. Szemerédi, Topological complete subgraphs in random graphs, Studia Scien. Math. Hungar. 14 (1979), 293-297.
- [2] B. Bollobás, Graph Theory, An Introductory Course, Graduate Texts in Math., Vol. 63, Springer-Verlag, Berlin 1979.
- [3] B. Bollobás, The distribution of the maximum degree of a random graph, Discrete Math. 32 (1980), 201-203.
- [4] B. Bollobás, Degree sequences of random graphs, Discrete Math. 33 (1981), 1-19.
- [5] B. Bollobás, Random graphs, Combinatorics, London Math. Soc. Lectures Notes 52, London 1981, 80-102.
- [6] B. Bollobás, Counting coloured graphs of high connectivity, Canadian J. Math, 33 (1981), 476-484.
- [7] B. Bollobás, Vertices of given degree in a random graph, J. Graph Theory 6 (1982), 147-155.
- [8] B. Bollobás, Random Graphs, Academic Press, London 1985.
- [9] B. Bollobás, P. Catlin, Topological cliques of random graphs, J. Comb. Theory B. 30 224-227.
- [10] B. Bollobás, P. Erdös, Cliques in random graphs, Math. Proc. Cambridge Phil. Soc. 80 (1976), 419-427.
- [11] B, Bollobás, T. Fenner, A. Frieze, An algorithm for finding Hamilton paths and cycles in random graphs, Combinatorica 7 (1987), 327-341.
- [12] B. Bollobás, A. Frieze, On matchings and hamiltonian cycles in random graphs, Annals Disc. Math. 28 (1985), 23-46.
- [13] B. Bollobás, A. Thomason, Random graphs of small order, Annals Disc. Math. 28 (1985), 49-97.
- [14] Yu. Burtin, Asymptotic estimates of the diameter, independence and dominance numbers of a random graph, Sov. Math. Dokl. 14 (1973), 497-501.
- [15] Yu. Burtin, On probability of connectivity of a random subgraph of n-dimensional cube, Problems of Inform. Transm. 13 (1977), 90-95.
- [16] M. Capobianco, Z. Palka, The distribution of popular persons in a group, Social Networks 5 (1983), 383-393.
- [17] Y. Chow, H. Teicher, Probability Theory, Springer-Verlag, New York 1978.
- [18] G. Cornuéjols, Degree sequences of random graphs - submitted.
- [19] P. Erdös, Z. Palka, Trees in random graphs, Discrete Math. 46 (1983), 145-150; Addendum: Ibid. 48 (1984), 331.
- [20] P. Erdös, A. Rényi, On the evolution of random graphs, Publ. Math. Inst. Hungar. Acad. Sci. 5 (1960), 17-61.
- [21] P. Erdös, A. Rényi, On the strength of connectedness of a random graph. Acta Math. Acad. Sci. Hungar. 12 (1961), 261-267.
- [22] P. Erdös, A. Rényi, Asymmetric graphs, Acta Math. Acad. Sci. Hungar. 14 (1963), 295-315.
- [23] P. Erdös, A. Rényi,, On the existence of a factor of degree one of a connected random graph, Acta Math. Acad. Sci. Hungar. 17 (1966), 359-368.
- [25] P. Erdös, J. Spencer, Evolution of the n-cube, Comp. and Math, with Appl, 5 (1979), 33-39.
- [26] P. Erdös, R. Wilson, On the chromatic index of almost all graphs, J. Comb. Theory B, 23 (1977), 255-257.
- [27] W. Fernandez de la Vega, On the bandwidth of random graphs, Annals Disc. Math. 17 (1983), 633-638.
- [28] W. Fernandez de la Vega, On the chromatic number of sparse random graphs, in Graph Theory and Combinatorics, B. Bollobás (ed.), Academic Press. 1984. 321-328.
- [29] W. Fernandez de la Vega, Random graphs almost optimaly colorable in polynomial time, Annals Disc. Math. 28 (1985) 311-317.
- [30] W. Fernandez de la Vega, Induced trees in sparse random graphs, Graphs and Combinations 2 (1986), 227-231.
- [31] A. Frieze, Partitioning random graphs into large cycles - submitted.
- [32] A. Frieze, B. Jackson, Large induced trees in sparse random graphs, J. Comb. Theory B 42 (1987), 181-195.
- [331 A. Frieze, Large holes in sparse random graphs, Combinatorica 7 (1987), 265-274.
- [34] P. Gazmuri, Independent sets in random sparse graphs, Networks 14 (1984), 367-377.
- [35] A. Gibbons, O. Ogunyode, A polynomial-time algorithm to edge-colour almost all graphs using $Ψ_e$ colours - submitted.
- [36] G. Grimmett, Random graphs, in Graph Theory, vol. 2, Academic Press, New York 1983, 201 235.
- [37] G. Grimmett, C. McDiarmid, On colouring random graphs. Math. Proc. Cambridge Phil. Soc. 77 (1975), 313-324.
- [38] E. Hakimullin, On the valencies of degrees in a random graph, Probabilistic Processes 282, 136 140, Kuban 1979.
- [39] G. Ivchenko, On the asymptotic behaviour of degrees of vertices in a random graph, Th. Prob. and Appl. 18 (1973), 188-195.
- [40] G. Ivchenko, The strength of connectivity of a random graph, Th. Prob. and Appl. 18 (1973), 396-403.
- [41] J. Jaworski, Z. Palka, Cliques in a social group - submitted.
- [42] J. Kalbfleisch, Complete subgraphs of random hypergraphs and bipartite graphs, in Proc. 3rd Southeastern Conf. on Combinatorics, Graph Theory and Computing, Boca Raton, 1972, 297-304.
- [43] M. Karoński, A review of random graphs, J. Graph Theory 6 (1982), 349-390.
- [44] M. Karoński, Balanced Subgraphs of Large Random Graphs, UAM Poznań, Poznań 1984.
- [45] M. Karoński, Z. Palka, On the size of a maximal induced tree in a random graph. Math. Slovaca 30 (1980), 151-155; Addendum and erratum: Ibid. 31 (1981), 107-108.
- [46] M. Karoński, A. Ruciński, Poisson convergence and semiinduced properties of random graphs, Math. Proc. Cambridge Phil. Soc. 101 (1987), 291-300.
- [47] V. Klee, D. Larman, E. Wright, The proportion of labelled bipartite graphs which are connected, J. London Math. Soc. (2) 24 (1981), 397-404.
- [48] J. Komlós, E. Szemerédi, Limit distribution for the existence of hamiltonian cycles in a random graph. Discrete Math. 43 (1983), 55-63.
- [49] W. Korodecki, personal communication.
- [50] A. Korshunov, A new version of the solution of a problem of Erdös and Rényi on hamiltonian cycles in undirected graphs, Annals Disc. Math. 28 (1985), 171-180.
- [51] Y. Kuang, C. McDiarmid, On the bandwidth of a random graph, Ars Combinatorica A 20 (1985), 29-36.
- [52] L. Kučera, V. Rödl, Large trees in random graphs, Comment. Math. Univ. Carolin. 28 (1987), 7 14.
- [53] J. Littlewood, On the probability in the tail of the binomial distribution, Advances in Appl. Prob. 1 (1969), 43-72.
- [54] T. Łuczak, Z. Palka, Maximal induced trees in sparse random graphs, Discrete Math. - in press.
- [55] A. Marchetti-Spaccamela, M. Protasi, The largest tree in a random graph, Th. Computer Sci. 23 (1983), 273-286.
- [56] D. Matula, On the complete subgraphs of a random graph, Comb. Math. and Appl. Chapel Hill, N. C, 1970, 356-369.
- [57] D. Matula, The largest clique size in a random graph, Tech. Report CS-7608, Southern Methodist Univ., Dallas.
- [58] D. Matula, Expose-and-merge exploration and the chromatic number of a random graph, Combinatorica 7 (1987), 275-284.
- [59] N. Nurmeev, On the vertex-degrees of almost all graphs, Probabilistic Methods and Kibernetica 16, Kazan 1980, 83-90.
- [60] Z. Palka, On pendant vertices in random graphs, Colloq. Math. 45 (1981), 159-167.
- [61] Z. Palka, On the number of vertices of given degree in a random graph, J. Graph Theory 8 (1984), 167-170.
- [62] Z. Palka, On the degrees of vertices in a bichromatic random graph, Periodica Math. Hungar. 15 (1984), 121 126.
- [63] Z. Palka, Extreme degrees in a random subgraph of a regular graph, Math. Proc. Cambridge Phil. Soc. 97 (1985), 69-78.
- [64] Z. Palka, Bipartite complete induced subgraphs of a random graph, Annals Disc. Math. 28 (1985), 209-219.
- [65] Z. Palka, Some remarks about extreme degrees in a random graph, Math. Proc. Cambridge Phil. Soc. 100 (1986), 167-174.
- [66] Z. Palka, Extreme degrees in random graphs, J. Graph Theory, II (1987), 121 134.
- [67] Z. Palka, Rulers and slaves in a random social group, Graphs and Combinatorics 2 (1986), 165-172.
- [68] Z. Palka, L. Quintas, Random subgraphs of the n-cycle. Discrete Math. 52 (1984), 243-251.
- [69] Z. Palka, A. Ruciński, On the order of the largest induced tree in a random graph, Discrete Appl. Math. 15 (1986), 75-83.
- [70] Z. Palka, A. Ruciński, Vertex-degrees in a random subgraph of a regular graph - submitted.
- [71] Z. Palka, A. Ruciński, J. Spencer, On a method for random graphs, Discrete Math. 61 (1986), 253-258.
- [72] E. Palmer, Graphical Evolution, An Introduction to the Theory of Random Graphs, New York 1985.
- [73] A. Rényi, Probability Theory, Akademiai Kiado, Budapest 1970.
- [74] A. Ruciński, The r-connectedness of k-partite random graph. Bull. Acad. Polon. Sci. Ser. Sci. Math. 29 (1981), 321-330.
- [75] A. Ruciński, Induced subgraphs of a random graph. Annals Disc. Math. 33 (1987), 275-296.
- [76] E. Shamir, J. Spencer, Sharp concentration of the chromatic number of random graphs Gn , Combinatories 7 (1987), 121 129.
- [77] E. Shamir, E. Upfal, On factors in random graphs, Israel J. Math. 39 (1981), 296-302.
- [78] E. Shamir, E. Upfal, Sequential and distributed graph coloring algorithms with performance analysis in random graph spaces, J. of Algorithms 5 (1984), 488-501.
- [79] E. Shamir, E. Upfal, Large regular factors in random graphs, North-Holland Math. Stud. 87 (1984), 271-282.
- [8O] K. Weber, C. Kaiser, Degrees and domination number of random graphs in the n-cube, Rostock. Math. Kolloq. 28 (1985), 18-32.
- [81] W. Wright, Asymmetric and symmetric graphs, Glasgow Math. J. 15 (1974), 69-73.
- [A 1] A. Barbour, M. Karoński, A. Ruciński, A central limit theorem for decomposable random variables with applications to random graphs, J. Comb. Th. - in press.
- [A 2] B. Bollobás, The chromatic number of random graphs, Combinatorica - in press.
- [A3] A. Frieze, On the independence number of random graphs - submitted.
- [A4] W. Kordecki, Normal approximation and isolated vertices in random graphs, in Proc. Random Graphs '87 - in press.
- [A 5] T. Łuczak, The chromatic number of random graphs - submitted.
- [A 6] T. Łuczak, The size of the largest hole in random graphs - submitted.
- [A 7] T. Łuczak, The automorphism group of random graphs with a given number of edges - submitted.
- [A 8] T. Łuczak, On k-leaf connectivity of a random graph, J. Graph Th. 12 (1988), 1-10.
- [A 9] C. Stein, A bound for the error in the normal approximation to the distribution of a sum of dependent random variables, in Proc. VIth Berk. Symp. Math. Stat. Prob. 2 (1970), 583-602.
Języki publikacji
FR |
Uwagi
Identyfikator YADDA
bwmeta1.element.zamlynska-cffd2ad6-9a68-409c-869f-c9a71fbb44f5
Identyfikatory
ISBN
83-01-08821-4
ISSN
0012-3862
Kolekcja
DML-PL
