๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

The number of connected sparsely edged graphs. III. Asymptotic results

โœ Scribed by E. M. Wright

Publisher
John Wiley and Sons
Year
1980
Tongue
English
Weight
413 KB
Volume
4
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

โœฆ Synopsis

Abstract

The number of connected graphs on n labeled points and q lines (no loops, no multiple lines) is f(n,q). In the first paper of this series I showed how to find an (increasingly complicated) exact formula for f(n,n+k) for general n and successive k. The method would give an asymptotic approximation to f(n,n+k) for any fixed k as n โ†’ โˆž. Here I find this approximation when k = o(n^1/3^), a much more difficult matter. The problem of finding an approximation to f(n,q) when q > n + Cn^1/3^ and (2 q/n) โ€ log n โ†’ โ€ โˆž is open.

๐Ÿ“œ SIMILAR VOLUMES

The number of connected sparsely edged g
The number of connected sparsely edged graphs
โœ E. M. Wright ๐Ÿ“‚ Article ๐Ÿ“… 1977 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 472 KB

## Abstract An (__n, q__) graph has __n__ labeled points, __q__ edges, and no loops or multiple edges. The number of connected (__n, q__) graphs is __f(n, q)__. Cayley proved that __f(n, n__^โ€1^) = __n__^nโˆ’2^ and Renyi found a formula for __f(n, n)__. Here I develop two methods to calculate the exp

The number of connected sparsely edged g
The number of connected sparsely edged graphs. IV large nonseparable graphs
โœ E. M. Wright ๐Ÿ“‚ Article ๐Ÿ“… 1983 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 306 KB

The number of nonseparable graphs on n labeled points and q lines is u(n, 9). In the second paper of this series an exact formula for u(n, n + k) was found for general n and successive (small) k. The method would give an asymptotic approximation for fixed k as n + 30. Here an asymptotic approximatio

Wright's formulae for the number of conn
Wright's formulae for the number of connected sparsely edged graphs
โœ P. M. D. Gray; A. M. Murray; N. A. Young ๐Ÿ“‚ Article ๐Ÿ“… 1977 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 161 KB

## Abstract We have written computer programs to determine exactly the coefficients in Wright's formula for __f(n, n + k)__, the number of connected sparsely edged labeled graphs (see preceding paper), and used them up to __k__ = 24. We give the results up to __k__ = 7.

The number of connected sparsely edged g
The number of connected sparsely edged graphs. II. Smooth graphs and blocks
โœ E. M. Wright ๐Ÿ“‚ Article ๐Ÿ“… 1978 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 215 KB

A smooth graph is a connected graph without endpoints; f (n, q ) is the number of connected graphs, v(n, q ) is the number of smooth graphs, and u(n, q) is the number of blocks on n labeled points and q edges: wk, V,, and u k are the exponential generating functions of f(n, n + k ) , v(n, n + k). an

The Number of Removable Edges in 3-Conne
The Number of Removable Edges in 3-Connected Graphs
โœ Su Jianji ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 147 KB

An edge of a 3-connected graph G is said to be removable if G&e is a subdivision of a 3-connected graph. Holton et al. (1990) proved that every 3-connected graph of order at least five has at least W(|G| +10)ร‚6X removable edges. In this paper, we prove that every 3-connected graph of order at least