A064731 Number of connected integral graphs on n vertices.

1, 1, 1, 2, 3, 6, 7, 22, 24, 83, 113, 325

Offset

1,4

Comments

An integral graph is defined by the property that all of the eigenvalues of its adjacency matrix are integral.

Links

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

K. Balinska, D. Cvetkovic, M. Lepovic, S. Simic, There are exactly 150 connected integral graphs up to 10 vertices, Univ Beograd Publ Elektrotehn Fak Ser Mat 10 (1999), 95-105.

K. Balinska, D. Cvetkovic, Z. Radosavljevic, S. Simic and D. Stevanovic, A survey of integral graphs, Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. 13 (2002), 42-65. However, the values given there for a(11) and a(12) are incorrect.

K. T. Balińska, M. Kupczyk, S. K. Simić, K. T. Zwierzyński, On generating all integral graphs on 11 vertices, Tech Univ Poznań Comput Sci Cent Rep 469 (1999/2000).

K. T. Balińska, M. Kupczyk, S. K. Simić, K. T. Zwierzyński, On generating all integral graphs on 12 vertices, Tech Univ Poznań Comput Sci Cent Rep 482 (2001).

K. T. Balińska, S. K. Simić, K. T. Zwierzyński, Some properties of integral graphs on 13 vertices, Tech Univ Poznań Comput Sci Cent Rep 578 (2009). This paper contains incomplete enumeration of integral graphs on 13 vertices (547), so this term is not added to the sequence at this moment.

D. Cvetkovic, S. K. Simic, Errata, Univ Beograd, Ser. Mat 15 (2004) 112.

L. Wang, A survey on integral trees and integral graphs, 2005.

Eric Weisstein's World of Mathematics, Connected Graph

Eric Weisstein's World of Mathematics, Integral Graph

K. T. Zwierzynski, Generating Integral Graphs Using PRACE Research Infrastructure, Partnership for Advanced Computing in Europe, 2013.

Formula

a(n) = A077027(n) - A287154(n).

Example

The three integral graphs on five vertices are the star K1,4, the complete graph K5 and the complete join (K2 join 3K1).

Crossrefs

Cf. A077027 (number of simple not necessarily connected integral graphs).

Cf. A287154 (number of simple disconnected integral graphs).

Cf. A363064 (number of connected Laplacian integral graphs).

Sequence in context: A352934 A073317 A371293 * A159069 A162681 A070301

Adjacent sequences: A064728 A064729 A064730 * A064732 A064733 A064734

Keyword

more,nonn,nice

Author

Gordon F. Royle, Oct 17 2001

Extensions

a(11) = 236 and a(12) = 325 (from the BCRSS paper) sent by Felix Goldberg (felixg(AT)tx.technion.ac.il), Oct 06 2003; however, it appears that those numbers were incorrect

a(11) = 113 from Gordon F. Royle, Dec 30 2003; confirmed by Krystyna Balinska, Apr 19 2004

a(12) = 325 from the BKSK 2001 paper added by Dragan Stevanovic, Jan 29 2020

Status

approved