A003089 Number of connected line graphs with n nodes.

1, 1, 2, 5, 12, 30, 79, 227, 710, 2322, 8071, 29503, 112822, 450141, 1867871, 8037472, 35787667, 164551477, 779945969, 3804967442, 19079312775, 98211456209, 518397621443, 2802993986619, 15510781288250, 87765472487659, 507395402140211, 2994893000122118, 18035546081743772, 110741792670074054, 692894304050453139

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• nice

Comments

Sequence is identical to the number of connected graphs on n edges (A002905), except for the term a(3). The three connected 3-edge graphs (P_4, K_3 and K_{1,3}) yield only two linegraphs because K_3 and K_{1,3} have isomorphic linegraphs. No other connected nonisomorphic graphs have isomorphic linegraphs.

References

• F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 221.
• R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Max Alekseyev, Table of n, a(n) for n = 1..60
• Eric Weisstein's World of Mathematics, Line Graph.

Crossrefs

Cf. A002905.

Extensions

More terms from Ronald C. Read.

More terms from Gordon F. Royle, Jun 05 2003

a(25)-a(26) from Max Alekseyev, Nov 25 2013

a(27) and beyond from Max Alekseyev, Sep 07 2016