Numbers of characteristic polynomials and cospectral graphs for A

Number of distinct characteristic polynomials, and number of graphs with a cospectral mate for the adjacency matrix A.

n#graphs#char. pols#graphs with mate
0110
1110
2220
3440
411110
534332
615615110
71044988110
812346114531722
927466824735751039*
1012005168106081282560606*
111018997864901029366215331676*
1216509117259214818799352031067572481

The three starred entries are 1 more, 90 more, and 1 less than the corresponding values that Haemers & Spence found. The first entry is confirmed by Godsil & McKay (who gave data up to n=9). Lepović has collected statistical data on connected graphs on 10 vertices, so his data is not directly comparable to the data here. The entire table above has now been confirmed by Spence.

References

C. Godsil & B. McKay, Some computational results on the spectra of graphs, in: Combinatorial Mathematics IV, Springer LNM 560 (1976) 73-92.

W. H. Haemers & E. Spence, Enumeration of cospectral graphs, Europ. J. Combin. 25 (2004) 199-211.

Mirko Lepović, Some statistical data on graphs with 10 vertices, Univ. Beograd Publikacija Elektrotehničkog Fakulteta - Serija: Matematika 9 (1998) 79-88.

The number of distinct characteristic polynomials for simple graphs on n vertices is sequence A082104 in the Encyclopedia of Integer Sequences.

Number of graphs per polynomial

Number of characteristic polynomials that occur for m graphs, for the adjacency matrix A.

n 1234567 8910111213 14151621
5 321              
6 1465              
7 934522             
8 10624771526            
9 223629210252015551953712-2      
10 94445621003418110812367485672469394887012514272289131042

For n=11 the largest family of cospectral graphs has size 46. For n=12 it has size 128.

Subdivided according to number of edges

Below the same data again, subdivided according to number of edges. Perhaps one is mostly interested in the totals, but because the files are large, and the spectrum determines the number of edges and of triangles, it is easiest to subdivide the generation process. As a side result we have counts of the number of simple graphs with given numbers of vertices, edges, and triangles.)

n=5 n=6 n=7 n=8 n=9 n=10 n=11 n=12

n < 5

No cospectral graphs.

n=5

Here and below, e gives the numer of edges, #cp gives the number of distinct characteristic polynomials, #cpN (for N=1,2,...) gives the number of characteristic polynomials that occur for precisely N graphs.

e#graphs#cp#cp1#cp2#with mate
0111-0
1111-0
2222-0
3444-0
465412
5666-0
6666-0
7444-0
8222-0
9111-0
10111-0

Here a single cospectral pair: K1+C4 and K1,4, with spectrum 2,0,0,0,–2.

n=6

e#graphs#cp#cp1#cp2#with mate
0111-0
1111-0
2222-0
3555-0
497524
515141312
621201912
724232212
8242424-0
9212121-0
10151515-0
11999-0
12555-0
13222-0
14111-0
15111-0

n=7

e#graphs#cp#cp1#cp2#cp3#with mate
0111--0
1111--0
2222--0
3555--0
410862-4
5211918-13
64134277-14
76561574-8
89788799-18
91311251196-12
101481401328-16
111481411355113
121311251196-12
139795932-4
146564631-2
154140391-2
162120191-2
17101010--0
18555--0
19222--0
20111--0
21111--0

Here two triples of cospectral graphs, one with 5 and one with 11 edges. The first triple has spectrum 2, 1, 0, 0, 0, –1, –2 and consists of the three graphs K1+K2+C4 and K1,4+K2 and K1,2~K1,2. The second triple has spectrum 3.49, 1.29, 0, 0, –1, –1.78, –2 (where the three nonintegers are roots of x3–3x2–4x+8 = 0). The adjacency matrices are

...1..1   ...1111   ..1.111
....111   ...1...   ...1.1.
....111   ....111   1...111
1.....1   11...1.   .1....1
.11...1   1.1...1   1.1....
.11...1   1.11..1   111...1
111111.   1.1.11.   1.11.1.

n=8

e#graphs#cp#cp1#cp2#cp3#cp4#with mate
0111---0
1111---0
2222---0
3555---0
411972--4
524211911-5
656443571121
71151028913--26
8221187158253163
9402366334284-68
106635764996710-164
119809038326641148
121312119810939771219
1315571443133410531223
14164615331427997-219
151557145113471022-210
16131212341161685-151
17980933889421191
18663630599292-64
1940238737215--30
2022121521122-10
211151131112--4
225655541--2
23242424---0
24111111---0
25555---0
26222---0
27111---0
28111---0

n=9

e#graphs#cp#cp1#cp2#cp3#cp4#cp5#cp6#cp7#cp8#cp9#cp10#with mate
0111---------0
1111---------0
2222---------0
3555---------0
411972--------4
525222011-------5
663493981-1-----24
7148120971931------51
834526920950541-----136
9771658567751141-----204
10163713471125169411011----512
113252285825123053551-----740
125995520345764941091923----1419
13101209012805584089226-----2065
141561513826123331273167371051---3282
1521933196371760218331494922----4331
16279872499322474217326157188-1-15513
1732403290642606527421797512----6338
18340403060227636261525772175----6404
19324032926126413262615466-2----5990
20279872532023056197920554204-1-14931*
2121933199881823816001103631----3695
221561514289131579831182083----2458
23101209331862065241171-----1500
2459955565520629658311----789
253252305028571866-1-----395
261637155014756312-------162
27771739708301-------63
2834533532762-------18
291481441404--------8
306362611--------2
31252525---------0
32111111---------0
33555---------0
34222---------0
35111---------0
36111---------0

The above data agrees with Godsil & McKay. For the starred entry Haemers & Spence gave 4930 instead of 4931.

n=10

In order not to make the following table too wide, the data for a given number of edges is given in several rows, with cp1-cp10 in the first row, cp11-cp20 in the second row, cp21-cp30 in the third row, etc.

e#graphs#cp#cp1#cp2#cp3#cp4#cp5#cp6#cp7#cp8#cp9#cp10#with mate
0111---------0
1111---------0
2222---------0
3555---------0
411972--------4
526232111-------5
666514091-1-----26
716513010322311-----62
842831623761936-----191
911038736911482383-----412
10276921441701326772411221--1068
1167595655476573311629921---1994
121577212992109291583332943016611-4843
1334663297742578933235041063016321-8874
147131860763525706549119129894361353318748*
1---------
15136433118922104581121081618415121551372131852
-1--------
1624157720993818475020773313486423310639273356827
21111-----
17395166346777307180336164147130425418349287287986
52--------
18596191522518462841501646611207438529260581211133350
8-2-------
198287287296376474927055379782662453356566376181236
7211------
2010611599335858279099092110058346654444393991323233250
66-21-----
1---------
2112513891102637978053108195111054013539494109831418273336
322322----
22135885211988881064453117027117564363542510107100128294399
621-1-----
23135885212006731067461116158115454269508499103981310291391
52-11-----
24125138911068189850951060981066237964954748278819266294
221222----
251061159940404839500874509233314146140181911120221659
56-21-----
1---------
268287287370046600116674271832310327315475076168717
51--------
275961915314744779244579855221616266244394079118267
8-1-------
2839516635375131907329898345598515613422154276093
61--------
29241577217134196949171212297533122741913-144628
3--11-----
3013643312334811214597551147217482835--24288
317131864836593904625679101221216--11928
3234663317762923122562453671----5432
33157721459113584857129183-----2188
346759632259193722911-----840
35276926152479119161------290
36110310541009414-------94
37428414402102-------26
381651621593--------6
396665641--------2
40262626---------0
41111111---------0
42555---------0
43222---------0
44111---------0
45111---------0

This data agrees with the data given by Haemers & Spence, except for the starred entry 18748 where they have 18747. That means that their total is 2560605, and that their 2560516 was a typo.

n=11

Here the last column gives the maximum size of a family of cospectral graphs.

e#graphs#cp#with matemaxsz
01101
11101
22201
35501
411942
5262353
66752265
7172135655
84673362206
913059805586
103664268516179
1110250818136018
1228259223041008810
1375415630212191511
141927881600485685116
1546780740183011809921
16106989091836626916621
172295898200189152957916
1846091794022395105469821
19864013475938061892068*20
201510804713287522329256631
212463088721719491527919030
223743376033026554800147739
2353037356468464291126462935
2470065437618898501490375436
2586318670762563131837328031
2699187806876448592110834946
27106321628939929682256101834
28106321628940185622251907734
2999187806877245332097557346
3086318670763752101817714331
3170065437620435911464899636
3253037356470048091100395134
333743376033196606772150733
342463088721862432504366430
351510804713426080306524230
3686401347690246173380820
374609179410900991374118
382295898205233444668716
39106989095942620283215
40467807421573855099
41192788174815332219
427541568958120796
43282592608840485
4410250958212725
45366434683694
46130512531003
47467454243
4817216882
49676622
50262601
51111101
525501
532201
541101
551101
The starred entry is 1 less than the corresponding entry in Haemers & Spence. (And correspondingly our total is 1 less than their total.)

n=12

e#graphs#cp#with matemaxsz
01101
11101
22201
35501
411942
5262353
66853265
7175137675
84853462317
9140510286308
1041912930203810
11127639621527710
1239243294051619314
13119890961374076415
1435930728787412100621
15104377487640829384224
162911086245107580239426
1777396016685738187869520
181951536116911773463379531
1946505609408294791022653636
20104504341920091612252924547
212211473511960039944562354042
224403936063912100058933335058
2382507550673560735616307731775
241454265734129867830128388192884
252411961516215807498346416879770
263765262970337222587771928317988
2755342550924962042192104880437877
2876613452776873359123144574446598
2999923401878969183184187960977387
301228184120911026119614230881162089
3114229503560127773984092672120188106
321554235043613959109693291482299098
3316006173014143779929332998429426128
341554235043613960847673291201111398
3514229503560127805316272667028735106
361228184120911030772434230129960889
3799923401878974361437187122781192
3876613452776879443698143597968298
3955342550924967640411103980043977
403765262970337804081371001727888
412411961516216271625745675677170
421454265734130307695127692848184
4382507550673865647515824252675
444403936063938822688513858052
452211473511976217764306606242
46104504341933163792048202837
474650560941511313914729326
481951536117422116383600723
4977396016918134150845017
502911086260821055720915
51104377493939719294610
523593073254476276410
53119890109562192998
54392433624755986
55127631194515555
56419139744074
57140513501063
58485471263
5917517262
60686722
61262601
62111101
635501
642201
651101
661101