Asymptotic properties of random graphs

Palka, Zbigniew

Książka - szczegóły

Tytuł książki

Asymptotic properties of random graphs

Autorzy

Zbigniew Palka

Seria

Rozprawy Matematyczne tom/nr w serii: 275 wydano: 1988

Zawartość

Pełne teksty:

Pobierz

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

Wydawca

Instytut Matematyczny Polskiej Akademii Nauk

Miejsce publikacji

Warszawa

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

Zbigniew Palka

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

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