✦ LIBER ✦

The number of connected sparsely edged graphs

✍ Scribed by E. M. Wright

Publisher: John Wiley and Sons
Year: 1977
Tongue: English
Weight: 472 KB
Volume: 1
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190010407

No coin nor oath required. For personal study only.

✦ Synopsis

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 exponential generating function of f(n, n + k) for particular k and so to find a formula for f(n, n + k) for general n. The first method is a recurrent one with respect to k and is well adapted for machine computation, but does not itself provide a proof that it can be continued indefinitely. The second (reduction) method is much less efficient and is indeed impracticable for k greater than 2 or 3, but it supplies the missing proof that the generating function is of a particular form and so that the first method can be continued for all k, subject only to the capacity of the machine.

📜 SIMILAR VOLUMES

The number of connected sparsely edged g

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

✍ E. M. Wright 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 413 KB

## 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 woul

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. 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

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

Linear Ramsey numbers of sparse graphs

✍ Lingsheng Shi 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 102 KB

## Abstract The Ramsey number __R__(__G__~1~,__G__~2~) of two graphs __G__~1~ and __G__~2~ is the least integer __p__ so that either a graph __G__ of order __p__ contains a copy of __G__~1~ or its complement __G__^c^ contains a copy of __G__~2~. In 1973, Burr and Erdős offered a total of $25 for se