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
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?)

Similar Articles

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

Retrieve articles in all journals with MSC: 05C99

Additional Information

Keywords: Unlabelled graphs, probability of connectedness
Article copyright: © Copyright 1972 American Mathematical Society

American Mathematical Society