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

Asymptotic properties of random graphs

Seria
Rozprawy Matematyczne tom/nr w serii: 275 wydano: 1988
Zawartość
Warianty tytułu
Abstrakty
EN

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
  • 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
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ć.