Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

The probability of connectedness of an unlabelled graph can be less for more edges


Author: E. M. Wright
Journal: Proc. Amer. Math. Soc. 35 (1972), 21-25
MSC: Primary 05C99
DOI: https://doi.org/10.1090/S0002-9939-1972-0295954-3
MathSciNet review: 0295954
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We write $ \beta = \beta (n,q)$ for the probability that a graph on n unlabelled nodes with q edges is connected; that is $ \beta $ is the ratio of the number of connected graphs to the total number of graphs. We write $ N = n(n - 1)/2$. For fixed n we might expect that $ \beta $ would increase with q, at least nonstrictly. On the contrary, we show that, for any given integer s, we have $ \beta (n,q + 1) < \beta (n,q)$ for $ N - n - s \leqq q \leqq N - n$ and $ n > {n_0}(s)$. We can show that $ \beta (n,q + 1) < \beta (n,q)$ for a much longer range, but this requires much more elaborate arguments.


References [Enhancements On Off] (What's this?)

  • [1] N. G. de Bruijn, Applied combinatorial mathematics, (ed. E. F. Beckenback), Wiley, New York, 1964, Chap. 5.
  • [2] P. Erdös and A. Rényi, On random graphs. I, Publ. Math. Debrecen 6 (1959), 290-297. MR 22 #10924. MR 0120167 (22:10924)
  • [3] L. Euler, Calcul de la probabilité dans le jeu de rencontre, Mem. Acad. Sci. Berlin 1753, 255-270; Opera Omnia (1) 7 (1923), 11-25.
  • [4] -, Solutio questionis curiosae ex doctrina combinationum, Mem. Acad. Sci. St. Petersbourg 3 (1811), 57-64; Opera Omnia (1) 7 (1923), 435-448.
  • [5] F. Harary, The number of linear, directed, rooted, and connected graphs, Trans. Amer. Math. Soc. 78 (1955), 445-463. MR 16, 844. MR 0068198 (16:844b)
  • [6] -, Graph theory, Addison-Wesley, Reading, Mass., 1969, pp. 214-223. MR 41 #1566. MR 0256911 (41:1566)
  • [7] W. Oberschelp, Kombinatorische Anzahlbestimmungen in Relationen, Math. Ann. 174 (1967), 53-78. MR 36 #1342. MR 0218255 (36:1342)
  • [8] G. Pólya, Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen, Acta Math. 68 (1937), 147-254.
  • [9] J. Riordan, An introduction to combinatorial analysis, Wiley Publ. in Math. Statist., Wiley, New York; Chapman and Hall, London, 1958. MR 20 #3077. MR 0096594 (20:3077)
  • [10] E. M. Wright, Asymptotic enumeration of connected graphs, Proc. Roy. Soc. Edinburgh Sect. A 68 (1968/69), 298-308. MR 42 #1723. MR 0266820 (42:1723)
  • [11] -, Graphs on unlabelled nodes with a given number of edges, Acta Math. 126 (1970), 1-9. MR 42 #2975. MR 0268076 (42:2975)
  • [12] -, Arithmetical properties of Euler's rencontre number, J. London Math. Soc. 4 (1972), 437-442.

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 05C99

Retrieve articles in all journals with MSC: 05C99


Additional Information

DOI: https://doi.org/10.1090/S0002-9939-1972-0295954-3
Keywords: Unlabelled graphs, probability of connectedness
Article copyright: © Copyright 1972 American Mathematical Society

American Mathematical Society