A039735 - OEIS

A039735

Triangle read by rows: T(n,k) = number of nonisomorphic unlabeled planar graphs with n >= 1 nodes and 0 <= k <= 3n-6 edges.

1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 2, 1, 1, 1, 1, 2, 4, 6, 6, 6, 4, 2, 1, 1, 1, 2, 5, 9, 15, 21, 24, 24, 20, 13, 5, 2, 1, 1, 2, 5, 10, 21, 41, 65, 97, 130, 144, 135, 98, 51, 16, 5, 1, 1, 2, 5, 11, 24, 56, 115, 221, 401, 658, 956, 1217, 1264, 1042, 631, 275, 72, 14, 1, 1, 2, 5

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,10

COMMENTS

Planar graphs with n >= 3 nodes have at most 3n-6 edges. - Charles R Greathouse IV, Feb 18 2013

REFERENCES

R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.

R. J. Wilson, Introduction to Graph Theory. Academic Press, NY, 1972, p. 162.

LINKS

Table of n, a(n) for n=1..76.

F. Harary, The number of linear, directed, rooted, and connected graphs, Trans. Amer. Math. Soc. 78 (1955), 445-463. (MR0068198) See page 457, equation (2.9).

FORMULA

From Michael Somos, Aug 23 2015: (Start)

Sum_{k} T(n, k) = A005470(n) if n >= 1.

log(1 + A(x, y)) = Sum_{n>0} B(x^n, y^n) / n where A(x, y) = Sum_{n>0, k>=0} T(n,k) * x^n * y^k and similarly B(x, y) with A049334. (End)

EXAMPLE

Triangle starts

n\k 0 1 2 3 4 5 6 7 8 9 10 11 12

--:-- -- -- -- -- -- -- -- -- -- -- -- --

1: 1

2: 1 1

3: 1 1 1 1

4: 1 1 2 3 2 1 1