Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-25T19:29:13.509Z Has data issue: false hasContentIssue false
  • English
  • Français

Enumeration of smooth labelled graphs

Published online by Cambridge University Press:  14 November 2011

E. M. Wright
E. M. Wright
Affiliation:
Mathematics Department, University of Aberdeen
Get access Rights & Permissions [Opens in a new window]

Synopsis

An (n, q) graph is a graph on n labelled points and q lines without loops or multiple lines. We write ν(n, q) for the number of smooth (n, q) graphs, i.e. connected graphs without end points, and ν = V(Z, Y) = ∑n,q ν(n,q)ZnYq /n! for the exponential generating function of ν(n,q). We use the Riddell “core and mantle” method to find an explicit form for V (not, as usual with this method, only a functional equation). From this we deduce a partial differential equation satisfied by V. We interpret this equation in purely combinatorial terms. We write Vk = ∑ n ν(n, n + k)Xn/n! and find a recurrence formula for Vk for successive k. We use these and other results to find an asymptotic expansion for ν(n,q) as n→∞ when (q/n) − log n − log log n→ + ∞ and an asymptotic approximation to ν(n,n + k) when 0 < k = o and to log ν(n, n + k) when k < (1−ε).

Type
Research Article
Information
Proceedings of the Royal Society of Edinburgh Section A: Mathematics , Volume 91 , Issue 3-4 , 1982 , pp. 205 - 212
Copyright
Copyright © Royal Society of Edinburgh 1982

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

1Erdös, P. and Rényi, A.. On random graphs I. Publ. Math. Debrecen 6(1959), 290–297.Google Scholar
2Erdös, P. and Rényi, A.. On the strength of connectedness of a random graph. Ada Math. Acad. Sci. Hungar. 12 (1961), 261–267.Google Scholar
3Ford, G. W. and Uhlenbeck, G. E.. Combinatorial problems in the theory of graphs I. Proc. Nat. Acad. Sci. U.S.A. 42 (1956), 122–128.CrossRefGoogle Scholar
4Gilbert, E. N.. Enumeration of labelled graphs. Canad. J. Math. 8 (1956), 405–411.Google Scholar
5Gray, P. M. D., Murray, A. M. and Young, N. A.. Wright's formulae for the number of connected sparsely edged graphs. J. Graph Theory 1 (1977), 331–334.CrossRefGoogle Scholar
6Harary, F. and Palmer, E.. Graphical Enumeration, 10–11 (New York: Academic Press, 1973).Google Scholar
7Hurwitz, A. and Courant, R.. Funktionentheorie, 3rd edn, 141–142 (Berlin: Springer, 1929).Google Scholar
8Read, R. C.. Some unusual enumeration problems. Ann. New York Acad. Sci. 175 (1970), 314–326.Google Scholar
9Riddell, R. J.. Contributions to the theory of condensation (Dissertation, Univ. of Michigan, Ann Arbor, 1951).Google Scholar
10S, T. R.. Walsh. Counting labelled three-connected and homeomorphically irreducible twoconnected graphs. Graph Theory Newsletter 7 (1978), no. 3, 3.Google Scholar
11Wright, E. M.. Asymptotic enumeration of connected graphs. Proc. Roy. Soc. Edinburgh Sect. A 68 (1970), 298–308.Google Scholar
12Wright, E. M.. The number of connected sparsely edged graphs. J. Graph Theory 1 (1977), 317–330.Google Scholar
13Wright, E. M.. The number of connected sparsely edged graphs II, Smooth graphs and blocks. J. Graph Theory 2 (1978), 299–305.Google Scholar
14Wright, E. M.. The number of connected sparsely edged graphs III, Asymptotic results. J. Graph Theory 4 (1980), 393–407.CrossRefGoogle Scholar