ARS MATHEMATICA CONTEMPORANEA ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 18 (2020) 105-115 https://doi.org/10.26493/1855-3974.1933.2df (Also available at http://amc-journal.eu) Notes on exceptional signed graphs Zoran Stanic * © Faculty of Mathematics, University of Belgrade, Studentski trg 16, 11 000 Belgrade, Serbia Received 14 February 2019, accepted 25 December 2019, published online 24 September 2020 A connected signed graph is called exceptional if it has a representation in the root system E8, but has not in any Dk. In this study we obtain some properties of these signed graphs, mostly expressed in terms of those that are maximal with a fixed number of eigenvalues distinct from -2. As an application, we characterize exceptional signed graphs with exactly 2 eigenvalues. In some particular cases, we prove the (non-)existence of such signed graphs. Keywords: Adjacency matrix, least eigenvalue, root system, signed line graph, exceptional signed graph, signed graph decomposition. Math. Subj. Class. (2020): 05C22, 05C50 1 Introduction A signed graph G is a pair (G, a), where G = (V, E) is a finite unsigned graph, called the underlying graph, and a: E —> {-1,1} is the signature. The edge set of a signed graph is composed of subsets of positive and negative edges. Throughout the paper we interpret a graph as a signed graph with all the edges being positive. The n x n adjacency matrix Ag of G is obtained from the (0,1)-adjacency matrix of G by reversing the sign of all 1s which correspond to negative edges. The eigenvalues of Ag are real and form the spectrum of G. We establish some properties of exceptional signed graphs. Precisely, we extend some results concerning the particular case of exceptional graphs, which can be found in [3]. It occurs that the 'signed' generalizations of some known theorems have a nice form and give an interesting insight into the nature of signed graphs. We also give a characterization *This research is partially supported by Serbian Ministry of Education, Science and Technological Development, Projects 174012 and 174033. E-mail address: zstanic@math.rs (Zoran Stanic) Abstract ©® This work is licensed under https://creativecommons.org/licenses/by/4.0/ 106 Ars Math. Contemp. 18 (2020) 105-115 of exceptional signed graphs with 2 (distinct) eigenvalues in terms of certain decompositions which are specified in the corresponding section. Some particular exceptional signed graphs with 2 eigenvalues are determined. Sections 2 and 3 are preparatory. In the former we fix some terminology and notation, and in the latter we give a brief review of the root systems with a special emphasis on Dk and E8. Our main contribution is reported in Sections 4 and 5. 2 Preliminaries If the vertices i and j of a signed graph are adjacent, then we write i ~ j; in particular, the existence of a positive (resp. negative) edge between these vertices is designated by i ~ j (resp. i ~ j). The degree of a vertex in a signed graph is equal to the number of edges incident with it. A signed graph is said to be r-regular if the degree of all its vertices is r. The signed graphs G and H are said to be switching equivalent if there exists a set U C V(G), such that H is obtained from G by reversing the sign of every edge with exactly one end in U. Switching equivalent signed graphs share the same underlying graph and the same spectrum. Equivalently, if the vertex labelling of G and H is transferred from their common underlying graph, then they are switching equivalent if there exists a diagonal matrix D of ±1s, such that Ah = D-1AgD. A walk in a signed graph is positive if the number of its negative edges (counted with their multiplicity if there are repeated edges) is not odd. Otherwise, it is negative. In the same way we decide whether a cycle, considered as a subgraph of a signed graph, is positive or negative. A signed doubled graph G is obtained by doubling every edge of a graph G (i.e., a signed graph with positive signature) with a negative edge. In fact, this is a signed multigraph. We proceed by a concept of signed line graphs which is frequently used in spectral considerations, see [2, 5, 8]; a slightly different approach can be found in [10]. For a signed graph G, we introduce the vertex-edge orientation n: V(G) x E(G) —> {1,0, -1} formed by obeying the following rules: (1) n(i, jk) = o if i i {j,k}, (2) n(i, ij) = 1 or n(i, ij) = -1 and (3) n(iij)n(j\ij) = -^(ij). In fact, each edge has two orientations, and thus n is also called a bi-orientation. The vertex-edge incidence matrix Bn is the matrix whose rows and columns are indexed by V(G) and E(G), respectively, in such a way that its (i, e)-entry is equal to n(i, e). The following relation, valid also if multiple edges exist, is well-known: BT Bn = 2/ + Ai(G), where L(G) is taken to be the signed line graph of G. In fact, a signed line graph is a switching class, not a single signed graph, since L(G) depends on orientation. We say that a signed graph is maximal with a fixed property, if it is not an induced subgraph of a signed graph having the same property. Z. Stanic: Notes on exceptional signed graphs 107 3 Root systems A representation of a signed graph G with least eigenvalue > -2 is a mapping f: V(G) Rk, k > 1, such that If S C Rk is the image of f, then we say that G is represented by S. Clearly, A^ + 21 is the Gram matrix of S, so it is positive semidefinite and the least eigenvalue of G is, indeed, > -2. We do not make a difference between the set S and the matrix (also denoted by S) whose columns are the vectors of S. If ei, e2,..., ek are the vectors of the canonical basis of Rk, k > 4, then the root system Dk consists of the vectors (in the context of root systems, they are also known as the roots) ±ei ± ej, for 1 < i < j < k. The root system E8 consists of the 112 roots that also belong to D8 and the additional 128 roots of the form 2 J28=i ±ei, where the number of positive summands is not odd. The root system E7 consists of the 126 roots of E8 orthogonal to a fixed root x g E8, and E6 consists of the 72 roots of E8 orthogonal to a fixed pair of roots x, y g E8, such that x • y = -1. A root system determines a line system, i.e., a system of one-dimensional subspaces generated by the corresponding roots. The definitions of E7 and E6 do not essentially depend on the choice of roots, as different choices produce isometric line systems. For a root system R, a system of positive roots R+ is its subset such that: (1) for ±x g R, exactly one of x, -x belongs to R+ and (2) for x, y g R+, if x + y g R then x + y g R+. Observe that R and R+ produce the same line system. In particular, we shall frequently deal with the systems of positive roots E+ (of Ek, for 6 < k < 8). It is known that every signed line graph has a representation in some Dk [2, 5]. Accordingly, the least eigenvalue of every signed line graph is > -2. A connected signed graph is said to be exceptional if it has a representation in E8, but has not in any Dk. It follows that a connected signed graph is exceptional if and only if it is not a signed line graph, but its least eigenvalue is > -2. For a signed graph G with n vertices and least eigenvalue greater than -2, an extension (or a (-2)-extension) of G is a signed graph with the following properties: (1) its least eigenvalue is equal to -2, (2) it contains G as an induced subgraph and (3) exactly n of its eigenvalues (with possible repetitions) are greater than -2. 4 Properties of exceptional signed graphs We start with the following lemma. 106 Ars Math. Contemp. 18 (2020) 105-115 Lemma 4.1. If a signed graph is represented by S c Rk, then the set S' obtained by reversing the sign of some elements of S represents a switching equivalent signed graph. In particular, signed graphs represented by all the possible sets of positive roots R+ of R (where R stands for any of Dk, E6, E7, E8) are switching equivalent. Proof. Given S = {xi, x2,..., xn} and N C {1,2,..., n}, let S' be obtained by reversing the sign of vectors whose indices belong to N. If S represents a signed graph G, then S' obviously represents some signed graph, say H. Moreover, if D is the diagonal matrix of ±1s with —1 in the ith position if and only if i e N, then Ag + 2I = STS = D-1 S'JS'D = D-1(Ail + 2I)D = D-1Ail D + 2I, giving the first part of the statement. Let R+ be a fixed set of positive roots. If x, y e R+, then xy e { — 1,0,1}, and so R+ indeed represents a signed graph. In addition, any other set of positive roots is obtained by reversing the sign of some roots of R+, and the result follows by the previous part of the proof. □ The previous result can also be proved on the basis of Vijayakumar's [9, Lemma 2.3]. Throughout the remainder of the paper, we do not make a difference between switching equivalent signed graphs; in particular, when we say that some signed graph is unique (for certain property), we always mean that it is unique up to the switching equivalence. The following 3 signed graphs play a significant role in our study: M6 represented by E+, M7 represented by E+ and M8 represented by E+. Each of them is unique (by Lemma 4.1). Their and spectra of the corresponding underlying graphs are given in Table 1. Note that the corresponding underlying graphs are known from literature; for example, they can be met in [3]. Table 1: Spectra of signed graphs M6, M7 and M8. Signed graph Spectrum Spectrum of the underlying graph MM6 [106, (—2)30] [20, 220, (—4)15] M7 [167, (—2)56] [32, 427, (—4)35] M8 [288, (—2)112] [56, 835, (—4)84] We proceed with the following theorem. Theorem 4.2. M8 is the unique maximal exceptional signed graph. Proof. If G is a maximal exceptional signed graph, then it has a representation in E8, and consequently it has a representation in some E+. The maximality of G implies that it is represented by the entire set of positive roots. The uniqueness follows by Lemma 4.1. □ In what follows we prove a sequence of results that give a closer insight into exceptional signed graphs. We start with the following lemma and conclude the section with the forthcoming Theorem 4.8 which, together with Theorem 4.2, gives an interesting generalization of certain results concerning exceptional graphs. Z. Stanic: Notes on exceptional signed graphs 107 Lemma 4.3. Given x, x', y, y' G Eg, such that x • y = —1 and x' • y' = — 1, let E7 and E' stand for the sets of roots of Eg orthogonal to x and y, respectively, and let E6 and E6 stand for the sets of roots of Eg orthogonal to the pair x, y and x', y', respectively. The set of signed graphs with a representation in E7 (resp. E6) is equal to the set of those with a representation in E' (resp. E6). Proof. Let E stand for one of E7 or E6 and E' for a corresponding E' or E'6. If a signed graph G has a representation in E, then A^ + 21 = STS, for some S C E. Observe that an entry of STS is twice the cosine of the angle between the corresponding vectors. Since E and E' determine isometric line systems, there exists S' C E' such that S'TS' = STS, that is G has a representation in E'. □ At this point we need a result of [5]. We restate it in a slightly modified form by putting focus on relations between signed graphs in question. Lemma 4.4. An exceptional signed graph whose least eigenvalue is greater than —2 is (i) one of 32 signed graphs with 6 vertices, (ii) one of 233 signed graphs with 7 vertices or (iii) one of 1242 signed graphs with 8 vertices listed in [5]. Every signed graph of (ii) (resp. (iii)) is a one-vertex extension of some of (i) (resp. (ii)). In [9], Vijayakumar characterized signed graphs represented in Dk, for all k. In particular, the set of connected minimal forbidden subgraphs for signed line graphs has been described. It occurs that they have at most 6 vertices, and all with least eigenvalue greater than — 2 are given in the previous lemma. In addition, we claim that none of them has — 2 as the least eigenvalue. One may confirm this by constructing all the minimal forbidden subgraphs (by following the particular procedure described in [9]) and checking their least eigenvalue. This would be an extensive work, as just in case of graphs there are the 31 minimal forbidden subgraphs [3, p. 35]. We applied a different approach based on the computer search. Namely, we first obtained all the connected signed graphs with at most 6 vertices that are represented in D6 and whose least eigenvalue is —2. This procedure was performed very quickly by computer, as there are just 30 roots in D+. Then we have just checked whether each connected signed graph with at most 6 vertices and least eigenvalue —2 (they can be found at the web page [6]) appears in the list found by computer. We record this as the following lemma. Lemma 4.5. Every signed graph with at most 6 vertices and least eigenvalue —2 has a representation in D6. Here is an immediate consequence. Corollary 4.6. Every exceptional signed graph G with least eigenvalue —2 has at least 7 vertices and contains an exceptional induced subgraph with 6 vertices and least eigenvalue greater than —2. 106 Ars Math. Contemp. 18 (2020) 105-115 Proof. Since G is exceptional, by the mentioned result of [9], it contains a connected induced subgraph, say H, with at most 6 vertices and with no representation in any Dk; in other words, H is an exceptional signed graph. By Lemma 4.5, the least eigenvalue of H is greater than -2. By Lemma 4.4, H has exactly 6 vertices and it is some of signed graphs mentioned in that lemma. □ Similarly to a result concerning graphs (cf. [2]), we have the following. Lemma 4.7. An exceptional signed graph G has between 6 and 8 eigenvalues (with possible repetitions) greater than -2. Proof. By Corollary 4.6, G contains an induced exceptional subgraph with 6 vertices and least eigenvalue greater than -2, which together with the interlacing argument, gives the lower bound. It holds Ag + 2I = STS, where S is obtained by arranging some roots of E8 as its columns. Since the dimension of the linear span of E8 is 8, the rank of Ag + 2I is at most 8, giving the upper bound. □ Theorem 4.8. For 6 < k < 8, Mk is the unique maximal extension of exceptional signed graphs with k vertices and least eigenvalue greater than -2. Proof. Every exceptional signed graph with k (6 < k < 8) vertices and least eigenvalue greater than -2 has a representation in Ek, and also in E+. Clearly, such a signed graph is an induced subgraph of a signed graph represented by the entire set of positive roots. For k = 8, the result follows by Theorem 4.2. For k = 7, assuming to the contrary, we arrive at the existence of an extension, say G, such that Ag + 2I = STS, where S is obtained by arranging some roots of E+ and at least one root, say x, of E+ \ E+ as its columns. Since x • y = 0, for all y G E+, it follows that the rank of Ag + 2I is 8, meaning that 8 eigenvalues (with repetitions) of G are greater than -2, and so G cannot be an extension - a contradiction. For k = 6, the proof is essentially the same. □ In particular case of graphs, there are exactly 473 maximal exceptional graphs, along with a large number of maximal extensions of exceptional graphs with 6 or 7 vertices, as follows by [3, Chapter 6]. On the contrary, the 'signed' generalization reported in Theorems 4.2 and 4.8 has a very simple formulation. 5 Exceptional signed graphs with 2 eigenvalues In [8], we determined all the signed line graphs with 2 eigenvalues. This result is also needed here. Theorem 5.1. A connected signed line graph has 2 eigenvalues if and only if the corresponding signed root graph is switching equivalent to (i) the star Kln-1, (ii) the negative quadrangle or the signed multigraph obtained by inserting the (parallel) negative edge between the vertices of degree 2 of the path P4, (iii) the complete graph Kn or Z. Stanic: Notes on exceptional signed graphs 107 (iv) a signed doubled regular graph with n vertices, in all cases, for n > 3. The next natural step is a determination of exceptional signed graphs with 2 eigenvalues. In the forthcoming Theorem 5.4, we give a characterization of such signed graphs; this result relies on Theorems 5.2 and 5.3. If A is the adjacency matrix of a signed graph with 2 eigenvalues, A and then A2 - (A + ¡)A + A¡I = O. (5.1) It follows that such a signed graph is regular with vertex degree -Aj. Let m a and mM denote the multiplicity of A and respectively, and let t (resp. q) denote the difference between the numbers of positive and negative triangles (resp. quadrangles) contained. Theorem 5.2. If G is an exceptional signed graph with 2 eigenvalues, then either G is the 3-dimensional cube with negative quadrangles or its parameters (n, r, A, mA, mM, t, q) have the form 2(A + 2), 2A, A, k, -2, 2A, 6A(A2 - 4), 8A(A + 2)(A - 1)(A - 5)), where A is a positive integer and either (a) k = 6, 2 < A < 10, (b) k = 7, 2 < A < 16 and A is even or (c) k = 8, 2 < A < 28. Proof. Let j > -2. Then either j = -1 or A = -j (as follows by considering (5.1)). In the former case, we arrive at the complete signed graph (which is non-exceptional). In the latter case, we have r = —Aj < 4, and so r = 3, as r < 3 leads to non-exceptional solutions. It is known from [8] that the mentioned cube is the unique 3-regular signed graph with 2 eigenvalues (±\/3); in addition, this is an exceptional signed graph. The last can be verified either by hand or by identifying our cube among 1242 signed graphs of Lemma 4.4(iii) (it is enumerated by 641 in the original reference). Let j = -2. We immediately get r = 2A, while, by virtue of Theorem 4.8, we have mA = k, for 6 < k < 8. By using mA + m-2 = n and AmA — 2m-2 = 0, we arrive at n = k (A + 2) and m-2 = | A. Similarly, the parameters t and q are obtained by m^A3 — 8m_2 = 6t, m^A4 + 16m_2 = (2r — 1)rn + 8q, where the right-hand sides count the difference between the numbers of positive and negative closed walks of length 3 and 4, respectively. Since G is an induced subgraph of Mfc, we get the upper bounds for A. Taking into account that all the parameters are integral if and only if either k is even or k is odd and A is even, we conclude the proof. □ Here is another result giving a specified decomposition of Mk. 106 Ars Math. Contemp. 18 (2020) 105-115 Theorem 5.3. Let G be a signed graph with a representation in Ek (6 < k < 8) having 2 eigenvalues, A and -2, and | (A + 2) vertices. If n denotes the number of vertices in Mk then, unless G coincides with Mk, there exists a signed graph Hi with eigenvalues |" — A—4 (of multiplicity k) and —2 (of multiplicity n — (A + 4)), such that A* = (aB AH). (5.2) Proof. Observe that, under given assumptions, the multiplicity of A (in G) is k. Clearly, the matrix A* can be written in the form (5.2), where Ah is the adjacency matrix of some signed graph Hi. If so, then by (5.1) we have AHB = —BAd + (— 2)B, as the positive eigenvalue of Mk is 2("fc-fc). If x is an eigenvector associated with an eigenvalue of G, then AH Bx = —BA¿,x + (— 2)Bx, giving AhBx = (—v + 2(n ~ k) — 2) Bx, (5.3) where v stands for either A or —2. If Bx = 0, then (again, by (5.1)) we have A* (x) = (A?x) = v (x). <5.4) The case v = A cannot occur in (5.4), since Mk and G cannot share the same eigenvalues because they differ in vertex degree. Therefore, |" — A — 4 is an eigenvalue of Hi, with multiplicity at least k. Moreover, its multiplicity must be exactly k, as follows by interchanging the roles of G and H and considering (5.3) (with Aq instead of Ah and BT instead of B); a larger multiplicity would imply either A = 2("fc-fc) or A = —2, both impossible. Since Hi has n — | (A+2) vertices, there are exactly n — | (A+4) remaining eigenvalues (with repetitions). If n — | (A + 4) =0, then H is totally disconnected (with k vertices), and we are done; this is a degenerate case where Hi has only one eigenvalue. Otherwise, if d is the average value of the remaining eigenvalues, then by k( — A — 4) + (n — ^(A + 4)) d = 0, we get d = —2, which (since H is an induced subgraph of Mk) implies that —2 is the unique remaining eigenvalue with the desired multiplicity. □ In the light of the previous result, we say that Mk is decomposed into G and Hi. We are now in position to give the following characterization. Theorem 5.4. If G is an exceptional signed graph with 2 eigenvalues, then either (i) G is the 3-dimensional cube with negative quadrangles, M6, M7, M8 or (ii) the parameters of G are determined by Theorem 5.2 and G is obtained from a decomposition of Mk in sense of Theorem 5.3. Z. Stanic: Notes on exceptional signed graphs 107 The proof follows directly. Observe that if Mk is decomposed as in Theorem 5.3, then a special case where G and H are isomorphic (possibly, after an appropriate switching) may occur. Here are some particular cases: • Besides the cube described in Theorem 5.2, in [8] (but see also [4, 7]) the existence of the 2 additional exceptional signed graphs with 2 eigenvalues is confirmed; they correspond to data of Theorem 5.2 obtained for (k, A) = (7, 2) and (k, A) = (8, 2), respectively. • Setting (k, A) = (7,14) and (k, A) = (8,26) in Theorem 5.2, we get that G is paired (in sense of Theorem 5.3) with a totally disconnected graph with 7 and 8 vertices, respectively. Since Mk contains a co-clique with the corresponding number of vertices, we may confirm the existence of G; clearly, it is exceptional. Note that every signed graph represented by all the non-integral roots of E+, for 6 < k < 8, is exceptional. Therefore, every signed graph represented by these and possibly some other roots of E+ is also exceptional. • Up to the switching equivalence, L(K8) is represented by the roots e¡ - ej (1 < i < j < 8). Thus, it has a representation in E+; moreover, since all the corresponding roots are orthogonal to 1 j G E+, L(K8) has a representation in E+, as well. It is paired with the signed graph with (k, A) = (7,8), which is exceptional by the previous observation. To get another example we need the following theorem. Theorem 5.5. If F is a regular graph with 8 vertices, then L(.F) is represented by integral roots of E+. Proof. Since each column of the vertex-edge incidence matrix Bn of F has length 8 and contains exactly 2 non-zero entries, it follows that L(.F) has a representation in D+, which is sufficient to conclude the proof. □ If F is r-regular with k vertices, then by (5.1) the spectrum of L(.F) is 2(r - 1)k, (-2)fc(r-1) (5.5) and so, for k = 8, L(-F) is paired with an exceptional signed graph with spectrum [2(14 — r )8, ( —2)8(14-r)] . Its existence covers many particular cases of Theorem 5.2. We continue by some non-existences. Theorem 5.6. There is no exceptional signed graph neither for k = 6 and A