Bulletin T.CXXIX de l’Académie serbe des sciences et des arts - 2004 Classe des sciences mathématiques et naturelles sciences mathématiques, N\underline{o} 29

SETS OF COSPECTRAL GRAPHS WITH LEAST EIGENVALUE AT LEAST −2 AND SOME RELATED RESULTS

D. CVETKOVIĆ, M. LEPOVIĆ

(Presented at the 4th Meeting, held on May 28, 2004)

A b s t r a c t. In this paper we study the phenomenon of cospectrality in generalized line graphs and in exceptional graphs. The paper contains a table of sets of cospectral graphs with least eigenvalue at least −2 and at most 8 vertices together with some comments and theoretical explanations of the phenomena suggested by the table. In particular, we prove that the multiplicity of the number 0 in the spectrum of a generalized line graph L(G) is at least the number of petals of the corresponding root graph G.

AMS Mathematics Subject Classification (2000): 05C50

Key Words: graphs, eigenvalues, least eigenvalue, cospectral graphs

1. Introduction

The spectrum of a graph is the spectrum of its adjacency matrix. Cospectral graphs are graphs having the same spectrum.

Both subjects contained in the title, cospectral graphs and graphs with least eigenvalue −2, have been studied since very beginnings of the development of the theory of graph spectra.

Both subjects, although present in the investigations all the time, have recently attracted special attention. In the first case it was the power of nowdays computers which enabled some investigations which were not possible in the past [18], while in the second case the reason was the constructive enumeration of maximal exceptional graphs [12].

In this paper we consider the intersection of these two subjects and study the phenomenon of cospectrality in generalized line graphs and in exceptional graphs. The paper contains a table of sets of cospectral graphs with least eigenvalue at least −2 and with 6, 7 or 8 vertices together with some comments and theoretical explanations of the phenomena suggested by the table.

2. Basic notions

Let G = (V, E) be a simple graph with n vertices. The characteristic polynomial det(xI − A) of the adjacency matrix A of G is called the characteristic polynomial of G and denoted by P_{G}(x). The eigenvalues of A (i.e., the zeros of det(xI − A)) and the spectrum of A (which consists of the n eigenvalues) are also called the eigenvalues and the spectrum of G, respectively. The eigenvalues of G are usually denoted by λ_{1}, λ_{2}, …, λ_{n}; they are real because A is symmetric. Unless we indicate otherwise, we shall assume that λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{n} and use the notation λ_{i} = λ_{i}(G) for i = 1, 2, …, n.

Graphs with the same spectrum are called isospectral or cospectral graphs. The term ”(unordered) pair of isospectral non–isomorphic graphs” will be denoted by PING. More generally, a ”set of isospectral non–isomorphic graphs” is denoted by SING. A two element SING is a PING. A SING may be empty (of course, if it has no elements) or trivial (if it consists of just one graph). A graph H, cospectral but non–isomorphic to a graph G, is called a cospectral mate of G.

As usual, K_{n}, C_{n} and P_{n} denote respectively the complete graph, the cycle and the path on n vertices. Further, K_{m,n} denotes the complete bipartite graph on m + n vertices. The cocktail-party graph CP (n) is the unique regular graph with 2n vertices of degree 2n − 2; it is obtained from K_{2n} by deleting n mutually non-adjacent edges.

The union of disjoint graphs G and H is denoted by G ∪ H . The joint G ∇H of (disjoint) graphs G and H is the graph obtained from G and H by joining each vertex of G with each vertex of H.

3. L–graphs and graphs with blossoms

Let L (L^{+}, L^{0}) be the set of graphs whose least eigenvalue is greater then or equal to −2 (greater then −2, equal to −2). A graph is called an L–graph (L^{+}–graph, L^{0}–graph) if its least eigenvalue is greater then or equal to −2 (greater then −2, equal to −2).

The line graph L(H) of any graph H is defined as follows. The vertices of L(H) are the edges of H and two vertices of L(H) are adjacent whenever the corresponding edges of H have a vertex of H in common.

Interest in the study of graphs with least eigenvalue −2 began with an elementary observation that line graphs have the least eigenvalue greater than or equal to −2. A natural problem arose to characterize the graphs with such a remarkable property. It appeared that line graphs share this property with generalized line graphs and with some exceptional graphs.

A generalized line graph L(H; a_{1}, …, a_{n}) is defined (in [19]) for graphs H with vertex set {1, …, n} and non-negative integers a_{1}, …, a_{n} by taking the graphs L(H) and CP (a_{i}) (i = 1, …, n) and adding extra edges: a vertex e in L(H) is joined to all vertices in CP (a_{i}) if i is an end-vertex of e as an edge of H. We include as special cases an ordinary line graph (a_{1} = a_{2} = ⋯ = a_{n} = 0) and the cocktail-party graph CP (n) (n = 1 and a_{1} = n). We introduce the abbreviation GLG for a generalized line graph.

Let a = (a_{1}, a_{2}, …, a_{n}). Consider a generalized line graph L(G; a), where G is connected and ∑_{i=1}^{n} a_{i} > 0. The root graph of L(G; a) is defined in [8] as the multigraph H obtained from G by adding a_{i} pendant double edges (petals) at vertex v_{i} for each i = 1, …, n. Then L(G; a) = L(H) if we understand that in L(H) two vertices are adjacent if and only if the corresponding edges in H have exactly one vertex in common.

It is convenient to reformulate slightly the concept of the root graph of a GLG.

A pendant double edge is called a petal. A blossom B_{n} consists of n (n ≥ 0) petals attached at a single vertex. An empty blossom B_{0} has no petals and is reduced to the trivial graph K_{1}. A graph in which to each vertex a blossom (possibly empty) is attached is called a graph with blossoms or a B–graph. The set of B–graphs includes as a subset the set of (undirected) graphs without loops or multiple edges. A graph G is a generalized line graph if G = L(H) is the line graph of a B–graph H called the root graph of G. The definition of L(H) remains as given above. We have L(B_{n}) = CP (n). A GLG is called a line graph if there exists a B–graph H with no petals such that G = L(H) while in the opposite case G is a proper generalized line graph. Hence, the set of generalized line graphs is the union of two disjoint sets: the set of line graphs and the set of proper generalized line graphs.

An exceptional graph is a connected graph with least eigenvalue greater than or equal to −2 which is not a generalized line graph. A generalized exceptional graph is a graph with least eigenvalue greater than or equal to −2 in which at least one component is an exceptional graph.

An important graph invariant is the star value S of an L-graph G. It is defined by

S = \frac{(−1)^{n}}{(n − k)!}P_{G}^{(n−k)}(−2) = (λ_{1} + 2)(λ_{2} + 2) ⋯ (λ_{k} + 2),

where f^{(p)}(x) denotes the p-th derivative of the function f(x).

Since the characteristic polynomial of a disconnected graph G is equal to the product of characteristic polynomials of its components, the star value of G is the product of star values of components of G as well.

In 1976 the key paper [3] by P.J.Cameron, J.M.Goethals, J.J.Seidel and E.E.Shult introduced root systems into the study of graphs with least eigenvalue −2. These graphs can be represented by sets of vectors at 60 or 90 degrees via the corresponding Gram matrices. Maximal sets of lines through the origin with such mutual angles are closely related to the root systems known from the theory of Lie algebras. Using such a geometrical characterization one can show that graphs in question are either generalized line graphs (representable in the root system D_{n} for some n) or exceptional graphs (representable in the exceptional root system E_{8}). The main result is that an exceptional graph can be represented in the exceptional root system E_{8}. In particular, it is proved in this way that an exceptional graph has at most 36 vertices and each vertex has degree at most 28.

Much information on these problems can be found in the books [1], [4], [7], [6], [14], in the expository papers [2], [5] and in the new book [15].

4. Table of cospectral graphs

Before presenting some details from our table of cospectral L–graphs we shall give some definitions.

If the set of graphs {G_{1}, G_{2}, …, G_{k}} is a SING and if G is any connected graph, then the set {G_{1} ∪G, G_{2} ∪G, …, G_{k} ∪G} is also a SING. Each graph in the later SING has a component isomorphic to a fixed graph (to the graph G).

A SING S is called reducible if each graph in S contains a component isomorphic to a fixed graph. Otherwise, S is called irreducible.

A SING is called complete if no graph outside the SING is cospectral to graphs from the SING; otherwise the SING is called incomplete. The SINGs whose members belong to a set X of graphs are called X–SINGs.

The table of cospectral graphs from this paper contains irreducible SINGs in which graphs have the least eigenvalue at least −2 and the number of vertices n is at most 8.

The next table gives some statistic of SINGs.

n 5 6 7  8
all SINGs 1 5 54 829
L-SINGs 1 5 32 198
irreducible L-SINGs 1 4 28 168

Our table contains 4 + 28 + 168 = 200 irreducible L-SINGs with at most 8 vertices.

Many of the SINGs from our table can be found in already published tables of graphs (cf. [17], [7], [6], [11], [13], [9]).

In the table which follows the SINGs are classified by the number of vertices and by the number of edges. Within a group with fixed numbers of vertices and edges the SINGs are classified lexicographically by their eigenvalues in non-decreasing order (first by non-increasing least eigenvalues, then by the second smallest one, etc.). For each SING, first row contains an identification number, followed by eigenvalues and the star value. Next, a row is related to each member of the SING with exceptions mentioned below. The row first contains the rows of the lower triangle of an adjacency matrix of the graph. In addition, the number of components is given followed by the numbers c_{i}, i = 1, 2, 3 where c_{i} is the number of components with i vertices for i = 1, 2, 3. Further we find a graph classificator: LG for line graphs, GL for proper generalized line graphs and EX for generalized exceptional graphs. For line graphs we come across a B if the root graph is bipartite and NB in the oposite case. In proper generalized line graphs the number of petals is given.

90 D. Cvetković, M. Lepović

To save the space graphs from some SINGs are omitted if they appear in earlier publications. This applies to SINGs consisting of connected graphs on 7 vertices and to SINGs consisting of (connected) exceptional L^{+}–graphs on 8 vertices. Deleted graphs are refered to by their identification numbers in the table of connected graphs on 7 vertices from [6] and in Table A2 of exceptional L^{+}–graphs on 8 vertices. The later table appears also in [13] as Table 1. Identification numbers appear behind the character & for 7 vertex graphs and behind the character # for 8 vertex graphs. A part of information on deleted graphs is given behind the mentioned identification numbers. In deleted 8 vertex graphs the star value is always equal to 1 and therefore omitted.

For a complete version of the table see [10].

A TABLE OF COSPECTRAL GRAPHS WITH LEAST EIGENVALUE AT LEAST −2

***********************************************************************
          Cospectral graphs with 6 vertices
***********************************************************************
4 edges
1.  1.7321  1.0000  0.0000  0.0000 -1.0000 -1.7321  12
0 01 101 0100 00000  2  1 0 0  LG B
0 01 100 0001 00010  2  0 1 0  GL 1
5 edges
2.  2.0000  1.0000  0.0000  0.0000 -1.0000 -2.0000  48
0 01 001 0101 10000  2  0 1 0  LG B
1 10 010 1000 01000  1  0 0 0  GL 2
6 edges
3.  2.5616  1.0000  0.0000 -1.0000 -1.0000 -1.5616  12
0 01 011 0011 10000  2  0 1 0  LG NB
0 01 011 0001 00011  2  1 0 0  LG B
7 edges
4.  2.7093  1.0000  0.1939 -1.0000 -1.0000 -1.9032  3
1 10 100 1100 10100  1  0 0 0  EX
1 10 010 0010 11100  1  0 0 0  EX

***********************************************************************
          Cospectral graphs with 7 vertices
***********************************************************************
5 edges
1.  2.0000  1.0000  0.0000  0.0000  0.0000 -1.0000 -2.0000  96
0 01 001 0101 10000 000000  3  1 1 0  LG B
0 01 100 0001 00010 000100  2  0 1 0  GL 2
0 01 101 0001 00100 000000  2  1 0 0  GL 2
6 edges
2.  2.0000  1.0000  1.0000  0.0000 -1.0000 -1.0000 -2.0000  72
0 01 101 0100 10001 000000  2  1 0 0  LG B
1 10 010 0010 10000 000001  1  0 0 0  EX
3.  2.0000  1.4142  0.0000  0.0000  0.0000 -1.4142 -2.0000  64
0 01 001 0101 10000 000001  2  0 0 1  LG B
1 10 010 0010 01000 001000  1  0 0 0  GL 2
7 edges
4.  2.4383  1.1386  0.6180  0.0000 -0.8202 -1.6180 -1.7566  8
1 10 010 0010 11000 000001  1  0 0 0  LG B
0 01 101 1100 01001 000000  2  1 0 0  LG NB

Sets of cospectral graphs with least eigenvalue 91

5.  2.5616  1.0000  0.0000  0.0000  0.0000 -1.5616 -2.0000  48
0 01 101 1101 10000 000000  2  1 0 0  LG B
1 10 010 1000 01000 110000  1  0 0 0  GL 2
8 edges
6.  2.7093  1.4142  0.1939  0.0000 -1.0000 -1.4142 -1.9032  4 &92-93 GL 1 GL 1
7.  2.4728  1.4626  0.6180  0.0000 -1.0000 -1.6180 -1.9354  2 &62-63 EX EX
8.  2.7649  1.2395  0.3257  0.0000 -1.0000 -1.3746 -1.9555  2 &98-99 EX EX
9.  2.8136  1.0000  0.5293  0.0000 -1.0000 -1.3429 -2.0000  48
0 01 101 1101 01001 000000  2  1 0 0  LG B
1 10 010 0010 10000 111000  1  0 0 0  EX
10.  2.7321  1.4142  0.0000  0.0000 -0.7321 -1.4142 -2.0000  48
0 01 101 1101 01100 000000  2  1 0 0  LG B
1 10 010 1000 01000 101010  1  0 0 0  GL 2
11.  2.9032  0.8061  0.0000  0.0000  0.0000 -1.7093 -2.0000  32
1 10 010 1000 11000 110000  1  0 0 0  GL 2
0 01 101 1101 00011 000000  2  1 0 0  GL 1
9 edges
12.  3.2361  0.6180  0.6180  0.0000 -1.2361 -1.6180 -1.6180  8
1 10 010 1100 00001 110010  1  0 0 0  LG B
0 01 101 0011 11110 000000  2  1 0 0  LG NB
13.  2.8162  1.3666  0.6927 -0.2256 -1.0000 -1.7555 -1.8944  2 &148-149 EX EX
14.  3.0569  1.0661  0.6180 -0.4041 -0.7855 -1.6180 -1.9334  2 &197-198 EX EX
15.  3.2361  1.0000  0.0000  0.0000 -1.0000 -1.2361 -2.0000  48
0 01 011 0011 01011 100000  2  0 1 0  LG NB
0 01 101 1101 10011 000000  2  1 0 0  LG B
16.  2.8608  1.2541  0.6180  0.0000 -1.1149 -1.6180 -2.0000  28 &152-153 LG B GL 1
17.  2.7757  1.5892  0.2763  0.0000 -1.0000 -1.6412 -2.0000  28 &146-147 LG B LG B
10 edges
18.  3.4114  1.1172  0.3513 -0.5571 -1.0000 -1.3792 -1.9437  2 &343-344 EX EX
19.  3.3571  1.3701  0.2230 -1.0000 -1.0000 -1.0000 -1.9502  2 &339-340 EX EX
11 edges
20.  3.6147  1.0999  0.3309 -0.4807 -1.0000 -1.6603 -1.9045  2 &373-374 EX EX
21.  3.7785  0.7108  0.0000  0.0000 -1.0000 -1.4893 -2.0000  32
0 01 011 0011 01011 000111  2  1 0 0  LG NB
1 10 100 1000 11100 111001  1  0 0 0  GL 2
22.  3.4893  1.2892  0.0000  0.0000 -1.0000 -1.7785 -2.0000  16 &437-439 LG NB LG NB GL 2
23.  3.5366  1.0000  0.3068  0.0000 -1.0000 -1.8434 -2.0000  12 &449-450 EX EX
12 edges
24.  3.8284  0.6180  0.6180  0.0000 -1.6180 -1.6180 -1.8284  2 &588-589 EX EX
25.  3.6458  1.0000  1.0000 -1.0000 -1.0000 -1.6458 -2.0000  18 &542-543 EX EX
26.  3.8154  1.0607  0.0000  0.0000 -1.1362 -1.7398 -2.0000  16 &586-587 LG NB GL 1
13 edges
27.  3.9832  1.0000  0.1995  0.0000 -1.4687 -1.7140 -2.0000  12 &672-673 EX EX
15 edges
28.  4.3723  1.0000  0.0000  0.0000 -1.3723 -2.0000 -2.0000  48 &782-783 LG NB LG NB

***********************************************************************
          Cospectral graphs with 8 vertices
***********************************************************************
6 edges
1.  1.8478  1.4142  0.7654  0.0000  0.0000 -0.7654 -1.4142 -1.8478  16
0 01 101 0100 00001 000001 0000000  2  1 0 0  LG B
0 01 100 0001 00001 001000 0000100  2  0 0 1  GL 1
2.  2.0000  1.0000  1.0000  0.0000  0.0000 -1.0000 -1.0000 -2.0000  144
0 01 001 0101 10000 000000 0000001  3  0 2 0  LG B
0 01 101 0100 10001 000000 0000000  3  2 0 0  LG B
0 01 100 0001 00001 000010 0001000  2  0 1 0  GL 2
0 01 101 0100 00100 000001 0000000  2  1 0 0  EX

3.  2.0000  1.4142  0.0000  0.0000  0.0000  0.0000 -1.4142 -2.0000  128
0 01 001 0101 10000 000001 0000000  3  1 0 1  LG B
0 01 100 0001 00100 000100 0001000  2  0 0 1  GL 2
0 01 101 0100 00010 010000 0000000  2  1 0 0  GL 2
7 edges
4.  2.3429  1.4142  0.4707  0.0000  0.0000 -1.0000 -1.4142 -1.8136  16
0 01 101 1001 01000 000010 0000000  2  1 0 0  LG B
0 01 011 1000 00001 000100 0001000  2  0 0 1  GL 1
5.  2.0000  1.6180  0.6180  0.0000  0.0000 -0.6180 -1.6180 -2.0000  80
0 01 001 0101 10000 000001 0000001  2  0 0 0  LG B
1 10 010 0010 00010 001000 0001000  1  0 0 0  GL 2
8 edges
6.  2.6855  1.4142  0.3349  0.0000  0.0000 -1.2713 -1.4142 -1.7491  16
0 01 101 1001 00110 000010 0000000  2  1 0 0  LG B
0 01 011 0011 10000 000001 0001000  2  0 0 1  GL 1
7.  2.6412  1.4142  0.7237  0.0000 -0.5892 -1.0000 -1.4142 -1.7757  16
0 01 011 0011 10000 000001 0000100  2  0 0 1  LG NB
0 01 101 1001 00110 010000 0000000  2  1 0 0  LG B
8.  2.7913  1.0000  0.6180  0.0000  0.0000 -1.0000 -1.6180 -1.7913  12
0 01 011 0011 10000 000100 0010000  2  0 1 0  GL 1
0 01 101 0111 11000 000000 0000000  3  2 0 0  EX
9.  2.3429  2.0000  0.4707  0.0000 -1.0000 -1.0000 -1.0000 -1.8136  16
0 01 011 1000 10001 000101 0000000  2  1 0 0  LG B
0 01 011 1000 10001 000001 0000010  2  0 0 1  GL 1
10.  2.5554  1.1946  0.7799  0.0000  0.0000 -0.8911 -1.7177 -1.9210  4
1 10 010 0010 11000 000001 0100000  1  0 0 0  GL 1
0 01 101 1100 01001 000010 0000000  2  1 0 0  EX
11.  2.4728  1.4626  0.6180  0.0000  0.0000 -1.0000 -1.6180 -1.9354  4
1 10 010 0010 00010 001000 1010000  1  0 0 0  GL 1
1 10 010 0010 01000 101000 0000001  1  0 0 0  GL 1
0 01 101 1100 00001 000011 0000000  2  1 0 0  EX
0 01 101 1100 01001 000100 0000000  2  1 0 0  EX
12.  2.3920  1.5739  0.6852  0.2715 -0.5010 -1.0000 -1.4339 -1.9877  #6-7
13.  2.7321  1.0000  1.0000  0.0000 -0.7321 -1.0000 -1.0000 -2.0000  108
0 01 011 0011 10000 000010 0000100  2  0 1 0  GL 1
0 01 101 1001 00010 000101 0000000  2  1 0 0  EX
14.  2.8136  1.0000  0.5293  0.0000  0.0000 -1.0000 -1.3429 -2.0000  96
0 01 101 1101 01001 000000 0000000  3  2 0 0  LG B
0 01 011 0011 10000 000100 0001000  2  0 1 0  GL 2
0 01 101 0111 01000 000010 0000000  2  1 0 0  EX
15.  2.4812  1.4142  0.6889  0.0000  0.0000 -1.1701 -1.4142 -2.0000  80
0 01 101 1101 00000 000001 0000001  2  0 0 1  LG B
1 10 010 0010 00010 100000 1010000  1  0 0 0  EX
9 edges
16.  2.6588  1.6479  0.8536  0.0000 -0.7492 -1.0000 -1.4737 -1.9373  4
1 10 010 0010 00010 000010 0101010  1  0 0 0  LG NB
1 10 010 0010 01000 001010 1010000  1  0 0 0  GL 1
17.  2.5466  1.5596  0.6180  0.4582 -0.2004 -1.3867 -1.6180 -1.9772  #12-13
18.  2.7741  1.4323  0.7366  0.1853 -0.6028 -1.0000 -1.5415 -1.9841  #22-23
19.  2.7231  1.5257  0.8004  0.1381 -0.7610 -1.0000 -1.4408 -1.9855  #19-20
20.  2.7321  1.4142  1.0000  0.0000 -0.7321 -1.0000 -1.4142 -2.0000  72
0 01 101 1101 01100 000000 0000001  2  0 1 0  LG B
1 10 010 0010 00010 000010 1110000  1  0 0 0  EX
21.  2.8608  1.2541  0.6180  0.0000  0.0000 -1.1149 -1.6180 -2.0000  56
0 01 101 1101 01001 000001 0000000  2  1 0 0  LG B
0 01 101 1100 01001 010010 0000000  2  1 0 0  GL 1
1 10 010 0010 11000 000001 0100010  1  0 0 0  EX
22.  2.4989  1.4959  1.0000  0.4249 -0.7574 -1.0000 -1.6624 -2.0000  48
1 10 010 0010 00010 000010 0010110  1  0 0 0  LG B
1 10 010 0010 00010 000010 0011010  1  0 0 0  EX
23.  2.5806  1.5143  0.7890  0.0000  0.0000 -1.0769 -1.8070 -2.0000  32
1 10 010 0010 00010 000010 1100010  1  0 0 0  LG B
1 10 010 0010 01000 001000 0101100  1  0 0 0  EX
24.  3.0000  1.0000  0.0000  0.0000  0.0000  0.0000 -2.0000 -2.0000  240
0 01 101 1101 11100 000000 0000000  3  2 0 0  LG B
1 10 010 1000 01000 110000 1100000  1  0 0 0  GL 3

10 edges
25.  3.3234  1.4142  0.3579  0.0000 -1.0000 -1.0000 -1.4142 -1.6813  16
0 01 011 0111 00011 100000 0000001  2  0 0 1  LG NB
0 01 101 0011 00111 100100 0000000  2  1 0 0  LG B
26.  3.1819  1.2470  1.0000 -0.4450 -0.5936 -1.0000 -1.5884 -1.8019  9
1 10 010 0010 00010 110000 1100001  1  0 0 0  LG B
0 01 101 0111 10011 000000 0000001  2  0 1 0  EX
27.  3.0278  1.4429  0.8317  0.0000 -0.6668 -1.0000 -1.7668 -1.8687  4
1 10 010 0010 00010 000010 1111000  1  0 0 0  LG NB
1 10 010 0010 01010 110000 1100000  1  0 0 0  GL 1
28.  3.3132  0.8693  0.6180  0.0000  0.0000 -1.2727 -1.6180 -1.9098  4
1 10 010 1100 00001 100000 1100100  1  0 0 0  GL 1
0 01 101 0011 11110 000001 0000000  2  1 0 0  EX
29.  2.9107  1.7994  0.6180  0.0000 -0.7994 -1.0000 -1.6180 -1.9107  4
1 10 010 0010 11000 000001 1010100  1  0 0 0  LG NB
0 01 101 0111 11000 100001 0000000  2  1 0 0  EX
30.  2.9881  1.5670  0.7685  0.0000 -0.5905 -1.2668 -1.5544 -1.9118  4
1 10 010 0010 00010 000010 1101010  1  0 0 0  LG NB
1 10 010 0010 01000 110000 0101010  1  0 0 0  GL 1
31.  3.2554  1.1980  0.6180  0.0000 -0.5345 -1.0000 -1.6180 -1.9188  4
1 10 010 0010 01000 110000 1100001  1  0 0 0  GL 1
0 01 011 0001 00011 000101 0001001  2  1 0 0  EX
32.  2.7245  2.1364  0.4982  0.0000 -1.0000 -1.0000 -1.4310 -1.9280  4
1 10 010 0010 00010 101000 0101010  1  0 0 0  LG NB
1 10 010 0010 01000 001010 0101010  1  0 0 0  GL 1
33.  3.1843  1.5088  0.4170  0.0000 -0.6987 -1.0000 -1.4783 -1.9330  4
1 10 010 0010 01000 101000 1010001  1  0 0 0  GL 1
0 01 101 0111 10010 000110 0000000  2  1 0 0  EX
34.  2.9028  1.4315  0.7148  0.2910 -0.2462 -1.3252 -1.8115 -1.9572  #38-39
35.  3.1215  1.2470  0.5477  0.2974 -0.4450 -1.0000 -1.8019 -1.9666  #55-56
36.  3.0625  1.3611  0.7668  0.1388 -0.6830 -1.0000 -1.6690 -1.9772  #51-52
37.  3.0587  1.4263  0.6180  0.1901 -0.5164 -1.1804 -1.6180 -1.9783  #49-50
38.  3.0259  1.4880  0.6966  0.1395 -0.6087 -1.2800 -1.4804 -1.9810  #47-48
39.  2.9139  1.7891  0.5850  0.1163 -1.0000 -1.0000 -1.4213 -1.9830  #44-45
40.  3.0000  2.0000  0.0000  0.0000 -1.0000 -1.0000 -1.0000 -2.0000  80
0 01 101 0111 10010 100001 0000000  2  1 0 0  LG NB
0 01 011 0111 10000 000001 1000001  2  0 0 0  LG B
0 01 011 1000 10001 000011 0000110  2  0 0 1  GL 1
41.  3.2361  1.4142  0.0000  0.0000  0.0000 -1.2361 -1.4142 -2.0000  64
0 01 011 0011 01011 100000 0000001  2  0 0 1  LG NB
0 01 011 0001 00011 000101 0011000  2  1 0 0  GL 2
42.  3.2814  1.0000  0.7719  0.0000 -0.5125 -1.0000 -1.5408 -2.0000  60
0 01 011 0011 00011 000110 1000000  2  0 1 0  GL 1
0 01 101 0111 00011 000011 0000000  2  1 0 0  EX
43.  3.0664  1.2222  1.0000  0.0000 -0.6522 -1.0000 -1.6364 -2.0000  48
0 01 101 0111 01001 100001 0000000  2  1 0 0  LG NB
1 10 010 0010 10000 000001 1111000  1  0 0 0  EX
44.  3.3234  1.0000  0.3579  0.0000  0.0000 -1.0000 -1.6813 -2.0000  48
1 10 010 1000 01000 110000 1100001  1  0 0 0  GL 2
0 01 011 0011 01011 100000 0001000  2  0 1 0  GL 2
0 01 011 0011 00011 000101 0001000  2  1 0 0  EX
45.  2.9032  1.4142  0.8061  0.0000  0.0000 -1.4142 -1.7093 -2.0000  32
1 10 010 0010 00010 000010 0111100  1  0 0 0  LG B
0 01 101 1101 01100 100001 0000000  2  1 0 0  LG NB
46.  2.8136  1.7321  0.5293  0.0000  0.0000 -1.3429 -1.7321 -2.0000  32
1 10 010 0010 00010 101000 1100010  1  0 0 0  LG B
1 10 010 0010 00010 101000 0101001  1  0 0 0  LG B
47.  2.8681  1.4537  0.7742  0.4678 -0.6535 -1.1545 -1.7558 -2.0000  32
1 10 010 0010 00010 000010 1011010  1  0 0 0  LG B
1 10 010 0010 00010 000010 1010110  1  0 0 0  EX
48.  3.1488  1.1784  0.5525  0.0000  0.0000 -1.0903 -1.7895 -2.0000  32
0 01 101 1101 01001 000110 0000000  2  1 0 0  GL 1
1 10 010 0010 10000 110000 1110000  1  0 0 0  EX
49.  2.8422  1.5069  1.0000  0.0000 -0.5069 -1.0000 -1.8422 -2.0000  24
1 10 010 0010 00010 001000 0010111  1  0 0 0  GL 1
1 10 010 0010 00010 000010 0101110  1  0 0 0  EX
1 10 010 0010 10000 010100 0011001  1  0 0 0  EX
50.  3.1774  1.0000  0.6784  0.0000  0.0000 -1.0000 -1.8558 -2.0000  24
1 10 010 1100 00001 110000 1000100  1  0 0 0  EX
0 01 101 1101 11001 000001 0000000  2  1 0 0  EX
51.  3.0000  1.0000  1.0000  0.0000  0.0000 -1.0000 -2.0000 -2.0000  180
0 01 101 1101 11100 000000 0000001  2  0 1 0  LG B
0 01 101 1101 01001 100001 0000000  2  1 0 0  LG B
1 10 010 0010 10000 000001 1011010  1  0 0 0  EX

11 edges
52.  3.2959  1.2470  0.9362  0.0000 -0.4450 -1.4789 -1.7532 -1.8019  4
1 10 010 0010 00010 110000 1111000  1  0 0 0  LG NB
0 01 101 0111 10011 110000 0000000  2  1 0 0  EX
53.  3.1774  1.7321  0.6784  0.0000 -1.0000 -1.0000 -1.7321 -1.8558  4
1 10 010 1010 01010 110000 1100000  1  0 0 0  GL 1
0 01 101 0111 11000 100101 0000000  2  1 0 0  EX
54.  3.2703  1.4142  0.6180  0.4053 -0.8079 -1.4142 -1.6180 -1.8676  4
1 10 010 0010 00010 101000 1110100  1  0 0 0  LG NB
1 10 010 0010 00010 101000 1010011  1  0 0 0  LG NB
55.  3.4467  1.2170  0.7331  0.0000 -0.8114 -1.0000 -1.7043 -1.8812  4
1 10 010 0010 11000 000001 1101010  1  0 0 0  LG NB
0 01 101 0111 01101 100001 0000000  2  1 0 0  EX
56.  3.3906  1.4983  0.5423  0.0000 -1.0000 -1.0000 -1.5177 -1.9135  4
1 10 010 0010 00010 101000 1010101  1  0 0 0  LG NB
1 10 010 1000 01010 110000 1100001  1  0 0 0  GL 1
57.  3.1211  1.4975  0.8466  0.1241 -0.4072 -1.3978 -1.8473 -1.9369  #73-74
58.  3.2620  1.5763  0.4923  0.1545 -0.7247 -1.0000 -1.7990 -1.9614  #89-90
59.  2.8950  2.0306  0.7316  0.0672 -1.0000 -1.0000 -1.7622 -1.9623  #63-64
60.  3.2084  1.6723  0.6180  0.0944 -1.0000 -1.0000 -1.6180 -1.9750  #83-84
61.  3.4122  1.4549  0.3966  0.1758 -1.0000 -1.0000 -1.4585 -1.9811  #101-102
62.  3.4142  1.4142  0.5858  0.0000 -1.0000 -1.0000 -1.4142 -2.0000  56
0 01 101 1101 10011 010010 0000000  2  1 0 0  LG B
1 10 010 0010 00010 101000 1110001  1  0 0 0  EX
63.  3.5289  0.8326  0.6180  0.0000  0.0000 -1.3615 -1.6180 -2.0000  40
0 01 101 0011 11110 000101 0000000  2  1 0 0  GL 1
1 10 010 1100 00001 110000 1100100  1  0 0 0  EX
64.  3.3615  1.1674  0.6180  0.0000  0.0000 -1.5289 -1.6180 -2.0000  32
1 10 010 0010 11000 000001 1100110  1  0 0 0  LG B
0 01 101 1101 11001 100001 0000000  2  1 0 0  LG NB
65.  3.0594  1.5994  0.9045  0.2491 -0.8195 -1.3361 -1.6568 -2.0000  32
1 10 010 0010 00010 101000 0111100  1  0 0 0  LG B
1 10 010 0010 00010 101000 0011011  1  0 0 0  EX
66.  3.2647  1.5378  0.6491  0.0000 -0.7013 -1.0000 -1.7503 -2.0000  32
0 01 101 1101 11001 001100 0000000  2  1 0 0  LG NB
1 10 010 0010 10000 010100 1111000  1  0 0 0  EX
67.  3.1249  1.4142  1.0000  0.0000 -0.3633 -1.4142 -1.7616 -2.0000  24
1 10 010 0010 00010 101000 1010110  1  0 0 0  EX
1 10 010 0010 00010 101000 0011101  1  0 0 0  EX
68.  3.3839  1.0000  0.7424  0.0000  0.0000 -1.3279 -1.7985 -2.0000  24
1 10 010 1000 01000 110000 1111000  1  0 0 0  EX
0 01 101 1101 11001 000110 0000000  2  1 0 0  EX
69.  3.0600  1.8275  0.2920  0.0000  0.0000 -1.3102 -1.8694 -2.0000  16
1 10 010 0010 01000 010101 1100100  1  0 0 0  GL 1
1 10 010 0010 01000 101000 0101011  1  0 0 0  GL 1
70.  3.3707  1.2402  0.4369  0.0000  0.0000 -1.1601 -1.8877 -2.0000  16
1 10 010 0010 01000 110000 1100101  1  0 0 0  GL 1
1 10 010 1000 10100 110000 1110000  1  0 0 0  EX
71.  3.1847  1.3022  0.6993  0.5041 -0.6307 -1.1166 -1.9428 -2.0000  8
1 10 010 0010 00010 010010 1110001  1  0 0 0  EX
1 10 010 0010 00010 100000 1011011  1  0 0 0  EX
72.  3.0772  1.7151  0.7055  0.0000 -0.5520 -1.0000 -1.9459 -2.0000  8
1 10 010 0010 10000 010100 1100110  1  0 0 0  EX
1 10 010 0010 10000 010100 1011010  1  0 0 0  EX
73.  3.3429  1.4707  0.0000  0.0000  0.0000 -0.8136 -2.0000 -2.0000  176
1 10 010 0010 01000 001000 1111010  1  0 0 0  GL 2
1 10 010 1000 01000 101010 1010100  1  0 0 0  GL 3
74.  3.2361  1.0000  1.0000  0.0000  0.0000 -1.2361 -2.0000 -2.0000  144
0 01 101 1101 11100 100001 0000000  2  1 0 0  LG B
1 10 010 0010 10000 001100 1110001  1  0 0 0  EX
12 edges
75.  3.6458  2.0000  0.0000 -1.0000 -1.0000 -1.0000 -1.0000 -1.6458  16
0 01 011 0111 00001 000011 0000111  2  1 0 0  LG B
0 01 011 0111 00111 100000 1000001  2  0 0 1  GL 1
76.  3.8284  0.6180  0.6180  0.0000  0.0000 -1.6180 -1.6180 -1.8284  4
1 10 010 1100 00001 110010 1100100  1  0 0 0  GL 1
0 01 011 0111 00011 001010 0100100  2  1 0 0  EX
0 01 101 0011 11110 001101 0000000  2  1 0 0  EX
77.  3.6254  1.3337  0.6180  0.0000 -0.5865 -1.5349 -1.6180 -1.8378  4
1 10 010 0010 11000 000001 1110110  1  0 0 0  LG NB
0 01 101 0111 10011 010011 0000000  2  1 0 0  EX

78.  3.7759  1.1619  0.4209  0.0000 -0.5478 -1.2503 -1.6984 -1.8623  4
1 10 010 0010 11000 110000 1100011  1  0 0 0  GL 1
0 01 011 0111 00011 000011 0010100  2  1 0 0  EX
79.  3.5551  1.5695  0.7271 -0.3166 -1.0000 -1.0000 -1.6672 -1.8680  4
1 10 010 0010 00010 001010 1110101  1  0 0 0  LG NB
1 10 010 1100 00001 101000 1101100  1  0 0 0  LG NB
80.  3.5176  1.7640  0.3619  0.0000 -1.0000 -1.2800 -1.4704 -1.8931  4
1 10 010 0010 11000 101000 1101010  1  0 0 0  LG NB
1 10 010 1000 11000 101010 1100010  1  0 0 0  GL 1
81.  3.7161  1.4683  0.2514  0.0000 -1.0000 -1.0000 -1.5313 -1.9044  4
1 10 010 0010 01000 010101 0101011  1  0 0 0  GL 1
0 01 011 0111 00011 000011 0000101  2  1 0 0  EX
82.  3.4046  2.0530  0.4112 -0.4987 -1.0000 -1.0000 -1.4642 -1.9058  4
1 10 010 0010 01010 101000 1010101  1  0 0 0  LG NB
1 10 010 0010 11000 101010 1100010  1  0 0 0  LG NB
83.  3.3086  1.3815  1.2470 -0.2210 -0.4450 -1.5367 -1.8019 -1.9324  #116-117
84.  3.4857  1.4233  0.7799  0.0774 -0.7549 -1.2556 -1.8076 -1.9483  #134-135
85.  3.6166  1.4204  0.4756  0.1246 -1.0000 -1.0000 -1.6670 -1.9703  #154-156
86.  3.6432  1.2526  0.6180  0.1166 -0.7232 -1.3188 -1.6180 -1.9704  #159-160
87.  3.5699  1.6019  0.3587  0.1369 -1.0000 -1.2571 -1.4337 -1.9765  #150-151
88.  3.4298  2.0130  0.3640 -0.4322 -1.0000 -1.0000 -1.3951 -1.9795  #146-147
89.  3.3651  2.1222  0.4946 -1.0000 -1.0000 -1.0000 -1.0000 -1.9819  #143-144
90.  3.8951  1.0000  0.3973  0.0000 -1.0000 -1.0000 -1.2924 -2.0000  60
0 01 011 0111 00111 000110 1000000  2  0 1 0  GL 1
0 01 011 0111 00011 000111 0000100  2  1 0 0  EX
91.  3.7217  1.5127  0.0000  0.0000 -0.6902 -1.0000 -1.5442 -2.0000  48
0 01 101 0111 10111 100001 0000000  2  1 0 0  LG NB
1 10 010 1000 01000 101010 1010101  1  0 0 0  GL 2
92.  3.4651  1.5096  0.6180  0.3000 -1.0000 -1.2746 -1.6180 -2.0000  32
1 10 010 0010 00010 101010 1010011  1  0 0 0  LG NB
1 10 010 0010 00010 101000 1011011  1  0 0 0  LG B
1 10 010 0010 00010 101000 1111100  1  0 0 0  EX
1 10 010 1000 10100 110000 1101100  1  0 0 0  EX
93.  3.4323  1.6076  0.7627  0.0000 -1.0000 -1.1505 -1.6521 -2.0000  32
1 10 010 0010 01010 110000 1100101  1  0 0 0  LG B
1 10 010 0010 00010 001010 0111101  1  0 0 0  LG B
94.  3.3234  2.0000  0.3579  0.0000 -1.0000 -1.0000 -1.6813 -2.0000  32
1 10 010 0010 01010 110010 0101010  1  0 0 0  LG B
1 10 010 0010 01010 101000 0101011  1  0 0 0  LG B
95.  3.6597  1.1461  0.7357  0.0000 -0.6264 -1.2228 -1.6923 -2.0000  32
0 01 101 1101 11001 010011 0000000  2  1 0 0  LG NB
1 10 010 0010 11000 000001 1111010  1  0 0 0  EX
96.  3.4533  1.5645  0.7380  0.0000 -1.0000 -1.0000 -1.7557 -2.0000  26
1 10 010 0010 00010 001010 1010111  1  0 0 0  EX
1 10 010 0010 01000 001110 1010101  1  0 0 0  EX
97.  3.3298  1.4838  1.0000  0.0000 -0.5288 -1.5081 -1.7768 -2.0000  18
1 10 010 0010 00010 110000 1010111  1  0 0 0  EX
1 10 010 0010 01000 001110 1110100  1  0 0 0  EX
98.  3.3322  1.4142  1.0948  0.0000 -0.6002 -1.4142 -1.8268 -2.0000  16
1 10 010 0010 01000 110000 0111110  1  0 0 0  GL 1
1 10 010 0010 00010 001110 0011011  1  0 0 0  EX
99.  3.2171  1.8041  1.0000 -0.1880 -1.0000 -1.0000 -1.8332 -2.0000  18
1 10 010 0010 00010 001010 0101111  1  0 0 0  EX
1 10 010 1000 01010 101000 0011011  1  0 0 0  EX
100.  3.4275  1.2549  0.7826  0.0000  0.0000 -1.5568 -1.9082 -2.0000  8
1 10 010 0010 00010 001100 0111101  1  0 0 0  EX
1 10 010 0010 01000 010110 1100101  1  0 0 0  EX
101.  3.3117  1.6570  0.6912  0.2728 -1.0000 -1.0000 -1.9327 -2.0000  8
1 10 010 0010 01010 010010 1110001  1  0 0 0  EX
1 10 010 0010 01000 001110 1111000  1  0 0 0  EX
102.  3.5557  1.3471  0.3320  0.0000  0.0000 -1.3007 -1.9340 -2.0000  8
1 10 010 0010 01000 110100 1100101  1  0 0 0  EX
1 10 010 0010 01000 110100 1111000  1  0 0 0  EX
103.  3.5141  1.5720  0.0000  0.0000  0.0000 -1.0861 -2.0000 -2.0000  144
0 01 101 1101 11100 011001 0000000  2  1 0 0  LG B
1 10 010 0010 01000 101010 1110100  1  0 0 0  GL 1
104.  3.4142  1.4142  0.5858  0.0000  0.0000 -1.4142 -2.0000 -2.0000  112
1 10 010 0010 00010 110010 1100011  1  0 0 0  LG B
1 10 010 0010 01000 001000 0111111  1  0 0 0  GL 2
13 edges
105.  3.8455  1.1389  0.6180  0.1424 -0.4862 -1.6180 -1.6959 -1.9447  #212-213
106.  3.7699  1.4880  0.7051 -0.2165 -1.0000 -1.0000 -1.7974 -1.9492  #201-202

107.  3.8964  1.3612  0.6180 -0.2870 -1.0000 -1.0000 -1.6180 -1.9705  #220-221
108.  3.8653  1.4447  0.7318 -0.5857 -1.0000 -1.0000 -1.4806 -1.9753  #217-218
109.  3.9452  1.0856  0.6180  0.0000 -0.7037 -1.3272 -1.6180 -2.0000  32
0 01 101 1101 01111 010011 0000000  2  1 0 0  LG NB
1 10 010 0010 10000 111000 1111001  1  0 0 0  EX
110.  3.6611  1.6057  0.5227  0.0000 -0.4775 -1.5282 -1.7837 -2.0000  16
1 10 010 0010 00010 110010 1101011  1  0 0 0  LG NB
1 10 010 0010 01010 101100 1101001  1  0 0 0  LG NB
111.  3.6196  1.6973  0.6352  0.0000 -1.0000 -1.1176 -1.8344 -2.0000  16
1 10 010 0010 00010 101010 1011011  1  0 0 0  LG NB
1 10 010 0010 01000 001010 0111111  1  0 0 0  GL 1
112.  3.5366  2.0000  0.3068  0.0000 -1.0000 -1.0000 -1.8434 -2.0000  16
1 10 010 0010 01010 101010 1110100  1  0 0 0  LG NB
1 10 010 0010 01010 101010 1011001  1  0 0 0  LG NB
113.  3.6533  1.4345  1.0000 -0.2024 -1.0000 -1.0000 -1.8854 -2.0000  12
1 10 010 0010 00010 001011 1010111  1  0 0 0  EX
1 10 010 0010 01010 001101 1101010  1  0 0 0  EX
114.  3.5383  1.5912  0.7054  0.2598 -0.6677 -1.5327 -1.8943 -2.0000  8
1 10 010 0010 00010 110010 1111010  1  0 0 0  EX
1 10 010 0010 01010 101100 1110010  1  0 0 0  EX
115.  3.6928  1.3254  0.9009  0.0000 -0.7693 -1.2262 -1.9235 -2.0000  8
1 10 010 0010 00010 001110 0111101  1  0 0 0  EX
1 10 010 0010 00010 111000 1111100  1  0 0 0  EX
116.  3.8529  1.1181  0.7045  0.0000 -0.5929 -1.1504 -1.9322 -2.0000  8
1 10 010 1000 10100 101010 1010110  1  0 0 0  EX
1 10 010 0010 10000 110001 1100111  1  0 0 0  EX
117.  4.0000  1.0000  0.0000  0.0000  0.0000 -1.0000 -2.0000 -2.0000  144
0 01 011 0011 01011 011011 1000000  2  0 1 0  LG NB
1 10 010 1000 11000 110000 1101011  1  0 0 0  GL 2
118.  3.7321  1.0000  1.0000  0.2679 -1.0000 -1.0000 -2.0000 -2.0000  117
1 10 010 0010 10000 000001 1111111  1  0 0 0  EX
1 10 100 1100 10100 111000 1000110  1  0 0 0  EX
1 10 010 0010 10000 111000 1111100  1  0 0 0  EX
119.  3.7785  1.0000  0.7108  0.0000  0.0000 -1.4893 -2.0000 -2.0000  96
0 01 101 1101 01111 111000 0000000  2  1 0 0  LG NB
1 10 010 1000 01000 110000 1111110  1  0 0 0  GL 2
14 edges
120.  4.2860  0.8098  0.6180  0.0000 -1.0000 -1.2460 -1.6180 -1.8498  4
1 10 010 1100 00001 110010 1110101  1  0 0 0  LG NB
0 01 101 0011 11110 011111 0000000  2  1 0 0  EX
121.  4.0363  1.4190  0.7396 -0.4803 -1.0000 -1.0000 -1.7640 -1.9507  #269-270
122.  3.9895  1.7321  0.3417 -0.3750 -1.0000 -1.0000 -1.7321 -1.9561  #263-264
123.  4.0507  1.4375  0.3604  0.1094 -1.0000 -1.3407 -1.6605 -1.9569  #272-273
124.  3.9595  1.7980  0.4717 -0.6624 -1.0000 -1.0000 -1.6002 -1.9666  #261-262
125.  4.3723  1.0000  0.0000  0.0000 -1.0000 -1.0000 -1.3723 -2.0000  48
0 01 101 0111 10111 001111 0000000  2  1 0 0  LG NB
0 01 011 0111 00111 010111 1000000  2  0 1 0  GL 2
126.  3.9929  1.1986  0.6180  0.3074 -0.8005 -1.6180 -1.6984 -2.0000  16
1 10 010 0010 11000 000001 1111111  1  0 0 0  EX
1 10 100 1100 10100 111000 1100110  1  0 0 0  EX
127.  4.2015  1.0000  0.5451  0.0000 -1.0000 -1.0000 -1.7466 -2.0000  24
1 10 010 1000 01000 111100 1111001  1  0 0 0  EX
0 01 011 0011 01011 000111 0101010  2  1 0 0  EX
128.  3.9378  1.5264  0.5900  0.0000 -1.0000 -1.2511 -1.8030 -2.0000  16
1 10 010 0010 01000 010101 0111111  1  0 0 0  GL 1
1 10 010 0010 00010 101000 1111111  1  0 0 0  EX
129.  3.6758  1.7321  0.8446  0.0000 -0.7128 -1.7321 -1.8075 -2.0000  8
1 10 010 0010 00010 101011 0101111  1  0 0 0  EX
1 10 010 0010 01010 001101 1111100  1  0 0 0  EX
130.  3.8284  1.6180  0.6180  0.0000 -0.6180 -1.6180 -1.8284 -2.0000  10
1 10 010 0010 01010 010010 1111101  1  0 0 0  EX
1 10 010 0010 01000 001110 1111011  1  0 0 0  EX
131.  3.8519  1.4762  0.7562  0.0000 -0.6274 -1.5808 -1.8760 -2.0000  8
1 10 010 0010 00010 101011 1011011  1  0 0 0  EX
1 10 010 0010 01010 001101 1111001  1  0 0 0  EX
132.  3.8397  1.4910  0.7434  0.1823 -1.0000 -1.3586 -1.8978 -2.0000  8
1 10 010 0010 01010 010010 1111110  1  0 0 0  EX
1 10 010 0010 01000 001110 1110111  1  0 0 0  EX
133.  3.9970  1.2922  0.5713  0.0000 -0.4828 -1.4771 -1.9007 -2.0000  8
1 10 010 0010 10000 110101 1100111  1  0 0 0  EX
1 10 010 0010 00010 110010 1111101  1  0 0 0  EX
1 10 010 0010 10000 110101 1011011  1  0 0 0  EX

134.  4.0048  1.1174  0.6785  0.3012 -0.8581 -1.3351 -1.9087 -2.0000  8
1 10 010 0010 00110 101001 1110011  1  0 0 0  EX
1 10 010 1000 10100 111000 1111010  1  0 0 0  EX
135.  3.9208  1.6847  0.3153  0.0000 -1.0000 -1.0000 -1.9208 -2.0000  8
1 10 010 0010 01010 110010 1101011  1  0 0 0  EX
1 10 010 0010 01010 101100 1101011  1  0 0 0  EX
1 10 010 1000 01010 111000 1111010  1  0 0 0  EX
136.  4.0000  1.0000  1.0000  0.0000 -1.0000 -1.0000 -2.0000 -2.0000  108
1 10 010 1000 10100 100010 1011111  1  0 0 0  EX
1 10 010 1000 01000 111100 1100111  1  0 0 0  EX
1 10 010 0010 00110 111000 1110011  1  0 0 0  EX
137.  3.6813  1.6421  1.0000  0.0000 -1.0000 -1.3234 -2.0000 -2.0000  84
1 10 010 0010 01010 110010 0111110  1  0 0 0  LG B
1 10 010 0010 01010 101100 0111110  1  0 0 0  LG B
15 edges
138.  4.2067  1.3376  0.6180  0.0552 -1.0000 -1.6180 -1.6708 -1.9286  #305-306
139.  4.2347  1.6565  0.4383 -0.6926 -1.0000 -1.0000 -1.6798 -1.9570  #314-315
140.  4.0890  1.6512  0.3331  0.0000 -0.5880 -1.6348 -1.8505 -2.0000  8
1 10 010 0010 01010 110010 1111101  1  0 0 0  EX
1 10 010 0010 01010 101100 1111101  1  0 0 0  EX
1 10 010 1000 01010 101110 1111001  1  0 0 0  EX
141.  4.1903  1.2733  1.0000 -0.6051 -1.0000 -1.0000 -1.8585 -2.0000  12
1 10 010 0010 00011 111100 1111001  1  0 0 0  EX
1 10 010 1000 10100 110010 1111011  1  0 0 0  EX
142.  4.1369  1.1785  0.8447  0.1820 -0.9159 -1.5669 -1.8593 -2.0000  8
1 10 010 0010 00110 111010 1110011  1  0 0 0  EX
1 10 010 0010 01000 111100 0111111  1  0 0 0  EX
143.  4.1055  1.4142  0.7765  0.0000 -1.0000 -1.4142 -1.8820 -2.0000  8
1 10 010 0010 00010 101011 1111101  1  0 0 0  EX
1 10 010 0010 01010 001101 0111111  1  0 0 0  EX
144.  4.2190  1.4142  0.3641  0.0000 -0.6866 -1.4142 -1.8964 -2.0000  8
1 10 100 1100 10100 111010 1110010  1  0 0 0  EX
1 10 010 0010 11000 111010 1100111  1  0 0 0  EX
145.  4.0398  1.6616  0.8991 -0.6961 -1.0000 -1.0000 -1.9043 -2.0000  8
1 10 010 0010 01010 001111 1101011  1  0 0 0  EX
1 10 010 0010 01010 111000 1111110  1  0 0 0  EX
146.  4.2620  1.0000  0.5665  0.3512 -1.0000 -1.1796 -2.0000 -2.0000  93
1 10 010 0010 10000 111000 1111111  1  0 0 0  EX
1 10 100 1100 10100 111000 1110110  1  0 0 0  EX
147.  4.0280  1.2953  1.0000  0.0000 -0.7151 -1.6082 -2.0000 -2.0000  60
1 10 010 0010 00011 111100 0111101  1  0 0 0  LG NB
1 10 010 0010 00110 111000 1111110  1  0 0 0  EX
148.  3.8781  1.5834  1.0000  0.0000 -0.7704 -1.6911 -2.0000 -2.0000  48
1 10 010 0010 01011 101100 0111110  1  0 0 0  LG NB
1 10 010 0010 01011 111010 1010110  1  0 0 0  LG NB
16 edges
149.  4.5505  1.4903  0.3648 -1.0000 -1.0000 -1.0000 -1.4385 -1.9671  #360-361
150.  4.5616  0.6180  0.6180  0.4384 -1.0000 -1.6180 -1.6180 -2.0000  16
1 10 010 1100 00001 110010 1111111  1  0 0 0  EX
1 10 010 1100 11000 110010 1111101  1  0 0 0  EX
1 10 100 1000 11100 110101 1011011  1  0 0 0  EX
151.  4.3250  1.4781  0.6952 -0.1629 -1.0000 -1.5313 -1.8041 -2.0000  10
1 10 010 0010 00010 101011 1111111  1  0 0 0  EX
1 10 010 0010 01010 001101 1111111  1  0 0 0  EX
152.  4.3630  1.2628  0.6180  0.1989 -1.0000 -1.6180 -1.8248 -2.0000  8
1 10 010 0010 00010 011110 1111111  1  0 0 0  EX
1 10 010 0010 01000 011111 1111101  1  0 0 0  EX
153.  4.3510  1.3105  0.7352  0.0000 -1.0000 -1.5518 -1.8448 -2.0000  8
1 10 010 0010 01011 110101 1100111  1  0 0 0  EX
1 10 010 0010 11000 110011 1111101  1  0 0 0  EX
154.  4.3186  1.5918  0.4244  0.0000 -1.0000 -1.4726 -1.8622 -2.0000  8
1 10 010 0010 01010 110010 1111111  1  0 0 0  EX
1 10 010 1000 10100 110110 1011111  1  0 0 0  EX
1 10 010 0010 01010 101100 1111111  1  0 0 0  EX
155.  4.3135  1.4674  0.8661 -0.4378 -1.0000 -1.3312 -1.8780 -2.0000  8
1 10 010 0010 11000 011110 1111101  1  0 0 0  EX
1 10 010 0010 01010 111100 0111111  1  0 0 0  EX
156.  4.5443  1.1412  0.3561  0.0000 -1.0000 -1.1374 -1.9043 -2.0000  8
1 10 010 1000 10100 101011 1011111  1  0 0 0  EX
1 10 100 1100 10100 111010 1100111  1  0 0 0  EX

157.  4.5188  1.3907  0.0000  0.0000 -1.0000 -1.0000 -1.9095 -2.0000  8
1 10 010 0010 11010 110011 1101011  1  0 0 0  EX
1 10 010 0010 11010 111100 1101011  1  0 0 0  EX
17 edges
158.  4.7443  0.8568  0.6180  0.0729 -1.0000 -1.6180 -1.7979 -1.8761  #383-384
159.  4.6569  1.1636  0.5313  0.0000 -1.0000 -1.5027 -1.8491 -2.0000  8
1 10 010 0010 11000 110011 1111111  1  0 0 0  EX
1 10 010 1000 10100 101111 1111011  1  0 0 0  EX
160.  4.5047  1.0000  1.0000  0.1354 -1.0000 -1.6400 -2.0000 -2.0000  45
1 10 010 0010 00011 011110 1111111  1  0 0 0  EX
1 10 010 0010 00110 111110 0111111  1  0 0 0  EX
18 edges
161.  4.9291  0.8145  0.6180  0.0000 -1.0000 -1.6180 -1.7436 -2.0000  10
1 10 010 1100 00001 111110 1111111  1  0 0 0  EX
1 10 010 1100 11000 111110 1111101  1  0 0 0  EX
162.  4.8260  1.3639  0.2110  0.0000 -1.0000 -1.5958 -1.8051 -2.0000  8
1 10 010 0010 11010 110011 1111111  1  0 0 0  EX
1 10 010 1000 10101 111101 1011111  1  0 0 0  EX
1 10 010 0010 11010 111100 1111111  1  0 0 0  EX
163.  4.7016  1.0000  1.0000  0.0000 -1.0000 -1.7016 -2.0000 -2.0000  36
1 10 010 0010 10110 011110 1111111  1  0 0 0  EX
1 10 010 1011 01110 110110 1101101  1  0 0 0  EX
1 10 010 0010 11100 111110 0111111  1  0 0 0  EX
164.  4.6458  1.7321  0.0000  0.0000 -0.6458 -1.7321 -2.0000 -2.0000  36
1 10 010 1010 01110 101110 1111011  1  0 0 0  EX
1 10 010 1010 01110 111101 1110110  1  0 0 0  EX
19 edges
165.  5.0884  1.0883  0.2467  0.0000 -1.0000 -1.6693 -1.7541 -2.0000  8
1 10 010 0010 10110 111101 1111111  1  0 0 0  EX
1 10 010 1000 10111 111101 1111011  1  0 0 0  EX
166.  4.9095  1.6093  0.0000  0.0000 -1.0000 -1.5188 -2.0000 -2.0000  48
1 10 010 1010 01110 101110 1111111  1  0 0 0  LG NB
1 10 010 1010 11010 111110 1011111  1  0 0 0  LG NB
20 edges
167.  5.2588  1.0000  0.2518  0.0000 -1.0000 -1.5106 -2.0000 -2.0000  48
1 10 010 0010 10110 111111 1111111  1  0 0 0  EX
1 10 010 1000 10111 111101 1111111  1  0 0 0  EX
22 edges
168.  5.6056  1.0000  0.0000  0.0000 -1.0000 -1.6056 -2.0000 -2.0000  36
1 10 010 1011 01110 111111 1111111  1  0 0 0  EX
1 10 010 1011 11011 111110 1111111  1  0 0 0  EX
***********************************************************************

5. Some observations

Given two graphs G and H, we shall say that G is smaller than H if |V (G)| < |V (H)| and in the case |V (G)| = |V (H)| if |E(G)| < |E(H)|. Any set of graphs has one or several smallest graphs in the above order of graphs. Since graphs in any SING have the same number of vertices and the same number of edges, we can compare SINGs as well in the above sense.

Cospectral L–graphs could be line graphs, proper generalized line graphs and (generalized) exceptional graphs in all combinations.

The smallest PING without the limitations on the least eigenvalue, which consists of graphs K_{1,4} and C_{4} ∪ K_{1}, is the only one with 5 vertices and belongs to L^{0}. Note that K_{1,4} is a proper GLG while C_{4} ∪ K_{1} is a line graph.

The first PING which appears in the table consists of disconnected graphs K_{1,3} ∪ K_{2}, P_{5} ∪ K_{1} and this is the smallest irreducible PING with such a property.

Although reducible SINGs should not be included in tables like our since they can easily be generated from irreducible ones, reducible SINGs are not quite uninteresting. Namely, although the reducible PINGs, for example, {K_{1,4} ∪ K_{1}, C_{4} ∪ 2K_{1}}, {K_{1,3} ∪ K_{2} ∪ K_{1}, P_{5} ∪ 2K_{1}} have been deleted from the table, the reducible SING {K_{1,4} ∪ K_{2}, C_{4} ∪ K_{1} ∪ K_{2}} appears to be incomplete and can be extended to the triplet of cospectral graphs {K_{1,4} ∪ K_{2}, C_{4} ∪ K_{1} ∪ K_{2}, S_{6} ∪ K_{1}} which does appear in the table! (Here S_{6} is the tree on 6 vertices with largest eigenvalue equal to 2).

PING No. 2 with 7 vertices consists of a line graph and of an exceptional graph. This is the smallest such PING. The line graph is C_{6} ∪ K_{1}; the other is an exceptional tree with largest eigenvalue 2 (and the least eigenvalue −2). In addition, these two graphs are switching equivalent.

Next we note that PING No. 10 with 8 vertices consists of a connected line graph and a generalized exceptional graph (having an isolated vertex) while in the PING No. 22 with the same number of vertices both graphs are connected one being a line graph and the other an exceptional graph. In the later case the least eigenvalue is equal to −2 and one can prove that this is not possible in L^{+}-graphs.

6. The number of petals

Looking at the table of L–SINGs we have realized that the spectrum of a generalized line graph contains some information on the number of petals in the corresponding root graph. This observation has led to the formulation and the proof of Proposition 1 and Theorem 1.

Proposition 1. Let G_{i}, G′_{i} be the B–graphs obtained from the B–graph G by adding at vertex i a pendant edge and a petal, respectively. Then we have

P_{L(G′_{i})}(λ) = −2λP_{L(G_{i})}(λ) − 2λ^{2}P_{L(G)}(λ).

P r o o f. Let x, y be vertices of L(G′_{i}) corresponding to the petal at vertex i of G. In the determinant defining P_{L(G′_{i})}(λ) subtract the entries of the y–row from the x–row and perform the same with the corresponding columns. Then develop the determinant by the x–row.

Theorem 1. The multiplicity of the number 0 in the spectrum of a generalized line graph L(G) is at least the number of petals of G.

P r o o f. To each petal of G Proposition 1 can be applied, yielding a factor λ in the characteristic polynomial of L(G).

However, the number of petals in the root graph is not determined by the spectrum of the corresponding GLG. There are cospectral GLGs with root graphs having different number of petals. The smallest example is just the PING on 5 vertices if we consider a line graph to be a GLG with 0 petals. If we look for such an example with proper GLGs then the PING No. 11 with 7 vertices provides it. Finally, if we want both proper GLGs to be connected, then the PING No. 73 with 8 vertices does the job (2 and 3 petals).

Sometimes it is of interest to recognize a line graph among generalized line graphs.

The following forbidden subgraph characterization is an immediate consequence of the existing results.

Proposition 2. A generalized line graph is a line graph if and only if it does not contain, as an induced subgraph, any of graphs K_{1,3} and K_{3}∇2K_{1}.

P r o o f. Line graphs are characterized by a set B of 9 forbidden subgraphs while generalized line graphs are characterized by a set C of 31 forbidden subgraphs (cf., e.g., [15], Theorems 2.1.3 and 2.3.18). Since C \ B contains just K_{1,3} and K_{3}∇2K_{1} we are done.

Note that K_{1,3} and K_{3}∇2K_{1} are proper generalized line graphs whose root graphs contain exactly one petal. This observation together with Proposition 2 could be used to define an algorithn for determining the number of petals in the root graph of a generalized line graph.

7. Additional observations

As known (cf., e.g., [15]), if G = L(H) the B–graph H is not unique. It can happen that a line graph can be presented as a generalized line graph of a graph with petals. We call such graphs polymorphic generalized line graphs. There are exactly 5 connected polymorphic generalized line graphs (see [15], Theorem 2.3.4). Disconnected polymorphic GLGs either have as a component one of the 5 connected polymorphic GLGs or contain two isolated vertices since 2K_{1} = L(2K_{2}) = L(B_{1}).

Proposition 3. The only regular connected proper generalized line graphs are the cocktail party graphs CP (k), k = 4, 5, . . ..

P r o o f. It is well-known that regular connected generalized line graphs are either line graphs or cocktail party graphs (see, for example, [15], Proposition 1.1.9). The cocktail party graphs CP (k), k = 1, 2, 3 are polymorpic, hence line graphs. For k = 4, 5, … they are not line graphs and the assertion of the lemma follows.

A B–graph is called bipartite if it contains neither odd cycles nor petals.

Theorem 2. Let H be a B–graph with n vertices and m edges. Then the multiplicity of the eigenvalue −2 in L(H) is m − n if H is not bipartite and m − n + 1 if H is bipartite.

This theorem has been proved in [16] for line graphs and in [8] for proper generalized line graphs (see Theorems 2.2.4 and 2.2.8 of [15]. The original results were formulated as two apparently non–related results. Our terminology and notation makes it possible to formulate the theorem as a unique result.

REFERENCES

[1] A. E. B r o u w e r, A. M. C o h e n, A. N e u m a i e r, Distance-Regular Graphs, Springer-Verlag, Berlin, 1989.

[2] F. C. B u s s e m a k e r, A. N e u m a i e r, Exceptional graphs with smallest eigenvalue −2 and related problems, Mathematics of Computation, 59(1992), 583–608.

[3] P. J. C a m e r o n, J. M. G o e t h a l s, J. J. S e i d e l, E. E. S h u l t, Line graphs, root systems, and elliptic geometry, J. Algebra, 43(1976), 305–327.

[4] P. J. C a m e r o n, J. H. v a n L i n t, Designs, Graphs, Codes and Their Links, Cambridge University Press, Cambridge, 1991.

[5] D. C v e t k o v i ć, Graphs with least eigenvalue −2: A historical survey and recent developments in maximal exceptional graphs, Linear Algebra Appl., 356(2002), 189– 210.

[6] D. C v e t k o v i ć, M. D o o b, I. G u t m a n, A. T o r g a š e v, Recent Results in the Theory of Graph Spectra, North-Holland, Amsterdam, 1988.

[7] D. C v e t k o v i ć, M. D o o b, H. S a c h s, Spectra of Graphs, 3rd edition, Johann Ambrosius Barth Verlag, Heidelberg - Leipzig, 1995.

[8] D. C v e t k o v ić, M. D o o b, S. S i m i ć, Generalized line graphs, J. Graph Theory, 5(1981), No.4, 385–399.

[9] D. C v e t k o v i ć, I. G u t m a n, On the spectral structure of graphs having the maximal eigenvalue not greater than two, Publ. Inst. Math. (Beograd), 18(32)(1975), 39–45.

[10] D. C v e t k o v i ć, M. L e p o v i ć, A table of cospectral graphs with least eigenvalue at least −2, http://www.mi.sanu.ac.yu/projects/results1389.htm

[11] D. C v e t k o v i ć, M. L e p o v i ć, P. R o w l i n s o n, S. S i m i ć, A database of star complements of graphs, Univ. Beograd, Publ. Elektrotehn. Fak., Ser. Mat., 9(1998), 103–112.

[12] D. C v e t k o v i ć , M. L e p o v i ć, P. R o w l i n s o n, S. S i m i ć, The maximal exceptional graphs, J. Combinatorial Theory, Ser. B, 86(2002), 347-363.

[13] D. C v e t k o v i ć, M. L e p o v i ć, P. R o w l i n s o n, S. S i m ić, Computer investigations of the maximal exceptional graphs, University of Stirling, Technical Report CSM-160, Stirling, 2001.

[14] D. C v e t k o v i ć, P. R o w l i n s o n, S. K. S i m i ć, Eigenspaces of Graphs, Cambridge University Press, Cambridge, 1997.

[15] D. C v e t k o v i ć, P. R o w l i n s o n, S. K. S i m i ć, Spectral Generalizations of Line Graphs, On Graphs with Least Eigenvalue −2, Cambridge University Press, Cambridge, 2004.

[16] M. D o o b, An interrelation between line graphs, eigenvalues, and matroids, J. Combinatorial Theory, Ser. B, 15(1973), 40–50.

[17] C. D. G o d s i l, B. M c K a y, Some computational results on the spectra of graphs, Combinatorial Mathematics IV, ed. L.R.A.Casse, W.D.Wallis, Springer– Verlag, Berlin–Heidelberg–New York, 1976, 73–92.

[18] W. H a e m e r s, E. S p e n c e, Enumeration of cospectral graphs, Europ. J. Comb., 25(2004), 199–211.

[19] A. J. H o f f m a n, −1 − \sqrt{2} ?, Combinatorial Structures and Their Applications, Proc. of the Calgary Intern. Conf. on Combinatorial Structures and their Applications held at the Univ. of Calgary, June, 1969, ed. R.Guy, H.Hanani, N.Sauer, J.Schönheim, Gordon and Breach, Sci. Publ., Inc., New York - London - Paris, 1970, 173–176.

Faculty of Electrical Engineering, University of Belgrade, P.O.Box 35–54, 11120 Belgrade, Serbia and Montenegro ecvetkod@etf.bg.ac.yu Faculty of Sciences, University of Kragujevac, R. Domanovića 12, 34000 Kragujevac, Serbia and Montenegro lepovic@knez.uis.kg.ac.yu