A112410 Number of connected simple graphs with n vertices, n+1 edges, and vertex degrees no more than 4.

0, 0, 0, 1, 5, 17, 56, 182, 573, 1792, 5533, 16977, 51652, 156291, 470069, 1407264, 4193977, 12451760, 36838994, 108656009, 319583578, 937634011, 2744720126, 8018165821, 23379886511, 68056985580, 197800670948, 574068309840, 1663907364480, 4816910618093, 13929036720057

Offset: 1

Author

Jonathan Vos Post, Dec 08 2005

Keywords

• nonn

Comments

Such graphs are also referred to (e.g., by Hendrickson & Parks) as carbon skeletons with two rings, or bicyclic skeletons, although actual number of simple cycles in such graphs can exceed 2 (e.g., in the example). - Andrey Zabolotskiy, Nov 24 2017

Terms computed with nauty agree at least to a(20) with those computed by formula and sequences A125669, A125670, A125671, A305132. - Andrew Howroyd, May 26 2018

Examples

			The only such graph for n = 4 is:
o-o
|/|
o-o
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..200
• J. B. Hendrickson and C. A. Parks, Generation and Enumeration of Carbon skeletons, J. Chem. Inf. Comput. Sci., 31 (1991), 101-107. See Table 2, column 2 on page 103.
• Michael A. Kappler, GENSMI: Exhaustive Enumeration of Simple Graphs.

Crossrefs

The analogs for n+k edges with k = -1, 0, ..., 7 are: A000602, A036671, this sequence, A112619, A112408, A112424, A112425, A112426, A112442.

Cf. A121941 (any number of edges), A006820 (2n edges).

Cf. A125669, A125670, A125671, A305132.

Programs

nauty

for n in {4..15}; do geng -c -D4 ${n} $((n+1)):$((n+1)) -u; done # Andrey Zabolotskiy, Nov 24 2017

Formula

a(n) = A125669(n) + A125670(n) + A125671(n) + A305132(n). - Andrew Howroyd, May 26 2018

Extensions

Corrected offset and new name from Andrey Zabolotskiy, Nov 20 2017

a(20) corrected by Andrey Zabolotskiy and Andrew Howroyd, May 26 2018

Terms a(21) and beyond from Andrew Howroyd, May 26 2018