Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
Hostname: page-component-cd9895bd7-dk4vv Total loading time: 0 Render date: 2024-12-25T01:42:36.618Z Has data issue: false hasContentIssue false

References

Published online by Cambridge University Press:  02 March 2023

Alan Frieze  and
Michał Karoński
Alan Frieze
Affiliation:
Carnegie Mellon University, Pennsylvania
Michał Karoński
Affiliation:
Adam Mickiewicz University, Poznań, Poland
Get access

Summary

A summary is not available for this content so a preview has been provided. Please use the Get access link above for information on how to access this content.
Image of the first page of this content. For PDF version, please use the ‘Save PDF’ preceeding this image.'
Type
Chapter
Information
Random Graphs and Networks: A First Course , pp. 210 - 215
Publisher: Cambridge University Press
Print publication year: 2023

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Abdullah, M. and Fountoulakis, N., A phase transition on the evolution of bootstrap percolation processes on preferential attachment graphs, Random Structures and Algorithms, 52(2018) 379–418.Google Scholar
Aiello, W., Bonato, W., Cooper, C., Janssen, J. and Prałat, P., A spatial web graph model with local influence regions, Internet Mathematics, 5(2009) 175–196.Google Scholar
Ajtai, M., Komlós, J. and Szemerédi, E., The longest path in a random graph, Combinatorica, 1(1981) 1–12.Google Scholar
Ajtai, M., Komlós, J. and Szemerédi, E., The first occurrence of Hamilton cycles in random graphs, Annals of Discrete Mathematics, 27(1985) 173–178.Google Scholar
Aldous, D., Asymptotics in the random assignment problem, Probability Theory and Related Fields, 93(1992) 507–534.Google Scholar
Aldous, D., The ζ (2) limit in the random assignment problem, Random Structures and Algorithms, 4(2001) 381–418.Google Scholar
Alon, N., A note on network reliability. In Discrete Probability and Algorithms (Minneapolis, MN, 1993), The IMA Volumes in Mathematics and Its Applications, Vol. 72, Springer (1995) 11–14.Google Scholar
Alon, N. and Füredi, Z., Spanning subgraphs of random graphs, Graphs and Combinatorics, 8(1992) 91–94.CrossRefGoogle Scholar
Babai, L., Erdős, P. and Selkow, S. M., Random graph isomorphism, SIAM Journal on Computing, 9(1980) 628–635.Google Scholar
Bal, D., Bennett, P., Dudek, A. and Frieze, A. M., The t-tone chromatic number of random graphs, Graphs and Combinatorics, 30(2014) 1073–1086.Google Scholar
Ball, F., Mollison, D. and Scalia-Tomba, G., Epidemics with two levels of mixing, Annals of Applied Probability, 7(1997) 46–89.Google Scholar
Balogh, J., Bollobás, B., Krivelevich, M., Müeller, T. and Walters, M., Hamilton cycles in random geometric graphs, Annals of Applied Probability, 21(2011) 1053–1072.Google Scholar
Barabási, L. and Albert, R., Emergence of scaling in random networks, Science, 286(1999) 509–512.Google Scholar
Barbour, A. D., Karoński, M. and Ruciński, A., A central limit theorem for decomposable random variables with applications to random graphs, Journal of Combinatorial Theory B, 47(1989) 125–145.Google Scholar
Barbour, A. D. and Reinert, G., Small worlds, Random Structures and Algorithms, 19 (2001) 54–74.Google Scholar
Barbour, A. D. and Reinert, G., Discrete smallworld networks, Electronic Journal on Probability, 11(2006) 1234–1283.Google Scholar
Bernstein, S. N., Theory of Probability, (in Russian), Gostekhizdat (1927).Google Scholar
Bollobás, B., A probabilistic proof of an asymptotic formula for the number of labelled graphs, European Journal on Combinatorics, 1(1980) 311–316.Google Scholar
Bollobás, B., Random graphs. In Combinatorics, Proceedings, Swansea, London Mathematical Society Lecture Note Series, Vol. 52, Cambridge University Press (1981) 80–102.CrossRefGoogle Scholar
Bollobás, B., The evolution of random graphs, Transactions of the American Mathematical Society, 286(1984) 257–274.CrossRefGoogle Scholar
Bollobás, B., Random Graphs, First edition, Academic Press (1985); Second edition, Cambridge University Press (2001).Google Scholar
Bollobás, B., The chromatic number of random graphs, Combinatorica, 8(1988) 49–56.Google Scholar
Bollobás, B. and Chung, F., The diameter of a cycle plus a random matching, SIAM Journal on Discrete Mathematics, 1(1988) 328–333.Google Scholar
Bollobás, B. and Erdős, P., Cliques in random graphs, Mathematical Proceedings of the Cambridge Philosophical Society, 80(1976) 419–427.Google Scholar
Bollobás, B. and Frieze, A., On matchings and Hamiltonian cycles in random graphs, Annals of Discrete Mathematics, 28(1985) 23–46.Google Scholar
Bollobás, B. and Frieze, A., Spanning maximal planar subgraphs of random graphs, Random Structures and Algorithms, 2(1991) 225–231.CrossRefGoogle Scholar
Bollobás, B. and Riordan, O., The diameter of a scale free random graph, Combinatorica, 24(2004) 5–34.Google Scholar
Bollobás, B., Riordan, O., Spencer, J. and Tusnády, G., The degree sequence of a scale-free random graph process, Random Structures and Algorithms, 18(2001) 279–290.Google Scholar
Bollobás, B. and Thomason, A., Threshold functions, Combinatorica, 7(1987) 35–38.Google Scholar
Chung, F. and Lu, L., Connected components in random graphs with given expected degree sequence, Annals of Combinatorics, 6(2002) 125–145.Google Scholar
Chung, F. and Lu, L., The volume of the giant component of a random graph with given expected degrees, SIAM Journal on Discrete Mathematics, 20(2006) 395–411.CrossRefGoogle Scholar
Chung, F. and Lu, L., Complex Graphs and Networks, American Mathematical Society (2006).Google Scholar
Cont, R. and Tanimura, E., Small-world graphs: characterizations and alternative constructions, Advances in Applied Probability, 20(2008) 939–965.Google Scholar
Cooper, C., Pancyclic Hamilton cycles in random graphs, Discrete Mathematics, 91(1991) 141–148.CrossRefGoogle Scholar
Cooper, C., 1-pancyclic Hamilton cycles in random graphs, Random Structures and Algorithms, 3(1992) 277–287.CrossRefGoogle Scholar
Cooper, C. and Frieze, A. M., Pancyclic random graphs. In Random Graphs, Karonski, M., Javorski, J., and Rucinski, A. (eds). John Wiley and Sons (1990) 29–39.Google Scholar
Cooper, C., Frieze, A. and Prałat., P. Some typical properties of the spatial preferred attachment model, Internet Mathematics, 10(2014) 27–47.Google Scholar
Díaz, J., Mitsche, D. and Pérez-Giménez, X., Sharp threshold for hamiltonicity of random geometric graphs, SIAM Journal on Discrete Mathematics, 21(2007) 57–65.Google Scholar
Dudek, A., Mitsche, D. and Prałat, P., The set chromatic number of random graphs, Discrete Applied Mathematics, 215(2016) 61–70.Google Scholar
Dudek, A. and Prałat, P., An alternative proof of the linearity of the size-Ramsey number of paths, Combinatorics, Probability and Computing, 24(2015) 551–555.Google Scholar
Durrett, R., Random Graph Dynamics, Cambridge University Press (2010).Google Scholar
Erdős, P. and Rényi, A., On random graphs I, Publicationes Mathematicae Debrecen, 6 (1959) 290–297.Google Scholar
Erdős, P. and Rényi, A., On the evolution of random graphs, Publication of the Mathematical Institute of the Hungarian Academy of Sciences, 5(1960) 17–61.Google Scholar
Erdős, P. and Rényi, A., On the strength of connectedness of a random graph, Acta Mathematica Academiae Scientiarum Hungaricae, 8(1961) 261–267.Google Scholar
Erdős, P. and Rényi, A., On random matrices, Publication of the Mathematical Institute of the Hungarian Academy of Sciences, 8(1964) 455–461.Google Scholar
Erdős, P. and Rényi, A., On the existence of a factor of degree one of a connected random graph, Acta mathematica Academiae Scientiarum Hungaricae, 17(1966) 359–368.Google Scholar
Faloutsos, M., Faloutsos, P. and Faloutsos, C., On power-law relationships of the internet topology, ACM SIGCOMM (1999).Google Scholar
Fill, J. A., Scheinerman, E. R. and Singer-Cohen, K. B., Random intersection graphs when m = ω(n): An equivalence theorem relating the evolution the evolution of the G(n, m, p) and G(n,p) models, Random Structures and Algorithms, 16(2000) 156–176.3.0.CO;2-H>CrossRefGoogle Scholar
Flaxman, A., Frieze, A. M. and Fenner, T., High degree vertices and eigenvalues in the preferential attachment graph, Internet Mathematics, 2(2005) 1–20.Google Scholar
Frieze, A. M., On the value of a random minimum spanning tree problem, Discrete Applied Mathematics, 10(1985) 47–56.CrossRefGoogle Scholar
Frieze, A. M., On the independence number of random graphs, Discrete Mathematics, 81 (1990) 171–176.Google Scholar
Frieze, A. M. and Karoński, M., Introduction to Random Graphs, Cambridge University Press (2016).Google Scholar
Frieze, A. M. and H. McDiarmid, C. J., On random minimum length spanning trees, Combinatorica, 9(1989) 363–374.Google Scholar
Gilbert, E. N., Random graphs, Annals of Mathematical Statistics, 30(1959) 1141–1144.Google Scholar
Grimmett, G. and McDiarmid, C., On colouring random graphs, Mathematical Proceedings of the Cambridge Philosophical Society, 77(1975) 313–324.Google Scholar
Gu, L. and Huang, L. H., The clustering coefficient and the diameter of small-world networks, Acta Mathematica Sinica, English Series, 29(2013) 199–208.Google Scholar
Gupta, P. and Kumar, P. R., Critical power for asymptotic connectivity in wireless networks. In Stochastic Analysis, Control, Optimization and Applications: A Volume in Honor of W. H. Fleming, McEneany, W. M., Yin, G. and Zhang, Q. (eds). Birkhauser (1998) 547–566.Google Scholar
Győri, E., Rothschild, B. and Ruciński, A., Every graph is contained in a sparest possible balanced graph, Mathematical Proceedings of the Cambridge Philosophical Society, 98(1985) 397–401.Google Scholar
Hoeffding, W., Probability inequalities for sums of bounded random variables, Journal of the American Statistical Association, 58(1963) 13–30.CrossRefGoogle Scholar
van der Hofstad, R., Random Graphs and Complex Networks, Vol. 1, Cambridge University Press, 2017.Google Scholar
Janssen, J., Prałat, P. and Wilson, R., Geometric graph properties of the spatial preferred attachment model, Advances in Applied Mathematics, 50(2013) 243–267.Google Scholar
Janson, S., The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph, Random Structures and Algorithms, 7(1995) 337–355.Google Scholar
Janson, S., One, two and three times log n/n for paths in a complete graph with random weights, Combinatorics, Probability and Computing, 8(1999) 347–361.CrossRefGoogle Scholar
Janson, S., Asymptotic degree distribution in random recursive trees, Random Structures and Algorithms, 26(2005) 69–83.Google Scholar
Janson, S., Plane recursive trees, Stirling permutations and an urn model. In Fifth Colloquium on Mathematics and Computer Science, Discrete Math. Theor. Comput. Sci. Proc., AI, Discrete Mathematics and Theoretical Computer Science, (2008) 541–547.Google Scholar
Janson, S., Łuczak, T. and Ruciński, A., Random Graphs, John Wiley and Sons (2000).Google Scholar
Karger, D. and Stein, C., A new approach to the minimum cut problem, Journal of the ACM, 43(1996) 601–640.Google Scholar
Karoński, M., Scheinerman, E. and Singer-Cohen, K., On random intersection graphs: the subgraph problem, Combinatorics, Probability and Computing, 8(1999) 131–159.Google Scholar
Karoński, M. and Ruciński, A., On the number of strictly balanced subgraphs of a random graph, In Graph Theory, Proc. Łagów, 1981, Lecture Notes in Mathematics 1018, Springer (1983) 79–83.Google Scholar
Karoński, M. and Ruciński, A., Problem 4, In Graphs and other Combinatorial Topics, Proceedings, Third Czech. Symposium on Graph Theory, Prague (1983).Google Scholar
Karoński, M. and Ruciński, A., Poisson convergence and semi-induced properties of random graphs, Mathematical Proceedings of the Cambridge Philosophical Society, 101(1987) 291–300.Google Scholar
Kleinberg, J., The small-world phenomenon: An algorithmic perspective, Proceedings of the 32nd ACM Symposium on Theory of Computing (2000) 163–170.Google Scholar
Komlós, J. and Szemerédi, E., Limit distributions for the existence of Hamilton circuits in a random graph, Discrete Mathematics, 43(1983) 55–63.Google Scholar
Kordecki, W., Normal approximation and isolated vertices in random graphs, In Random Graphs ’87, Karoński, M., Jaworski, J. and Ruciński, A. (eds). John Wiley and Sons (1990) 131–139.Google Scholar
Kovalenko, I. N., Theory of random graphs, Cybernetics and Systems Analysis, 7(1971) 575–579.Google Scholar
Krivelevich, M., Lee, C. and Sudakov, B., Long paths and cycles in random subgraphs of graphs with large minimum degree, Random Structures and Algorithms, 46(2015) 320–345.Google Scholar
Krivelevich, M. and Sudakov, B., The phase transition in random graphs – a simple proof, Random Structures and Algorithms, 43(2013) 131–138.Google Scholar
Linusson, S. and Wästlund, J., A proof of Parisi’s conjecture on the random assignment problem, Probability Theory and Related Fields, 128(2004) 419–440.Google Scholar
Łuczak, T., On the equivalence of two basic models of random graphs, In Proceedings of Random Graphs ’87, Karonski, M., Jaworski, J., and Rucinski, A. (eds). John Wiley and Sons (1990) 151–158.Google Scholar
Łuczak, T., Component behaviour near the critical point, Random Structures and Algorithms, 1(1990) 287–310.Google Scholar
Łuczak, T., On the number of sparse connected graphs, Random Structures and Algorithms, 1 (1990) 171–174.Google Scholar
Łuczak, T., Cycles in a random graph near the critical point, Random Structures and Algorithms, 2(1991) 421–440.Google Scholar
Łuczak, T., The chromatic number of random graphs, Combinatorica, 11(1991) 45–54.Google Scholar
Marczewski, E., Sur deux propriétés des classes d’ensembles, Fundamenta Mathematicae, 33 (1945) 303–307.Google Scholar
Matula, D., The largest clique size in a random graph, Technical Report, Department of Computer Science, Southern Methodist University, (1976).Google Scholar
Matula, D., Expose-and-merge exploration and the chromatic number of a random graph, Combinatorica, 7(1987) 275–284.Google Scholar
McDiarmid, C., Random channel assignment in the plane, Random Structures and Algorithms, 22(2003) 187–212.Google Scholar
McDiarmid, C. and Reed, B., Colouring proximity graphs in the plane, Discrete Mathematics, 199(1999) 123–137.Google Scholar
Milgram, S., The Small World Problem, Psychology Today, 2(1967) 60–67.Google Scholar
Molloy, M. and Reed, B., The Size of the Largest Component of a random graph on a fixed degree sequence, Combinatorics, Probability and Computing, 7(1998) 295–306.Google Scholar
Müller, T., Pérez, X. and Wormald, N., Disjoint Hamilton cycles in the random geometric graph, Journal of Graph Theory, 68(2011) 299–322.Google Scholar
Müller, T., Private communication.Google Scholar
Nachmias, A. and Peres, Y., The critical random graph, with martingales, Israel Journal of Mathematics, 176(2010) 29–41.CrossRefGoogle Scholar
Nair, C., Prabhakar, B. and Sharma, M., Proofs of the Parisi and Coppersmith–Sorkin random assignment conjectures, Random Structures and Algorithms, 27(2005) 413–444.Google Scholar
Newman, M., Networks, Second Edition, Oxford University Press, 2018.Google Scholar
Newman, M. E. J. and Watts, D. J., Scaling and percolation in the small-world network model, Physical Review E, 60(1999) 7332–7342.Google Scholar
Palmer, E. and Spencer, J., Hitting time for k edge disjoint spanning trees in a random graph, Periodica Mathematica Hungarica, 91(1995) 151–156.Google Scholar
Parisi, G., A conjecture on Random Bipartite Matching, Physics e-Print archive (1998).Google Scholar
Penrose, M., On k-connectivity for a geometric random graph, Random Structures and Algorithms, 15(1999) 145–164.Google Scholar
Penrose, M., Random Geometric Graphs, Oxford University Press, 2003.Google Scholar
Pósa, L., Hamiltonian circuits in random graphs, Discrete Mathematics, 14(1976) 359–364.Google Scholar
Ruciński, A., When a small subgraphs of a random graph are normally distributed, Probability Theory and Related Fields, 78(1988) 1–10.Google Scholar
Ruciński, A. and Vince, A., Strongly balanced graphs and random graphs, Journal of Graph Theory, 10(1986) 251–264.Google Scholar
Rybarczyk, K., Equivalence of the random intersection graph and G (n, p), Random Structures and Algorithms, 38(2011) 205–234.Google Scholar
Rybarczyk, K. and Stark, D., Poisson approximation of the number of cliques in a random intersection graph, Journal of Applied Probability, 47(2010) 826–840.Google Scholar
Sudakov, B. and Vu, V., Local resilience of graphs, Random Structures and Algorithms, 33 (2008) 409–433.Google Scholar
Scott, A., On the concentration of the chromatic number of random graphs (2008), arxiv 0806.0178Google Scholar
Spencer, J. with Florescu, L., Asymptotia, American Mathemetical Society, 2010.Google Scholar
Steele, J. M., On Frieze’s ζ (3) limit for lengths of minimal spanning trees, Discrete Applied Mathematics, 18(1987) 99–103.Google Scholar
Turán, P., On an extremal problem in graph theory (in Hungarian), Matematikai és Fizikai Lapok, 48(1941) 436–452.Google Scholar
de la Vega, W. F., Long paths in random graphs, Studia Scientiarum Mathematicarum Hungarica, 14(1979) 335–340.Google Scholar
Wástlund, J., An easy proof of the ζ (2) limit in the random assignment problem, Electronic Communications in Probability, 14(2009) 261–269.Google Scholar
Watts, D. J. and Strogatz, S. H., Collective dynamics of “small-world” networks, Nature, 393(1998) 440–442.Google Scholar
West, D., Introduction to Graph Theory, Second edition, Prentice Hall 2001.Google Scholar
Wormald, N., Models of random regular graphs, In Surveys in Combinatorics 1999, Lamb, J. and Preece, D. (eds). London Mathematical Society Lecture Note Series (1999) 239–298, Cambridge University Press.Google Scholar

Save book to Kindle

To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service.

  • References
  • Alan Frieze, Carnegie Mellon University, Pennsylvania, Michał Karoński, Adam Mickiewicz University, Poznań, Poland
  • Book: Random Graphs and Networks: A First Course
  • Online publication: 02 March 2023
  • Chapter DOI: https://doi.org/10.1017/9781009260268.019
Available formats
×

Save book to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

  • References
  • Alan Frieze, Carnegie Mellon University, Pennsylvania, Michał Karoński, Adam Mickiewicz University, Poznań, Poland
  • Book: Random Graphs and Networks: A First Course
  • Online publication: 02 March 2023
  • Chapter DOI: https://doi.org/10.1017/9781009260268.019
Available formats
×

Save book to Google Drive

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

  • References
  • Alan Frieze, Carnegie Mellon University, Pennsylvania, Michał Karoński, Adam Mickiewicz University, Poznań, Poland
  • Book: Random Graphs and Networks: A First Course
  • Online publication: 02 March 2023
  • Chapter DOI: https://doi.org/10.1017/9781009260268.019
Available formats
×