A064731 Number of connected integral graphs on n vertices.

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

Offset: 1

Author

Gordon F. Royle, Oct 17 2001

Keywords

• more
• nonn
• nice

Comments

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

Examples

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

Links

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

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

Formula

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

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