A077027 -id:A077027 - cp's OEIS frontend

A064731 Number of connected integral graphs on n vertices.

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

Offset: 1

Gordon F. Royle, Oct 17 2001

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

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

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.

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

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

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

A363065 Number of Laplacian integral graphs on n vertices.

Original entry on oeis.org

1, 2, 4, 10, 24, 70, 188, 553, 1721, 5716

Offset: 1

Nathaniel Johnston, May 16 2023

A (simple, undirected) graph is called Laplacian integral if all eigenvalues of its Laplacian matrix are integers. The corresponding sequence that uses the adjacency matrix instead of the Laplacian matrix is A077027.

Since every cograph is Laplacian integral, a(n) >= A000084(n).

			For n <= 3, all graphs are Laplacian integral, so a(n) = A000088(n) when n <= 3.
There is exactly one graph on 4 vertices that is not Laplacian integral: the path P_4, which has Laplacian matrix
   1 -1  0  0
  -1  2 -1  0
   0 -1  2 -1
   0  0 -1  1
which has eigenvalues 0, 2, 2-sqrt(2), and 2+sqrt(2), which are not all integers.

R. Grone and R. Merris, Indecomposable Laplacian integral graphs, Linear Algebra and its Applications, 428 (2008), 1565-1570.

Cf. A000084, A000088, A077027, A363064 (connected graphs only).

a(10) from M. A. Achterberg, May 26 2023

A287154 Number of simple disconnected integral graphs on n vertices.

Original entry on oeis.org

0, 1, 2, 4, 7, 14, 26, 49, 97, 186, 379

Offset: 1

Eric W. Weisstein, May 20 2017

Eric Weisstein's World of Mathematics, Disconnected Graph
Eric Weisstein's World of Mathematics, Integral Graph

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

Cf. A064731 (number of simple connected integral graphs).

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

cp's OEIS Frontend

A064731 Number of connected integral graphs on n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A363065 Number of Laplacian integral graphs on n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A287154 Number of simple disconnected integral graphs on n vertices.

Views

Author

Keywords

Links

Crossrefs

Formula