PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 88(102) (2010), 77–86 DOI: 10.2298/PIM1002077L

MAXIMAL CANONICAL GRAPHS WITH SEVEN NONZERO EIGENVALUES

Mirjana Lazić

Communicated by Slobodan Simić

Abstract. In [3] and [4] A. Torgašev described all finite and infinite connected graphs having 3, 4 or 5 nonzero eigenvalues (not necessarily distinct). In the same papers he has given a general method how to describe all connected graphs with any fixed number of nonzero eigenvalues. In [2] M. Lepović applying his method described all finite connected graphs which have exactly 6 nonzero eigenvalues. We here describe all finite connected graphs with exactly 7 nonzero eigenvalues.

1. Introduction

Throughout the paper, G will denote a connected finite graph, |G| the order of G (i.e., the number of its vertices), V (G) will be the set of vertices of G, and n(G) will be the number of all nonzero eigenvalues of G (including multiplicities). Consider the following equivalence relation on V (G): two vertices x, y ∈ V (G) are equivalent if they are not adjacent and they have exactly the same neighbors. Let g be the corresponding quotient graph of G. We call g “the canonical graph” of G.

The canonical graph of a connected graph is also connected. A graph is called canonical if no pair of its vertices has the same neighbors. The importance of canonical graphs is given by the following theorem.

Theorem 1. [3, 4] For any graph G we have n(g) = n(G).

Let n ⩾ 2 be a fixed integer. Denote by T (n) the set of all nonisomorphic graphs with exactly n nonzero eigenvalues, and by T_{c}(n) the set of all canonical graphs belonging to T (n). By Theorem 1 is clear that describing the class T (n) is reduced to describing the class T_{c}(n). In [3] and [4] it is also proved that the class T_{c}(n) is finite for any n ⩾ 2, and a general method for finding all graphs from the class T_{c}(n) is given. In particular, it is proved that any graph G ∈ T_{c}(n) has an induced subgraph H with n vertices, belonging to T_{c}(n). Such a subgraph H can not have 0 in this spectrum, and we call it the “co-kernel” of G, or a “basic graph” of G. Clearly, each graph H ∈ T (n) of order n is canonical, and the set H of all such nonisomorphic graphs is evidently finite. Of course, a graph can have different co-kernels.

2010 Mathematics Subject Classification: Primary 05C50.

Key words and phrases: Spectra of graphs, Maximal canonical graphs.

Since every vertex x ∈ V (G) ∖ V (H) is adjacent to some vertex in H, we have that |G| ⩽ 2^{n} − 1, and there are no two vertices in V (G) ∖ V (H) which have the same neighbors.

2. The main result

By above properties, a possible method to generate all the graphs from the class T_{c}(n) is clear. We start from the class H, and for any fixed graph H ∈ H, we apply the method of extension, so that each new added vertex is adjacent to some vertices of H and no two vertices have the same neighbors. Then we investigate all possible cases related to the adjacency relation of the new vertex and all added previously, and separate all the graphs of this type which belong to class T_{c}(n). The previous procedure is obviously finite.

For n = 7 we get the following results. Among all 853 connected graphs with 7 vertices, there are exactly 342 graphs without zero in the spectrum. Hence, there are exactly 342 basic graphs in the class T_{c}(7).

Creating a computer program for mentioned method of extension of these 342 graphs, after a long computer work we got the following result.

Theorem 2. There are exactly 23413 nonisomophic canonical graphs with exactly 7 nonzero eigenvalues. Their orders run over the set {7, 8, …, 18}.

Since it is almost impossible to expose this whole list, we have some statistics about nonisomorphic canonical graphs with seven nonzero eigenvalues (Table 1). In the table n is the number of vertices of graphs, m is the number of their edges and k is the number of nonisomorphic graphs with exactly seven nonzero eigenvalues which have n vertices and m edges.

From Table 1 we have that (n, k) ∈ {(7, 342), (8, 1384), (9, 3466), (10, 5400), (11, 5656), (12, 4031), (13, 2037), (14, 778), (15, 238), (16, 65), (17, 13), (18, 3)}, where k is the number of nonisomophic canonical graphs with exactly 7 nonzero eigenvalues with n vertices.

We have made a condensation of this result. Namely, the set T_{c}(7) can be obviously ordered by the relation “to be induced subgraph”, and we can separate only the corresponding maximal graphs. The set of all maximal graphs from this set is of course finite.

Making a computer program for separating maximal graphs from the class T_{c}(7), we have got the following result.

Theorem 3. There are exactly 183 maximal graphs with 7 nonzero eigenvalues. Their orders run over the set {7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18}. All these graphs are represented in Table 2.

MAXIMAL CANONICAL GRAPHS WITH SEVEN NONZERO EIGENVALUES 79

Table 1. Statistic about nonisomorphic canonical graphs

with 7 nonzero eigenvalues

n m k n m k n m k n m k n m k
7 7 6  19 463  21 145  42 28  43 74
8 17  20 396  22 231  43 21  44 59
9 37  21 290  23 376  44 15  45 65
10 52  22 193  24 479  45 6  46 49
11 60  23 124  25 568  46 5  47 54
12 57  24 82  26 645  48 1  48 53
13 45  25 39  27 597  49 45
14 31  26 21  28 553 13 28 6  50 20
15 19  27 7  29 551  29 14  51 24
16 10  28 3  30 442  30 30  52 17
17 4  29 1  31 337  31 54  53 12
18 2  30 2  32 227  32 94  54 6
19 1  33 138  33 110  55 4
21 1 10 13 2  34 85  34 122  56 1
14 8  35 65  35 160  57 2
8 8 1  15 30  36 45  36 197  58 2
9 13  16 71  37 33  37 190  59 2
10 36  17 161  38 14  38 177  60 1
11 88  18 263  39 8  39 173  61 1
12 130  19 423  40 3  40 146
13 193  20 553  45 1  41 140 15 43 6
14 216  21 633  42 126  44 7
15 214  22 614 12 22 4  43 90  45 9
16 177  23 660  23 12  44 64  46 15
17 135  24 600  24 34  45 57  47 22
18 90  25 470  25 75  46 26  48 20
19 48  26 350  26 123  47 17  49 19
20 29  27 212  27 174  48 18  50 16
21 9  28 132  28 247  49 5  51 15
22 3  29 106  29 318  50 8  52 14
23 1  30 52  30 397  51 6  53 15
24 1  31 35  31 399  52 6  54 17
32 13  32 407  53 1  55 19
9 10 1  33 9  33 367  56 16
11 8  34 1  34 330 14 35 7  57 6
12 28  36 1  35 311  36 11  58 2

Continued on next page

n m k n m k n m k n m k n m k
13 83  37 1  36 280  37 21  59 5
14 166  37 174  38 30  60 5
15 276 11 17 3  38 137  39 50  61 3
16 370  18 8  39 82  40 56  62 3
17 445  19 34  40 52  41 58  63 2
18 468  20 68  41 32  42 54  67 2
57 5  63 8 17 62 1  72 3
16 52 3  58 3  64 9  63 1
53 2  59 1  68 2  64 3 18 73 2
54 5  60 2  69 1  65 3  81 1
55 6  61 3  70 1  70 1
56 10  62 4  71 1
57 5  63 8 17 62 1  72 3
16 52 3  58 3  64 9  63 1
53 2  59 1  68 2  64 3 18 73 2
54 5  60 2  69 1  65 3  81 1
55 6  61 3  70 1  70 1
56 10  62 4  71 1

Table 2. All maximal canonical graphs with 7 nonzero eigenvalues

001  18  73  00080 00840 008C0 0351E 05633 0632D 1803F 063AD 0359E
             056B3 28747 180BF 03D5E 06B6D 05E73 05EF3 06BED 03DDE
002  18  73  00040 08E33 12783 03A99 0D83C 06C96 1718C 19329 1C526
             08E73 0D87C 201BF 127C3 171CC 06CD6 03AD9 19369 1C566
003  18  81  080FF 00F1F 20F0F 03373 055B5 069D9 19636 1AA5A 1CC9C
             1F0F0 23363 255A5 269C9 37F00 39626 3AA4A 3CC8C 3F0E0
004  16  52  0100 2221 4448 0096 0196 2321 4548 8E0F 187D 22B7
             44DE 18EB 23B7 19EB 197D 45DE
005  16  56  0100 0065 060A 070A 0165 32D6 34B9 981F 066F 4CB9
             4AD6 076F 33D6 4DB9 35B9 4BD6
006  16  64  207F 02BF 838F 0DD3 15D5 1AB9 6476 3879 7C70 9B89
             C786 DF80 E546 EA2A F22C FD40
007  16  64  047F 149F 0BA7 49AB 3355 C372 2C6D 3C8D 7159 8EA6
             B654 CCAA D392 EB60 F458 FB80
008  16  68  2000 0B1F 80FD 0D4F 52B3 1397 4C6B 54E3 2D4F 3397
             2B1F 6C6B 72B3 74E3 5FFC 7FFC
009  15  43  0201 000C 0862 1190 020D 4532 0A63 086E 119C 1391
             0A6F 24D7 24DB 139D 453E
010  15  44  0005 0028 0B10 10C2 002D 10EA 10C7 0B38 0B15 269E
             10EF 26B3 4573 0B3D 455E
011  15  46  0401 0208 0066 0609 4898 2916 026E 0467 11B3 11D5
             066F 2D17 13BB 13DD 48FE

012  15  47  0024 0108 00C3 012C 01CB 00E7 2C13 1655 16B2 4A5D
             01EF 2C37 4ABA 175D 17BA
013  15  49  0801 1081 200E 40F0 033A 0556 066C 280F 0B3B 0D57
             0E6D 15D7 13BB 16ED 60FE
014  15  49  1002 00E1 411C 0635 0A8D 0C59 10E3 2572 23A6 29CA
             1A8F 1637 1C5B 41FD 2F1E
015  15  50  0110 0C6A 0E8A 3285 3065 19C9 428F 1B29 2636 24D6
             406F 3395 0D7A 3175 0F9A
016  15  51  0011 14C6 2B28 1706 28E8 194B 1A9A 2565 26B4 14D7
             416F 1717 28F9 2B39 42BE
017  15  51  0082 0B25 0D61 321C 1315 2C68 3458 407F 1397 329E
             0DE3 0BA7 2CEA 40FD 34DA
018  15  52  081C 1541 22A2 4543 29C6 11AD 2E52 1639 2D2A 12D5
             41AF 42D7 463B 1D5D 2ABE
019  15  53  0480 1090 202F 032B 4353 0D66 0E4D 6057 07AB 1A5D
             24AF 1976 13BB 1EDD 1DF6
020  15  53  00F0 1503 2A0C 1603 290C 196A 2695 415F 42AF 425F
             41AF 16F3 15F3 2AFC 29FC
021  15  54  0840 02D4 0D0A 501F 11A7 21A7 1639 2639 601F 079E
             29E7 19E7 2E79 1E79 0FDE
022  15  54  0460 0450 0B83 12AD 602F 191E 129D 192E 601F 4C9B
             2367 0FE3 0FD3 16FD 1D7E
023  15  54  1003 0203 421D 056C 09B4 30E2 0CD8 076F 0BB7 0EDB
             156F 19B7 1CDB 62FC 70FC
024  15  55  018E 01C6 0638 0670 1A9B 1D2D 629B 652D 283F 1AD3
             1D65 57C1 62D3 6565 07FE
025  15  59  3000 40BD 407D 054F 0A73 058F 0AB3 2357 1CAB 354F
             358F 3A73 3AB3 0FFC 3FFC
026  15  60  0C4E 13B0 2177 4177 423F 25D3 3A2D 223F 5A2D 3DC1
             3E89 45D3 5DC1 5E89 1FFE
027  15  63  047F 099F 02EF 22E7 43AB 1C5D 2477 3C55 5B89 5D19
             63A3 7661 7B81 7D11 7FFE
028  14  41  080C 0414 2050 1023 0183 02E9 036A 098F 0597 182F
             21D3 3073 06FD 077E
029  14  41  1018 2024 00C3 0303 0555 0695 096A 0AAA 10DB 2327
             20E7 131B 0CFC 0F3C
030  14  43  1003 200C 04B2 0871 01D8 02E4 0B4D 078E 0D1B 0E27
             12E7 11DB 287D 24BE
031  14  43  0301 0921 100E 0056 20F0 30A8 0357 069D 130F 06CB
             0977 0CEB 0CBD 30FE
032  14  43  0601 008E 0194 2170 206A 0CD9 1971 0795 068F 0DC3
             1327 186B 123D 21FE
033  14  45  0421 091C 109A 2076 01F1 12C3 0B45 0789 260E 1E0F
             1877 14BB 0D3D 23DE
034  14  45  0070 0848 1207 03A3 0D0D 0696 0535 300F 249E 21AB
             1277 0BEB 0D7D 0EDE
035  14  45  0250 0454 02AA 110B 28A5 04AE 0B63 309D 0B99 3067
             0D67 135B 0D9D 06FE
036  14  45  0064 0834 104C 0303 0599 069A 0367 28B3 30CB 134F

0B37 389B 05FD 06FE
037  14  47  0248 0270 048D 0996 300F 04B5 0D23 3037 11DE 156B
2A37 0F6B 06FD 0BDE
038  14  51  1240 201F 05A3 083D 20CF 08ED 0B35 2317 0D9E 14EB
1733 17E3 1A7D 1FDE
039  13  32  0201 0424 0842 1068 0099 0116 0625 0A43 018F 0317
08DB 04BD 117E
040  13  33  0009 0444 0882 0116 0231 044D 088B 011F 032E 10F1
0AB3 0675 11EE
041  13  33  0011 0022 000C 002E 001D 0033 003F 0AC7 11C7 0747
0778 0AF8 11F8
042  13  35  0105 0411 0842 008A 103C 026C 049B 018F 0947 03E3
11B3 067D 187E
043  13  35  0201 008A 0116 1068 0425 0856 028B 0317 04AF 0A57
05B9 0CF9 117E
044  13  35  0048 0421 08C4 011A 0235 0469 1483 0996 032F 1297
053B 027D 09DE
045  13  36  0081 0411 084A 0146 02AC 1133 063C 01C7 08CB 0557
036B 06BD 18BE
046  13  36  0103 020C 00C4 0813 10B1 056A 04AD 01C7 030F 08D7
0C7A 12BD 137A
047  13  36  000A 0441 0886 0138 0265 044B 09B4 0357 026F 1297
0579 14B9 09BE
048  13  36  0821 100E 028A 0416 00F0 0555 01B3 114D 03C9 0C37
0AAB 0E4D 10FE
049  13  36  0210 0023 0154 1087 0469 0233 051E 098E 14CD 0177
0679 0AE9 0B9E
050  13  36  0030 0089 0252 0407 00B9 0907 0437 115B 156C 0937
02DB 06EC 0BEC
051  13  36  0042 0422 080D 0189 0215 0257 10B3 084F 01CB 0637
05AB 18FC 07FC
052  13  36  0081 0416 084C 010E 02AA 1171 0497 018F 08CD 0733
0E71 0B69 10FE
053  13  36  0812 1105 0189 0078 0C06 046C 02B3 02CB 1247 06A7
099B 117D 0C7E
054  13  36  0501 0056 10A8 0096 1068 0623 090D 0597 0A2F 0557
0A79 0AB9 10FE
055  13  36  0489 0485 180A 0078 0074 1806 0333 034B 0347 1627
099B 04FD 187E
056  13  37  008C 020C 0143 0869 04B2 1115 0632 034F 01CF 1A33
18B3 057D 06BE
057  13  37  00D0 0207 018A 0864 0407 1439 1239 02D7 10EE 04D7
0B39 0D39 09EE
058  13  37  020C 0414 0843 1116 02A9 016A 04B1 01CF 0A4F 11B3
1A33 06BD 057E
059  13  37  0828 1050 0207 041A 00E1 0107 092F 1157 0A2F 1257
04FB 06FC 05FC
060  13  37  0041 0086 0129 00C7 04B2 0B1C 122B 055C 01AF 04F3
0AB3 0B5D 165E

061  13  37  0203 0068 014C 1096 041E 026B 0CB1 08C7 034F 0D95
             0739 13B1 10FE
062  13  37  00C4 0144 0229 0413 0871 100F 193A 0557 036D 04D7
             18BA 02ED 07BA
063  13  37  010A 0464 0851 00CD 10B2 030D 0E32 095B 056E 12B5
             0A9B 1175 06AE
064  13  37  0C05 140A 1830 0159 02A6 0166 0299 058F 064F 0A75
             11BA 09B5 127A
065  13  37  040C 0430 1803 018D 024E 0272 01B1 08D7 08EB 1317
             132B 05BD 067E
066  13  38  0110 0432 0858 0185 120E 026B 04A7 08CD 1C0F 05B7
             037B 09DD 02FE
067  13  38  0070 0434 0898 0143 028D 0507 122E 184B 1C0F 0577
             09DB 02FD 03BE
068  13  38  0148 022C 00D1 08A3 102D 0616 1417 0B16 04EB 1917
             09EB 02FD 075E
069  13  38  0109 0206 00A9 08D4 106A 0633 030F 0595 02AF 1556
             0A7B 09DD 14F6
070  13  38  0070 0492 0911 006C 048E 090D 122B 1247 1C0F 03D7
             03BB 097D 04FE
071  13  38  088A 1109 0264 042B 0896 1115 0437 0653 01EC 1A17
             05DB 136D 0AEE
072  13  39  0415 00E1 101A 01A2 029B 0B0E 0837 0A4D 154C 05B7
             10FB 07CD 196E
073  13  39  00A1 0493 0A1C 054A 0265 1816 031D 1117 0CEA 0657
             05EB 0ABD 196E
074  13  39  0506 00E8 1211 0456 1095 090F 0A33 085F 076A 08B7
             13A9 12F9 05EE
075  13  39  0243 00B8 01C2 101C 04AB 0D25 140F 098E 0A0F 0B75
             02FB 1575 11DE
076  13  39  0470 02A3 110D 0896 040F 0A4A 10B7 185E 126B 05B5
             0769 0BF0 0D5C
077  13  39  0C02 104C 101C 00B1 00E1 031F 0937 034F 06CB 0CB3
             0CE3 10FD 03FE
078  13  39  0046 0121 0216 0429 08CB 0167 1193 0A9B 046F 0337
             149B 15FC 0BFC
079  13  40  0431 020B 1058 0886 00F0 036D 05A7 11CE 150F 0CB7
             02FB 0A7D 18DE
080  13  40  0065 0618 081B 0986 02AD 0355 10AB 1153 0CAE 0D56
             139B 067D 15E6
081  13  40  084A 1304 00B1 092A 0A52 044F 11AD 0657 052F 12D5
             08FB 13B5 04FE
082  13  40  0034 020B 010B 0865 0496 013F 023F 12C7 11C7 0CC7
             13F8 0DF8 0EF8
083  13  40  010E 0096 0168 00F0 145B 0A5B 07A5 065B 0BA5 15A5
             185B 19A5 01FE
084  13  40  0402 002D 10D0 0165 021D 042F 061F 0A9B 0567 09E3
             0BD3 10FD 0BFE
085  13  40  0818 1060 0107 0087 04B5 034B 089F 091F 1167 10E7

             0779 06F9 07FE
086  13  41  0488 0233 100F 0855 00F1 1166 03AB 09CD 0B0F 1476
             06BB 0CDD 0F76
087  13  41  0148 0087 0207 049B 1079 0A65 11B6 01CF 034F 1336
             0CF9 0E79 0FB6
088  13  41  0104 004B 0263 041B 10B5 014F 0C9D 051F 0367 0AE5
             11FA 0EB5 0FFA
089  13  41  004B 01B0 0263 041B 08B5 094E 149D 0D1E 0B66 12E5
             01FB 16B5 174E
090  13  41  0099 0162 021B 0463 08D5 1156 0BAC 0A57 15AC 1457
             01FB 0EAD 172E
091  13  42  0113 04A8 080F 0171 120F 086D 02BB 0AD6 126D 0DD6
             05BB 156D 17D6
092  13  42  0848 1017 0293 0427 00EB 052D 111D 0399 0C6F 11F6
             0ADB 0F1D 0FF6
093  13  42  0427 0217 1093 0954 02E9 052E 031E 119A 0E6D 01F7
             1AD9 1CE9 1D1E
094  13  42  0810 100F 0267 04AB 00F3 0355 0599 070D 11CE 0A77
             0CBB 0F1D 0FEE
095  13  42  0302 008D 0095 106B 1073 0C6B 038F 0397 052F 0AD3
             0C73 13FC 0FFC
096  13  44  0870 100F 0393 05A5 068E 0749 10B7 125B 146D 09B7
             0B5B 0D6D 0EFE
097  13  44  008D 0462 081D 01A7 02CB 1313 0937 0A5B 04EF 1537
             165B 0BFC 17FC
098  13  45  020F 040F 0871 1192 02DB 0337 0537 04DB 07EC 1937
             18DB 1BEC 1DEC
099  13  45  0309 0432 08C7 10C7 106F 066B 0793 0997 086F 1197
             073B 0FFC 17FC
100  13  48  082D 10D2 0363 0517 068B 0977 0C9F 149F 0AEB 1177
             12EB 0FFC 17FC
101  13  52  005F 003F 02AF 0537 02CF 0557 11BB 0E5D 1AEE 1D76
             1FB9 1FD9 1FE6
102  12  26  001 306 498 468 262 194 195 263 307 469 499 83E
103  12  29  038 034 14A 289 146 285 C0B C07 B23 4D3 2BD 17E
104  12  30  004 20B 413 0C3 123 127 0C7 20F 417 879 7F8 7FC
105  12  31  018 092 14C 229 465 2A3 1C6 C0F B17 2BB 47D 1DE
106  12  32  202 210 C0C 0A7 14B 0B5 159 46F 2B7 35B 99D 1FE
107  12  33  101 23A 456 80F 073 2A9 4C5 68C 557 33B 78D 9EE
108  12  36  21F 0AF 837 07B 43D 13E 7C8 BC2 DE0 EC1 F50 F84
109  12  36  606 A28 C50 09B 165 2AF 4D7 32F 557 8F9 979 1FE
110  12  36  03F 0CF 197 26B 639 535 9C6 ACA D94 E68 F30 FC0
111  12  36  60F A17 C27 0F9 17A 1BC 3D8 5E8 9F0 E43 E85 F06
112  12  39  01F 16D 0E7 4B5 34B 693 719 96E CB6 F1A ADD FE2
113  12  46  400 81F 1F7 2FB 37D 3BE 3CF 7CF 5F7 6FB 77D 7BE
114  12  48  1DF 0FF 1BF A6F E73 DB5 7DA EEC F33 F53 FAC FCC
115  11  22  041 00A 092 10C 434 04B 14D 2B1 0D3 325 43E
116  11  22  021 041 098 106 234 44A 147 127 0D9 0B9 61E
117  11  23  012 0C1 061 226 30C 198 42D 073 0D3 48D 31E

118  11  23  022 030 0C1 11C 10E 60D 28B 0F1 0E3 455 13E
119  11  23  042 021 085 109 41C 213 063 0C7 14B 43D 3BE
120  11  23  021 041 098 106 215 40B 147 127 0D9 0B9 67E
121  11  24  005 021 0C2 138 11C 293 0E3 0C7 44B 13D 63E
122  11  24  10E 093 425 219 035 151 2E0 483 541 609 3EE
123  11  25  106 083 418 205 031 049 14F 137 49B 61D 2FE
124  11  25  08B 0A5 0B4 740 09A 30B 147 465 31A 474 638
125  11  25  018 012 0C6 123 129 0CC 60F 475 13B 395 0DE
126  11  26  090 146 229 40F 21D 11E 463 1E2 2E1 2B9 1D6
127  11  26  044 083 023 20F 439 153 067 0C7 499 3B8 3FC
128  11  26  10C 031 423 059 095 313 2E2 487 44B 13D 3EE
129  11  26  034 109 203 055 0A5 45A 4AA 237 4CB 13D 3CE
130  11  26  1C2 125 618 425 40F 28E 10F 171 2F0 471 2DA
131  11  27  003 164 298 136 239 2C9 1C6 167 29B 49D 46E
132  11  28  022 115 219 053 0B1 44F 3CC 137 23B 4AD 3EE
133  11  29  086 051 0E5 529 338 1C3 24F 0D7 51B 43D 3BE
134  11  31  201 402 03F 05F 0AF 157 1A7 1C7 1F8 3F9 5FA
135  11  31  017 00F 0AB 14D 0B3 155 467 387 6BA 75C 7F8
136  11  31  00F 017 0B3 153 0AB 14B 38E 475 61B 7F4 7EC
137  11  32  186 078 497 50F 23B 25D 369 2F1 5A3 5C5 1FE
138  11  32  02E 1D0 237 26B 2AD 5C9 30F 4F1 553 595 1FE
139  11  33  08F 117 227 447 0BB 15D 26D 473 7B2 7CC 7F8
140  11  33  06F 0AF 0D7 31B 535 656 1E9 696 768 7A8 7D0
141  11  34  0E0 11E 21D 46B 4B3 4C7 34F 397 33B 2FD 1FE
142  11  35  140 0B7 44F 23D 50F 29E 2AB 1F7 3EB 37D 3DE
143  11  35  14F 0B7 45B 23D 52B 2D5 3A5 5C3 6B1 749 7FE
144  11  36  300 50F 617 07B 0BD 0DE 1EF 2F7 37B 3BD 3DE
145  11  37  0E0 11B 217 46F 4BD 4DE 36F 2F7 1FB 3BD 3DE
146  11  40  107 0F0 47F 27F 3BB 3DD 3EE 1F7 5BB 5DD 5EE
147  10  27  038 0C5 146 183 21F 22F 237 1BB 0FD 17E
148  10  33  09F 06F 237 13B 1CB 2C7 363 393 3FD 3FE
149  09  14  018 006 00C 012 125 143 0D1 0A9 01E
150  09  16  038 052 094 111 1E0 107 04B 08D 02E
151  09  16  023 00B 015 105 049 091 061 181 1FE
152  09  17  011 00A 023 043 107 087 01B 0FC 17C
153  09  17  018 00F 033 055 161 186 0AA 0CC 0F0
154  09  18  081 102 017 00F 047 027 078 0F9 17A
155  09  18  081 101 017 00F 04B 035 069 071 1FE
156  09  18  02B 00F 01B 115 066 1C4 0B8 1D0 1E0
157  09  19  049 00E 130 055 063 187 0AB 09D 13E
158  09  21  0C0 10B 107 01D 02E 0B7 07B 0DD 0EE
159  09  22  088 10B 035 056 06F 197 07B 0BD 0DE
160  09  22  08B 10B 035 056 06C 197 07B 1AD 1CE
161  09  22  00D 070 08B 097 0AE 157 13B 07D 16E
162  09  22  081 104 03A 05F 06F 077 0BB 07D 13E
163  09  24  0F0 11B 127 14D 18E 0B7 07B 0DD 0EE
164  09  25  0A3 11C 03F 14F 0CF 0F5 0FA 175 17A
165  09  26  04B 035 11F 09F 0ED 173 0F3 16D 1FE
166  09  30  05F 03F 12F 0D7 1A7 1C7 1FB 1FD 1FE

167  08  13  25 26 C2 0B 13 C1 78 9C
168  08  15  0A 29 54 27 C3 33 9D 5E
169  08  17  1B 27 4D 8B B4 6A D5 F2
170  08  17  49 93 0F 47 A5 39 71 FE
171  07  09  06 03 0A 15 49 70 2C
172  07  09  09 05 03 41 21 11 7E
173  07  11  34 4A 45 23 51 29 1E
174  07  11  03 06 0D 15 3A 65 5A
175  07  12  15 0B 45 23 51 29 7E
176  07  12  31 49 45 23 13 0D 7E
177  07  12  30 49 46 27 1B 1D 2E
178  07  12  23 58 25 26 1B 4D 56
179  07  13  21 41 0F 17 1B 1D 7E
180  07  14  25 51 2B 17 4B 1D 7E
181  07  15  23 43 0F 17 1B 7D 7E
182  07  17  17 0F 47 27 7B 7D 7E
183  07  21  3F 5F 6F 77 7B 7D 7E

We notice that all the graphs in the table are represented in the form:

n_{1} n_{2} n_{3} a_{1} a_{2} a_{3} … a_{n_{2}},

where n_{1} is the ordering number of maximal graph, n_{2} the number of its vertices, n_{3} the number of its edges and a_{1}, a_{2}, a_{3}, …, a_{n_{2}} denote the rows of adjacency matrix. The coding is made by converting the row of adjacency matrix from binary cod into hexadecimal.

We notice that for each graph from the above table the corresponding basic graph is always induced by its first 7 vertices. So it can be easily found.

From Table 2 we have that there exist exactly 13 maximal graphs of order 7, 4 graphs of order 8, 18 graphs of order 9, 2 graphs of order 10, 32 graphs of order 11, 13 graphs of order 12, 63 graphs of order 13, 11 graphs of order 14, 19 graphs of order 15, 5 graphs of order 16 and 3 graphs of order 18.

Any other canonical graph with 7 nonzero eigenvalues is then an induced subgraph of the 183 maximal graphs and an overgraph of the corresponding basic graph of this maximal graph. Hence, the complete list of all canonical graphs with 7 nonzero eigenvalues can be easily generated by Table 1.

References

[1] D. M. Cvetković, M. Doob, H. Sachs, Spectra of Graphs – Theory and Application, VEB Deutscher Verlag der Wissenschaften, Berlin, 1980.

[2] M. Lepović, Maximal canonical graphs with 6 nonzero eigenvalues, Glasnik Mat. 25 (1990), 683–686.

[3] A. Torgašev, On infinite graphs with three and four nonzero eigenvalues, Bull. Acad. Serbe Sci. Arts. (Sci. Math.) 76(11) (1981), 39–48.

[4] A. Torgašev, On infinite graphs with five nonzero eigenvalues, Bull. Acad. Serbe Sci. Arts (Sci. Math.) 79(12) (1982), 31–38.

Department of Mathematics (Received 05 02 2008) University of Kragujevac Kragujevac, Serbia

mmmvl@kg.ac.rs