ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 12 (2017) 271-286
Characterization of graphs with exactly two non-negative eigenvalues
Mohammad Reza Oboudi *
Department of Mathematics, College of Sciences, Shiraz University, Shiraz, 71457-44776, Iran School ofMathematics, Institute for Research in Fundamental Sciences (IPM), P.O. Box 19395-5746, Tehran, Iran
Received 28 March 2016, accepted 26 June 2016, published online 23 December 2016
In this paper we characterize all graphs with exactly two non-negative eigenvalues. As a consequence we obtain all graphs G such that A3(G) < 0, where A3(G) is the third largest eigenvalue of G.
Keywords: Spectrum and eigenvalues of graphs, graphs with exactly two non-negative eigenvalues. Math. Subj. Class.: 05C31, 05C50, 05C75, 05C76, 15A18
1 Introduction
Throughout this paper all graphs are simple, that is finite and undirected without loops and multiple edges. Let G be a graph with vertex set jvi,..., vn}. The adjacency matrix of G, A(G) = [aj], is an n x n matrix such that aij = 1 if vi and vj are adjacent, and aij = 0, otherwise. Thus A(G) is a symmetric matrix with zeros on the diagonal and all the eigenvalues of A(G) are real. By the eigenvalues of G we mean those of its adjacency matrix. We denote the eigenvalues of G by A1(G) > • • • > An(G). By the spectrum of G that is denoted by Spec(G), we mean the multiset of eigenvalues of G. The characteristic polynomial of G, det(AI - A(G)), is denoted by P(G, A). Studying the eigenvalues of graphs, the roots of characteristic polynomials of graphs, has always been of great interest to researchers, for instance see [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] and the references therein.
It is well known that Ai (G) +-----+ A„(G) =0 and A2 (G) +-----+ A^(G) = 2m, where
m is the number of edges of G. Thus if G has at least one edge, then G has at least one positive eigenvalue. One of the attractive problems is the characterization of graphs with a
*This research was supported in part by a grant from IPM (No. 95050012).
E-mail address: mr oboudi@yahoo.com (Mohammad Reza Oboudi)
Abstract
©® This work is licensed under http://creativecommons.Org/licenses/by/3.0/
272
Ars Math. Contemp. 12 (2017) 383-413
few non-zero eigenvalues. In [5] all bipartite graphs with at most six non-zero eigenvalues have been characterized. The another interesting problem is the characterization of graphs with a few positive eigenvalues. In [10] Smith characterized all graphs with exactly one positive eigenvalue. In fact, a graph has exactly one positive eigenvalue if and only if its non-isolated vertices form a complete multipartite graph. In [9] Petrovic has studied the characterization of graphs with exactly two non-negative eigenvalues. In this paper with a different proof we state a new characterization of all graphs G with exactly two nonnegative eigenvalues. In other words we find the graphs G with Ai(G) > 0, A2(G) > 0 and As(G) < 0.
For a graph G, V(G) and E(G) denote the vertex set and the edge set of G, respectively; G denotes the complement of G. The order of G denotes the number of vertices of G. The closed neighborhood of a vertex v of G which is denoted by N[v], is the set {u e V(G) : uv e E(G)} U {v}. For every vertex v e V(G), the degree of v is the number of edges incident with v and is denoted by degG(v) (for simplicity we use deg(v) instead of degG(v)). By ¿(G) we mean the minimum degree of vertices of G. A set S C V(G) is an independent set if there is no edge between the vertices of S. The independence number of G, a(G), is the maximum cardinality of an independent set of G. For two graphs G and H with disjoint vertex sets, G + H denotes the graph with the vertex set V(G) U V(H) and the edge set E(G) U E(H), i.e. the disjoint union of two graphs G and H. In particular, nG denotes the disjoint union of n copies of G. The complete product (join) G V H of graphs G and H is the graph obtained from G + H by joining every vertex of G with every vertex of H. For positive integers n1,..., n^, Knii...,n<, denotes the complete multipartite graph with I parts of sizes n1,..., n^. Let Kn, nK1 = Kn, Cn and Pn be the complete graph, the null graph, the cycle and the path on n vertices, respectively.
2 The structure of graphs with exactly two positive eigenvalues
In this section we obtain a characterization of graphs that have exactly two positive eigenvalues. We need the Interlacing Theorem.
Theorem 2.1. ([4, Theorem 9.1.1]) Let G be a graph of order n and H be an induced subgraph of G with order m. Suppose that A1(G) > • • • > An (G) and A1(H) > • • • > Am(H) are the eigenvalues of G and H, respectively. Then for every i, 1 < i < m, Ai(G) > Ai(H) > A n-m+i (G).
Theorem 2.2. ([10], see also [3, Theorem 6.7]) A graph has exactly one positive eigenvalue if and only if its non-isolated vertices form a complete multipartite graph.
First we characterize all graphs with exactly one non-negative eigenvalue.
Theorem 2.3. Let G be a graph of order n > 2 with eigenvalues A1 > • • • > An. Then A2 < 0 if and only if G = Kn.
Proof. If G = Kn and n > 2, then A2 = -1. Now suppose that A2 < 0. We show that G = Kn. Suppose that G = Kn. Thus 2K1 is an induced subgraph of G. So by Interlacing Theorem 2.1, A2 > A2(2K1) = 0, a contradiction. Hence G = Kn.	□
Lemma 2.4. Let G be a graph of order n > 3 with eigenvalues A1 > • • • > An. Suppose that A1 > 0, A2 > 0 and A3 < 0. Then the following hold:
M. R. Oboudi: Characterization of graphs with exactly two non-negative eigenvalues
273
1.	If G is disconnected, then G = Kr + Kn—r, for some positive integer r, where r < n — 1.
2.	If G is connected and A2 = 0, then G = Kn \ e for an edge e of Kn.
Proof. 1. Let G be disconnected. Assume that Gi,..., Gk are the connected components of G, where k > 2. Since A1(G1) > 0,..., A1(Gk) > 0 are k eigenvalues of G and A3 < 0 we obtain that k = 2. In other words G has exactly two connected components. Thus G = G1 + G2. We prove that G1 and G2 are complete graphs. First we show that G1 is a complete graph. If G1 = K1, there is nothing to prove. Assume that | V(G1) | > 2 (equivalently G1 ^ K1). We claim that A2(G1) < 0. By contradiction suppose that A2(G1) > 0. Since A1(G1) > 0, A2(G1) > 0 and A1(G2) > 0 are three eigenvalues of G we obtain that A3 > 0, a contradiction (since A3 < 0). Hence the claim is proved. In other words A2(G1) < 0. So by Theorem 2.3, G1 is a complete graph. Similarly we obtain that G2 is a complete graph. Hence G is a disjoint union of two complete graphs.
2. Suppose that G is connected and A2 = 0. Since A3 < 0, G = nK1. Thus A1 > 0. Hence G has exactly one positive eigenvalue. By Theorem 2.2 there are some positive integers t and n1 > • • • > nt > 1, so that n1 + • • • + nt = n and G = Knii...,nt. If t = 1, then G = nK1, a contradiction (since G is connected). Thus t > 2. If n1 = 1, then G = Kn and so A2 = —1, a contradiction. Therefore n1 > 2. If n2 > 2, then C4 is an induced subgraph of G. Using Interlacing Theorem 2.1 we get A3 > A3(C4) = 0, a contradiction. Thus n2 = • • • = nt = 1. Now if n1 > 3, then K1j3 is an induced subgraph of G. Similarly by Interlacing Theorem 2.1 we obtain A3 > A3 (K13) = 0, a contradiction. So n1 = 2. Thus G = K2j1i...i1. In other words G = Kn \ e, for an edge e of Kn. We note that
n — 3 + V n2 + 2n — 7 n — 3 — a/ n2 + 2n — 7 SPec(Kn \ e) = {-^-, 0, —1,..., —1,-^-}.
2 -v-' 2
n—3
The proof is complete.	□
In [2] all graphs G with A1 > 0, A2 < 0 and A3 < 0 have been characterized.
Remark 2.5. Let n1,..., nt be some positive integers and G = Knii...,nt. Similar to the proof of the second part of Lemma 2.4 by Interlacing Theorem 2.1 one can see that A2(G) < 0 if and only if n1 = • • • = nt = 1. On the other hand by Theorem 2.2, A2(Knii...,nt) < 0. Thus A2(Knii...jnt) =0 if and only if nk > 1 for some k. In other words, the second largest eigenvalue of any complete multipartite graph except complete graph is zero.
Remark 2.6. Let G be a graph of order n > 3 with eigenvalues A1 > • • • > An. Assume that G has exactly two non-negative eigenvalues. In other words, A1 > 0, A2 > 0 and A3 < 0. Since A3 < 0, G = nK1. Thus A1 > 0. Hence A1 > 0, A2 > 0 and A3 < 0. If G is disconnected, then by the first part of Lemma 2.4, G = Kr + Kn—r for some positive integer r < n — 1. If G is connected and A2 = 0, then by the second part of Lemma 2.4, G = Kn \ e, where e is an edge of Kn. Thus to characterize all graphs with exactly two non-negative eigenvalues it remains to find connected graphs G such that A1 (G) > 0, A2(G) > 0 and A3(G) < 0. In sequel we find this characterization.
274
Ars Math. Contemp. 12 (2017) 383-413
Definition 2.7. A graph G is called semi-complete if G is a disjoint union of two complete graphs or is obtained by adding some new edges to disjoint union of two complete graphs (see Figure 1).
M X V V
Hi
H,
Ha
Figure 1: The graphs Hi, H2 and H3 are semi-complete that are obtained from K3 + K4.
Now we prove one of the main results of this section.
Lemma 2.8. Let G be a connected graph of order n > 3 and with eigenvalues Ai > • • • > An. If A2 > 0 and A3 < 0, then for every vertex v e V(G) with degree ¿(G) we have N[v] = K5(G)+i and G \ N[v] = Kn_S(G)_i. In particular, G is semi-complete.
Proof. Let A2 > 0 and A3 < 0. Since A2 > 0, G is not complete graph. Therefore a(G) > 2. If a(G) > 3, then 3Ki is an induced subgraph of G. Thus by Interlacing Theorem 2.1, A3(G) > A3(3Ki) = 0, a contradiction. Therefore a(G) = 2. Thus for every vertex u e V(G), G \ N[u] is a complete graph. In fact, G \ N[u] = K„_des(„)_i.
Let v0 be a vertex of G with degree ¿(G), that is v0 has the minimum degree among all vertices of G. Since G ^ Kn, deg(v0) < n - 2. Since G \ N[v0] is a complete graph, to complete the proof it is sufficient to show that the induced subgraph on the set N [v0] is a complete graph, that is every two vertices of N[v0] are adjacent. This also shows that G is obtained by adding some edges to the complete graphs N[v0] and G \ N[v0] and so G is semi-complete.
Now we show that N[v0] is a complete graph. By contradiction, suppose that w and z are two non-adjacent vertices of N[v0]. Let a be an arbitrary vertex of V(G) \ N[v0]. The induced subgraph on {v0, w, z, a} in G is one of the graphs, Ai, A2, A3 or A4 (see Figure 2). Since A3(Ai) = A3(A4) = 0 and A3 < 0, Interlacing Theorem 2.1 shows that
v0
a
v0
v0
Ai
A,
A3
A4
Figure 2: The subgraphs Ai, A2, A3 and A4. the induced subgraph on {v0, w, z, a} is A2 or A3. In other words any vertex of G \ N[v0]
M. R. Oboudi: Characterization of graphs with exactly two non-negative eigenvalues
275
has exactly one neighbor in {w, z}. Without losing the generality assume that a is adjacent to w. Now we show that every vertex of G \ N[v0] is adjacent to w. By contradiction suppose that b = a is a vertex of G \ N[v0] such that b is adjacent to z. Since G \ N[v0] is complete and a, b G V(G) \ N[v0], the vertices a and b are adjacent. Thus the induced subgraph on {v0, w, z, a, b} is isomorphic to the cycle C5. Since A3(C5) ~ .618 > 0, by Interlacing Theorem 2.1, we have A3 > 0, a contradiction. This contradiction shows that all vertices of G \ N[v0] are adjacent only to w. This implies that deg(z) < deg(v0) - 1, a contradiction, since v0 has minimum degree. This contradiction completes the proof. □
Claim 2.9. Let G be a connected graph of order n > 3 and with eigenvalues Ai > • • • > An such that A2 > 0 and A3 < 0. Let X = N[v0] and Y = G \ N[v0], where v0 is a vertex of G with degree ¿(G). Then for every two vertices a and b in X (also for a and b in Y) N[a] C N[b] or N[b] C N[a].
Proof. Let a and b be two vertices of X. We show that N[a] C N[b] or N[b] C N[a]. First note that by Lemma 2.8, X is a complete graph. This implies that N[a] n X = N [b] n X = X. Now by contradiction suppose that there are some vertices c and d in Y such that c G N[a] \ N[b] and d G N[b] \ N[a]. Thus the induced subgraph on {a, b, c, d} is isomorphic to C4. Using Interlacing Theorem 2.1 we get A3 > A3 (C4) = 0, a contradiction (since A3 < 0). Thus the result follows. Similarly one can prove that for any two vertices v and w in Y, N[v] C N[w] or N[w] C N[v].	□
As an example we find an infinite family of connected graphs with positive second largest eigenvalue and negative third largest eigenvalue.
Corollary 2.10. Let n > 4 be an integer. Let K(n, t) be the graph obtained by deleting t edges incident to one vertex of Kn, where 2 < t < n — 2. Then A2(K(n, t)) > 0 and A3(K(n, t)) < 0.
Proof. Let A1 > • • • > An be the eigenvalues of K(n, t). Since Kn-1 is an induced subgraph of K(n, t), by Interlacing Theorem 2.1, A1 > n — 2 > A2 > —1 > A3. Thus A3 < 0. On the other, since K(n, t) is not a complete multipartite, by Theorem 2.2, A2 > 0.	□
Definition 2.11. A graph G is called quasi-reduced if for every two vertices u and v of G, N [u] = N [v].
As an example of quasi-reduced graphs, we define the graphs Gn that have important role for characterizing graphs with A2 > 0 and A3 < 0.
Definition 2.12. For every integer n > 2, let Gn be the graph of order n such that Gn is obtained from disjoint complete graphs Kpn] and K^nj as following: Let V(Kpn]) =
{v1,..., vpn} and V(Kpnj) = {w1,..., w^nj}. Then add some new edges to Kpn] + K\ n j such that the following hold:
(i)	N[v1] C • • • C N[vpn-] and N[w1] C • • • C N[wLnj].
(ii)	|N[v<] n V(KLnj)| = i — 1 for i = 1,..., [fl.
(iii)	iN [wj ]n v (kp n -)i={j,—1, if n isover; for j=^., l?j.
276
Ars Math. Contemp. 12 (2017) 383-413
In Figure 3, the graphs G2, G3, G4, G5 and G6 have been shown. In addition in Figure 4 one can see the complement of G7,..., Gi2. We note that G2k = B2k(1,..., 1; 1,..., 1)
and G2k+1 = B2k+1(1,..., 1; 1,..., 1; 1), where B2k and B2k+1 are the graphs that have been defined in [9].
Remark 2.13. For every n > 2, Gp is semi-complete and quasi-reduced. In addition if n > 3, then Gp is connected. We note that for every n > 3, Gp is an induced subgraph of Gp+1. In fact if n is even, then Gn+1 = K1 V Gp and if n is odd, then Gn+1 is obtained from Gp by adding a new vertex w such that w is adjacent to any vertex of {w1,..., wynj} = V(Kynj), where Kynj is one of the parts of Gp (see Definition 2.12).
Remark 2.14. We note that for every n > 2, the group of all automorphisms of the graph
Gp, Aut(Gp), has exactly two elements.
V1
w1 G2
V1
w1
G3
V1
\ V2	\
V2	V3
w1
w2
G4
G5
w2	w3
w1 G6
Figure 3: The graphs G2,G3, G4, G5 and G6 are semi-complete and quasi-reduced.
The next result shows that there is only one connected quasi-reduced graph with A2 > 0 and A3 < 0.
Lemma 2.15. Let G be a connected graph of order n > 3. If G is quasi-reduced and A2(G) > 0 and A3(G) < 0, then G = Gp.
Proof. Assume that A2(G) > 0 and A3(G) < 0. Since G is connected, by Lemma 2.8, G is semi-complete. Let ¿(G) = t and v1 be a vertex of G with degree t. By Lemma 2.8, N V] = Kt+1 and G \ N[v1 ] = Kn_t_1. In fact G is obtained from the disjoint complete graphs Kt+1 and Kn_t_1 by adding some new edges (see the proof of Lemma 2.8). Let
V (Ki+1) = {v1 ,v2 ,_.,vt+1} and V (Kn_t_1) = M,..., w^J. By Claim 2.9, for every two vertices v'i and vj in Kt+1, N[v-] C N[vj] or N[vj] C N[v-]. Also for every two vertices w- and wj in Kn _ t_ 1, N[w-] C N[wj] or N[wj] C N[w-]. So without losing the generality assume that N[ v1 ] C ••• C N [v-+1] and N [w1 ] C • • • C N [wn_t_1] (note that N[v-] = V(Kt+1) and for every 1 < i < t + 1, N[v1 ] C N[vi]). Now sup_osti that G is quasi-reduced. Therefore we find that
0 = |N [v1 ] n V (Kp_t_1)| < ••• < |N [v-+1] n V (Kp_t_1)| < n - t - 1, (2.1)
and
0 < |N[wi] n V(Kt+1)| < • • • < |N[wp_t_1] n V(Ki+1 )| < t.
(2.2)
M. R. Oboudi: Characterization of graphs with exactly two non-negative eigenvalues
277
V4 V3 V2 Vi
V4 V3 V2 Vi
V5 V4 V3 V2 Vi
W4 W3 W2 Wi
G9
V6 V5 V4 V3 V2 Vi
W5 W4 W3 W2 Wi	W5 W4 W3 W2 Wi
Gio	Gii
V6 V5 V4 V3 V2 Vi
W6 W5 W4 W3 W2 Wi
Gi2
Figure 4: The complement graphs of G7, G8, G9, Gi0, Gii and Gi2.
Since |N V ]nV (K„_t_i)|,..., |N K+1]nV (K„_t_i)| are t+1 distinct integers between 0 and n -t - 1, the Equation (2.1) shows that t < n -t - 1. Similarly, the Equation (2.2) implies that n - t - 2 < t. Hence n - 2 < 2t < n - 1. So t = [n] - 1.
If n is even, then the Equation (2.2) shows that |N[wj] n V(Kt+1
j - 1, for
j = 1,..., n - t - 1. So w[ has no neighbor in Kt+1. Thus for any 1 < i < t + 1, |N[V] n V(Kn_t_i)| < n - t - 2. Using Equation (2.1) we conclude that |N[v<] n V (Kn_t_1)| = i - 1, for i = 1,...,t +1. Hence G = Gn.
Similarly, for odd n we obtain that |N[v<] n V(Kn_t_1)| = i - 1, for i = 1,..., t + 1. Thus v£+1 is adjacent to every vertex of V(Kn_t_1). Hence 1 < |N[wi] n V(Kt+1)|. Using inequality (2.2) we find that |N [wj ] n V (Km)| = j, for j = 1,... ,n -1 - 1. Thus G = G„.	□
Lemma 2.16. Let Gn be the semi-complete and quasi-reduced graph as mentioned above. Then A2(Gn) > 0 and A3(Gn) < 0 ifandonly if 4 < n < 12.
Proof. One can see that A2(G3) = 0 and for every 4 < n < 12, A2(Gn) > 0 and A3(Gn) < 0. Now assume that n > 13. Since A3(G13) = 0 and G13 is an induced subgraph of Gn (by Remark 2.13), by Interlacing Theorem 2.1 we find that A3(Gn) > A3(G13) = 0. This completes the proof.	□
Definition 2.17. Let G be a graph with vertex set {v1, ..., Vn}. By G[Ktl,..., Ktn] we mean the graph obtained by replacing the vertex Vj by the complete graph Ktj for
278
Ars Math. Contemp. 12 (2017) 383-413
1 < j < n, where every vertex of Kti is adjacent to every vertex of Ktj if and only if vj is adjacent to vj (in G). For example K2 [Kp, Kq] = Kp+q and K2 [Kp, Kq] = Kp + Kq.
Now we prove one of the main results of the paper.
Theorem 2.18. Let G be a connected graph of order n > 3. If A2(G) > 0 and A3(G) < 0, then there exist some positive integers s and ti,... ,ts so that 3 < s < 12 and ti+- ■ -+ts = n and G = Gs[Ktl,..., Kts].
Proof. Suppose that A2(G) > 0 and A3(G) < 0. By Lemma 2.8, G is semi-complete. If G is quasi-reduced, then by Lemma 2.15, G = Gn = Gn[Ki,..., Ki]. So A2(Gn) = A2(G) > 0 and A3(Gn) = A3(G) < 0. Hence by Lemma 2.16, 4 < n < 12.
Now assume that G is not quasi-reduced. Thus there exists a connected induced subgraph of G, say H, such that H is quasi-reduced and G = H[Ktl,..., Kts ], where s is the order of H and ti,..., ts are some positive integers. Thus ti + ■ ■ ■ + ts = n. If H = Ks, then G = Kn, a contradiction (since A2(Kn) = -1 < 0 while A2(G) > 0). Thus H is not a complete graph. On the other hand H is a connected graph of order s. Thus s > 3. Since H is obtained from G by removing some vertices and G is semi-complete, H is also semi-complete. Suppose that C4 is an induced subgraph of H. Since H is an induced subgraph of G, by Interlacing Theorem 2.1 we conclude that A3(G) > A3(H) > A3(C4) = 0, a contradiction. Thus H has no induced cycle C4.
Now we show that H = Gs. Since H is semi-complete, H is obtained from the disjoint union of two complete graphs, say Kp and Kq, for some positive integers p and q. Let X = Kp and Y = Kq. We claim that for every two vertices a, b e V(X), N[a] C N[b] or N[b] C N[a]. By contradiction assume that N[a] £ N[b] and N[b] ^ N[a]. Thus there are two vertices c and d such that c e N[a] \ N[b] and d e N[b] \ N[a]. Since V(X) C N[a] n N[b], we find that c and d are two vertices of Y. Now we remark that the induced subgraph on the vertices a, b, c, d is isomorphic to C4. It is a contradiction, since H has no induced cycle C4. So the claim holds. Similarly for every two vertices z, w e V(Y), N[z] C N[w] or N[w] C N[z]. On the other hand H is quasi-reduced, thus similar to the proof of Lemma 2.15 one can see that H = Gs.
If s > 13, then by Remark 2.13, Gi3 is an induced subgraph of H and so is an induced subgraph of G. Thus by Interlacing Theorem 2.1, A3(G) > A3(Gi3) = 0, a contradiction, since A3(G) < 0. Hence s < 12. The proof is complete.	□
We end this section by characterization the graphs with A3 < 0. We note that if G is a graph with A3(G) < 0, then G is not the null graph. Thus Ai(G) > 0. Using Remark 2.5, the second part of Lemma 2.4 and Theorems 2.2, 2.3 and 2.18 we obtain this characterization.
Theorem 2.19. Let G be a graph with eigenvalues Ai > ■ ■ ■ > An. Assume that A3 < 0. Then the following hold:
1.	If Ai > 0 and A2 > 0, then G = Kp + Kq for some integers p, q > 2 or there exist some positive integers s and ti,..., ts so that 3 < s < 12 and ti + ■ ■ ■ + ts = n and G = Gs [Kti ,...,Kts ].
2.	If Ai > 0 and A2 = 0, then G = Ki + Kn-i or G = Kn \ e, where e is an edge of Kn.
3.	If Ai > 0 and A2 < 0, then G = Kn.
M. R. Oboudi: Characterization of graphs with exactly two non-negative eigenvalues
279
Since Kn \ e = G3[Ki, Ki, Kn-2] and Kp + Kq = K2[Kp,Kq], we can rewrite Theorem 2.19 as following:
Theorem 2.20. Let G be a graph. If A3(G) < 0, then G = Kn or there exist some positive integers s and ti,... ,ts such that 2 < s < 12 and ti + ■ ■ ■ + ts = n and G = Gs[Ktl ,...,Kts ].
In the next section we investigate the converse of Theorem 2.20. In other words we obtain all values of ti,..., ts (for 2 < s < 12) such that A3(Gs [Kt1,..., Kts ]) < 0. We need the following important result for computing the characteristic polynomial of
Gs[Kti,..., Kts ], the polynomial P (Gn[Kti,..., Ktn ], A).
Theorem 2.21. [7] Let n > 2. Suppose that {vi,... ,vn} is the vertex set of Gn and A = [aij ] is the adjacency matrix of Gn with respect to {vi,..., vn} (aij = 1 if and only if v^ and vj are adjacent and aij = 0, otherwise). Let ti,... ,tn be some positive integers and M = [mj ] be a n x n matrix, where
ti - 1, if i = j; aijtj, if i = j.
Then
P(Gn[Kti,..., Ktn], A) = (A + 1)tl+-+tn-n g(A),
where g(A) = det(AI — M). In addition, the multiplicity of —1 as an eigenvalue of Gn [Kt1,..., Ktn ] is equal to ti +-----+ tn — n.
3 The list of all connected graphs with A2 > 0 and A3 < 0
In this section we investigate the converse of Theorem 2.20. We use Petrovic's notation [9] that is very similar to the notation of Definition 2.17. We note that in Definition 2.17, the graph G[Hi,..., Hn] is dependent to the labeling of the vertices of G while in the next definition first we fix a labeling for the vertices of Gn (see Definition 2.12), and then use the operation of Definition 2.17. For instance we consider the labeling vi,... ,vs and wi,... ,ws for the vertices of G2s and then apply the operation of Definition 2.17.
Definition 3.1. Let s > 1 be an integer and ni,... ,n2s+i be some positive integers. Let B2s(ni,..., ns; ns+i,..., n2s) denote the graph obtained from G2s by replacing the vertices vi by Km, v2 by Kn2,..., and v,s by Kns and wi by K^+i, w2 by K„s+2, ..., and ws by Kn2s (see Definition 2.12). In other words
B2s(ni, . . . , ns; ns+l, . . . , n2s ) = G2 s [Kni , ... , Kn2s ],
where the ordering of the vertices of G2s is V(G2s) = {vi,..., vs,wi,.. Similarly, by B2s+i(ni,... ,ns; ns+i,... ,n2s; n2s+i) we mean
B2s + l(nl, ... , ns; ns + l, . . . , n2s; n2s + 0 = G2 s+i [Kni, ... , Kn2s + i ],
where the ordering of the vertices of G2s+i is V (G2s+i) = {vi,... ,vs,wvi,..., ws, vs+i}, (see Figure 5).
}
w
s
280
Ars Math. Contemp. 12 (2017) 383-413
Remark 3.2. For every positive integers s and ni,..., n2s+i, one can easily see that
B2S(ni,. .. ,ns; ns+i,. .. ,n2s) = B2s(ns+i, .. . ,n2s; ni,. .. ,ns),
and
B2S+i(ni,... ,ns; ns+i,... ,n2S; n2S+i) = B2S+i(ns+i,..., n2S; ni,... ,ns; n2S+i).
For avoiding the repeating, using the dictionary ordering on (ni,..., ns) and (ns+i,..., n2S) we just cite one of the graphs B2S(ni,... ,ns; ns+i,... ,n2S) or B2S(ns+i,... ,n2S; ni,..., ns) in our characterization. Similarly for the graphs B2s+i(ni,..., ns; ns+i,...,
n2S; n2S+i) and B2S+i(ns+i,... ,n2S; ni,..., ns; n2S+i) we only consider one of them. For example since by dictionary ordering (4,3,2) > (4,3,1) we use B6(4,3,2; 4, 3,1) instead of B6 (4, 3,1; 4,3, 2). As another example we use B7(5, 3, 2; 5,2,4; 8) instead of
B7(5, 2, 4; 5, 3, 2; 8), since (5, 3, 2) > (5, 2,4).
Figure 5: The graphs B3(2; 2; 4) and B4(1, 2; 4,2).
The following theorem is the main result of [9].
Theorem 3.3. [9] Graph G has the property A3 < 0 if and only if G is an induced subgraph of one of the following graphs:
1.	B4(3, 2; 2, r),
2.	B5(1,r;2, 3; 1),
3.	B5(r, 1;2, 3; 1),
4.	B5(3, 2; 2,1; r),
5.	B5(r, 2; 1, 2; 2),
6.	B6(r, 1, s; 1, 2, 2),
7.	B6(2,1, r; 2,1,s),
8.	B6(1, 2, 2; 1, r, 1),
9.	B6(2, 2,1; 1,1, r), 10. B7(2,1,1; 2,1,1; r),
M. R. Oboudi: Characterization of graphs with exactly two non-negative eigenvalues
281
11.	B7(r, 1, 2; 1, s, 1; 1),
12.	B7(r, 1,1; 1,1, 2; 1),
13.	B7(2, 2,1; 1, r, 1; s),
14.	B8(r, 1,1, s; 1,1,t, 1),
15.	B9(1,r, 1,1; 1, s, 1,1;t),
where r, s and t are some positive integers or G is an induced subgraph of one of the 323 graphs with 12 vertices belonging respectively to the classes B4 (10 graphs), B5 (25 graphs), B6 (69 graphs), B7 (74 graphs), B8 (80 graphs), B9 (40 graphs), Bio (20 graphs), Bn (4 graphs) and Bi2 (1 graph).
Now we give a nicer characterization for graphs with A3 < 0. Note that the Petrovic's result shows that any graph with exactly two non-negative eigenvalues is an induced subgraph of one the graphs described by Theorem 3.3. Since finding the structure of induced subgraphs of a graph is complicated, it is better to find the exact structure of all graphs with A3 < 0. In sequel we find this structure. To find our characterization, first we note that by Theorem 2.20 every graph with exactly two non-negative eigenvalues is isomorphic to Gs [Ktl,..., Kts] for some positive integers ti,..., ts, where 2 < s < 12. In this section we find all values of ti,..., ts such that Gs [Ktl,..., Kts] has exactly two non-negative eigenvalues. In other words we solve the converse of Theorem 2.20. We note that by Remark 2.6 it suffices to find all connected graphs with Ai > 0, A2 > 0 and A3 < 0. In other words we find all connected graphs Gs [Ktl,..., Kts ] such that 3 < s < 12 and Ai > 0, A2 > 0 and A3 < 0. We obtain these graphs in ten theorems (for every s, 3 < s < 12, we consider a theorem). First we prove the case s = 3. Since the cases s = 4,..., s = 9 similarly are proved, we just prove the case s = 6. In addition the proofs of the cases s = 10,11,12 are similar and we only prove the case s = 10. Our proofs are based on three theorems, Theorem 2.21 for computing the characteristic polynomials of Gs [Ktl,..., Kts], Descartes' Sign Rule for polynomials and Interlacing Theorem 2.1. Since Gs[Ktl,..., Kts] = Bs(ti,... ,ts), in sequel we use Bs(ti,... ,ts) instead of Gs [Ktl,..., Kts ].
Theorem 3.4. Let G = B3 (a; b; c), where a, b, c are some positive integers. Then A2 (G) > 0 and A3(G) < 0 if and only if ab = 1.
Proof. Let g(A) = P(B3(a; b; c), A). By Theorem 2.21 we obtain that
g(A) = (A + 1)a+b+c-3 f (A),	(3.1)
where
f (A) = A3 - (a + b + c- 3)A2 + (ab - 2a - 2b - 2c + 3)A + ac(b - 1) + (a - 1)(b + c- 1).
If ab = 1, that is a = b =1, then g(A) = A(A + 1)c-i(A2 - (c - 1)A - 2c). This shows that Ai(G) > 0 and A2(G) = 0. Now suppose that ab > 2. Let zi > z2 > z3 be all roots of f. Hence f (A) = (A - zi)(A - z2)(A - z3). Therefore zi + z2 + z3 = a + b + c- 3 > 0 and ziz2z3 = -f (0) = -(ac(b - 1) + (a - 1)(b + c - 1)) < 0. These equalities show that zi > 0, z2 > 0 and z3 < 0. On the other hand by the Equation (3.1), the eigenvalues
282	Ars Math. Contemp. 12 (2017) 383-413
of B3(a; b; c) are z\,z2, z3, — 1,..., —1 (the multiplicity of —1 is a + b + c — 3). Hence Ai(G) = zi > 0, A2(G) = z2 > 0 and A3(G) = max{z3, —1} < 0. The proof is complete.	□
Theorem 3.5. Let G = B4(a1, a2; a3, a4), where a1, a2, a3, a4 are some positive integers. Then A2(G) > 0 and A3(G) < 0 if and only if G is isomorphic to one of the following graphs:
1.	B4(a,b;1,d), B4(a,x; y, 1), B4(a, 1; c, 1), B4(a, 1; w,x),
2.	B4(a, 1; x, d), B4(w, b; x, 1), B4(w,x; y,d), B4(x, b; y,d),
3.	25 specific graphs: 5 graphs of order 10, 10 graphs of order 11, and 10 graphs of order 12,
where a, b, c, d, x, y, w are some positive integers such that x < 2, y < 2 and w < 3.
Theorem 3.6. Let G = B5(a1,a2; a3, a4; a5), where a1, a2, a3, a4, a5 are some positive integers. Then A 2(G) > 0 and A 3(G) < 0 if and only if G is isomorphic to one of the following graphs:
1.	B%(a, w; 1,1; 1), B5j(a, x; 1, d; 1), B5j(a, x;1,y; z), B5j(a, x; 1,1; e),
2.	B5j(a, 1; c, 1; e), B5j(a, 1; x, w; 1), B5j(a, 1; x,y; e), B5j(a, 1;1,d; e),
3.	B$(w,x; y, 1; e), B$(x,b;1,1; 1), B$(x, w; 1, d; 1), B5(x,w;1,1; e),
4.	B5(1,b;1,d;1), B5(1,b;1,x; y), B5(1,x;1,y; e),
5.	63 specific graphs: 13 graphs of order 10, 25 graphs of order 11, and 25 graphs of order 12,
where a, b, c, d, e, x, y, z, w are some positive integers such that x < 2, y < 2, z < 2 and w < 3.
Theorem 3.7. Let G = B6(a1, a2, a3; a4, a5, a6), where a1,..., a6 are some positive integers. Then A2(G) > 0 and A3(G) < 0 if and only if G is isomorphic to one of the following graphs:
1.	B6(a, x, c; 1,1,1), B6(a, 1,c;1,e, 1), B6(a, 1,c;1,x,y), B6(a, 1,c;1,1,f),
2.	B6(a, 1,1; x, e, 1), B6(x, b, 1; y, 1,1), B6(x, y, 1;1,e, 1),
3.	B6(x,y, 1; 1,1,f), B6(x, 1, c; y, 1, f), B6(1,b,x;1,1,1),
4.	B6(1,b, 1; 1, e, 1), B6(1,b, 1;1,x,y), B6(1,x,y;1,1,f),
5.	145 specific graphs: 22 graphs of order 10, 54 graphs of order 11, and 69 graphs of order 12,
where a, b, c, d, e, f, x, y are some positive integers such that x < 2 and y < 2.
M. R. Oboudi: Characterization of graphs with exactly two non-negative eigenvalues
283
Proof. Let be the set of all 13 above types of graphs. In other words,
= {#6(a, x, c; 1,1,1), B(a, 1, c; 1, e, 1),..., #6(1, b, 1; 1, x, y), #6(1, x, y; 1,1, f) j,
where a, b, c, d, e, f are arbitrary positive integers and x, y G {1,2}. First we prove that every graph of n6 has positive second largest eigenvalue and negative third largest eigenvalue. For instance we show that for any positive integers a, c and f, A2(B6(a, 1, c; 1,1, f)) > 0 and A3(B6(a, 1, c; 1,1, f)) < 0. The others are proved similarly.
First we note that G6 is an induced subgraph of B6(a, 1, c; 1,1, f). Thus by Interlacing Theorem 2.1, A2(B6(a, 1, c; 1,1, f)) > A2(G6) > 0. On the other hand, if m = max{a, c, f}, then B6(a, 1, c; 1,1, f) is an induced subgraph of B6(m, 1, m; 1,1, m). So by Interlacing Theorem 2.1, A3(B6(a, 1, c; 1,1, f)) < A3(B6(m, 1, m; 1,1, m)). Thus to show that the inequality A3(B6(a, 1, c; 1,1, f)) < 0, it is sufficient to prove that A3(B6(m, 1, m; 1,1, m)) < 0. Now we show that for every positive integer m, A3(B6(m, 1, m; 1,1, m)) < 0.
Let M and m be two positive integers. If M > m, then by Interlacing Theorem 2.1,
A3(B6(M, 1,M; 1,1, M)) > A3(B6(m, 1,m;1,1,m)). This shows that if for m > 12, A3(B6(m, 1,m;1,1,m)) < 0, then for all m, A3(B6(m, 1,m;1,1,m)) < 0. Hence suppose that m > 12. By Theorem 2.21 we can obtain the characteristic polynomial of B6(m, 1, m; 1,1, m). Let (A) = P(B6(m, 1,m; 1,1, m), A). By Theorem 2.21
$m(A) = (A +1)3m-3 tfm(A),	(3.2)
where
^m(A) = 3m + (6m2 + 7m - 1)A + (2m3 + 12m2 - m - 3)A2 +
(m3 + 7m2 - 14m - 2)A3 + (m2 - 12m + 2)A4 + (3 - 3m)A5 + A6.
Since m > 12, all coefficients of ^m(A) are positive except the coefficient of A5. In fact the coefficient of A5 is negative. Now by Descartes' Sign Rule we conclude that the number of positive roots of ^m(A) is 0 or 2 and the number of negative roots is 0 or 2 or 4. Since ^m(0) = 3m = 0, every root of ^m(A) is non-zero. On the other hand by Equation (3.2) the roots of ^m(A) with many numbers -1 are the eigenvalues of B6(m, 1, m; 1,1, m). Hence every root of ^m(A) is real. Since B6(1,1,1; 1,1,1) = G6 is an induced subgraph of B6(m, 1, m; 1,1, m), by Interlacing Theorem 2.1 and Lemma 2.16 we find that Ai(B6(m, 1, m; 1,1,m)) > Ai(G6) > 0 and A2(B6(m, 1,m;1,1,m)) > A2(G6) > 0. Therefore by Equation (3.2), Ai(B6(m, 1, m; 1,1, m)) and A2(B6(m, 1, m; 1,1, m)) are two roots of ^m(A). Hence ^m(A) has exactly two positive roots. Since the degree of ^m(A) is six and ^m(A) has exactly two positive roots and (0) = 0, the number of negative roots of ^m(A) is four. Therefore by Equation (3.2), B6(m, 1, m; 1,1, m) has exactly two positive eigenvalues and 3m + 1 negative eigenvalues. This shows that A3(B6(m, 1, m; 1,1, m)) < 0. Now we prove the necessity.
Claim 1. Let H = B6(a', b', c'; d', e', f') be a graph with at least 19 vertices, that is
a' +-----+ f' > 19. If H G 06, then one of the graphs Hi = B6(a' - 1,b',c'; d',e',f') or
H2 = B6(a',b' - 1, c'; d',e',f') or H3 = B6(a', b', c' - 1; d',e',f') or H4 = B6(a',b',c'; d' - 1, e', f') or H5 = B6(a', b', c'; d', e' - 1, f') or B6(a', b', c'; d', e', f' - 1) is not in n6. Note that these graphs are all induced subgraphs of H of order | V(H) | - 1.
284
Ars Math. Contemp. 12 (2017) 383-413
Proof of Claim 1. Suppose that H G Q6. By contradiction assume that all graphs Hi,..., H6 are in Q6. Now we consider Hi. If Hi = B6(a, x, c; 1,1,1) for some positive integers a, c and x < 2, then H G Q6, a contradiction. If H1 = B6(a, 1, c; 1, e, 1), for some positive integers a, c and e, then H G 06, a contradiction. Similarly one can see that H1 =
B6(a, 1, c; 1, x, y), B6(a, 1, c; 1,1, f ), B6(a, 1,1; x, e, 1). So H1 = B6(x, 6, 1; y, 1,1) or B6(x,y, 1; 1, e, 1) or Bs(x,y, 1; 1,1,f ) or #6(x, 1, c; y, 1, f ) or #3(1,6, x; 1,1,1) or B6(1,6,1; 1, e, 1) or B6(1, 6,1; 1, x, y) or B6(1, x, y; 1,1, f ), for some positive integers 6, c, e, f and x, y < 2. Since x < 2, we find that a' — 1 < 2. Thus a' < 3. Similarly if H2,..., H6 G ^6, we obtain that 6',..., f' < 3. Therefore a' + • • • + f' < 18, a contradiction. Thus the claim is proved.
Claim 2. Let K = #3(a'', 6'', c''; d'', e'', f '') be a graph with at least 13 vertices. If K G , then A3(K) > 0.
Proof of Claim 2. Assume that K G We prove the claim by induction on n = |V(K)|. By computer one can check the validity for n = 13,..., 18. Hence let n > 19. By Claim 1, K has an induced subgraph, say L, of order n — 1 such that L G Since n — 1 > 18, by the induction hypothesis A3(L) > 0. Thus by Interlacing Theorem 2.1, A3(K) > A3 (L) > 0. Thus the claim is proved.
Now let W = B6(a''', 6''', c'''; d''',e''', f ''') be a graph of order n. Assume that A2(W) > 0 and A3(W) < 0. If W G then by Claim 2, n < 12. By computer we find that there are only 145 graphs with this property. More precisely there are 22 graphs of order 10, 54 graphs of order 11 and 69 graphs of order 12 such that they are not in n6 while their second eigenvalues are positive and third eigenvalues are negative. The proof is complete.	□
Theorem 3.8. Let G = B7(a1, a2, a3; a4, a5, a6; a7), where a1,..., a7 are some positive integers. Then A2(G) > 0 and A3(G) < 0 if and only if G is isomorphic to one of the following graphs:
1.	B7(a, 1,x;1,e, 1; 1), B7(a, 1,1;1,e, 1;g), B7(a, 1,1; 1,1,x;1),
2.	#7(x,y, 1;1,e, 1; g), #7(x, 1,1; y, 1,1; g), B7(1,6,x;1,1,1; g),
3.	#7(1,6,1; 1, e, 1; g), #7(1,1,c;1,1,f ; 1),
4.	143 specific graphs: 18 graphs of order 10, 52 graphs of order 11, and 73 graphs of order 12,
where a, 6, c, d, e, f, g, x, y are some positive integers such that x < 2 and y < 2.
Theorem 3.9. Let G = Bg(a1, a2, a3, a4; a5, a6, a7, a8), where a1,..., a8 are some positive integers. Then A2(G) > 0 and A3(G) < 0 ifandonly if G is isomorphic to one of the following graphs:
1.	Bs(a, 1,1, d; 1,1,g, 1), B8(1,6,1,1;1,f, 1,1),
2.	134 specific graphs: 12 graphs of order 10, 42 graphs of order 11, and 80 graphs of order 12,
where a, 6, d, f, g are some positive integers.
M. R. Oboudi: Characterization of graphs with exactly two non-negative eigenvalues
285
Theorem 3.10. Let G = Bg(ai, , a3, a5, a6, a7, a8; ag), where ai,..., ag are some positive integers. Then A2(G) > 0 and A3(G) < 0 if and only if G is isomorphic to one of the following graphs:
1.	Bg(1,b, 1, 1;1,f, 1,1; k),
2.	59 specific graphs: 3 graphs of order 10, 17 graphs of order 11, and 39 graphs of order 12,
where b, f, k are some positive integers.
Remark 3.11. The complete list of the mentioned 25 graphs in Theorem 3.5, 63 graphs in Theorem 3.6, 145 graphs in Theorem 3.7, 143 graphs in Theorem 3.8, 134 graphs in Theorem 3.9 and 59 graphs in Theorem 3.10 can be obtained from the author upon request.
Theorem 3.12. Let G = Bi0(ai , a2, a3, a4, a5; ag, a7, ag, ag, ai0), where ai, . . . , ai0 are some positive integers. Then A2(G) > 0 and A3(G) < 0 if and only if G is isomorphic to one of the following 26 graphs:
1.	Bi0(1	1	1	1	1;	1	1	1 1 1				
2.	Bi0(1	1	1	1	2;	1	1	1 1 1	, Bi0(1,1,1 ,2 , 1; 1		1,1,	1, 1 ,
3.	Bi0(1	1	2	1	1;	1	1	1 1 1	, Bi0(1,2,1 ,1 , 1; 1		1,1,	1, 1 ,
4.	Bi0(2	1	1	1	1;	1	1	1 1 1				
5.	Bi0(1	1	1	1	3;	1	1	1 1 1	, Bi0(1,1,1 ,2 , 1; 1		1,1,	1, 2 ),
6.	Bi0(1	1	1	2	1;	1	1	1 2 1	, Bi0(1,1,1 ,	2, 2; 1,	1,1,	1, 1 ,
7.	Bi0(1	1	1	3	1;	1	1	1 1 1	, Bi0(1,1,2,	1,1; 1	1,1,	1, 2 ),
8.	Bi0(1	1	2	2	1;	1	1	1 1 1	, Bi0(1,1,3,	1,1; 1	1,1,	1, 1 ,
9.	Bi0(1	2	1	1	1;	1	1	2 1 1	, Bi0(1,2,1 ,	1,1; 1	2, 1,	1, 1 ,
10.	Bi0(1	2	1	1	2;	1	1	1 1 1	, Bi0(1,2,2 ,	1,1; 1	1,1,	1, 1 ,
11.	Bi0(1	3	1	1	1;	1	1	1 1 1	, Bi0(2,1,1 ,	1,1; 1	1,1,	2, 1 ,
12.	Bi0(2	1	1	1	1;	1	1	2 1 1	, Bi0(2,1,1 ,	1,1;2	1, 1, 1, 1 ,	
13.	Bi0(2	1	1	1	2;	1	1	1 1 1	, Bi0(2,1,1 ,	2,1; 1	1, 1, 1, 1 ,	
14.	Bi0(2	2	1	1	1;	1	1	1 1 1	, Bi0(3,1,1 ,1 , 1; 1		1, 1, 1, 1 .	
Proof. One can see that all of the above graphs have positive second largest eigenvalue and negative third largest eigenvalue. Now we prove the necessity. Let G = Bi0(ai,..., a5; a6, ..., ai0) such that A2(G) > 0 and A3(G) < 0. We show that for i = 1,..., 10, < 3. For example by contradiction suppose that ai > 4. Thus H = Bi0(4,1,1,1,1; 1,1,1,1,1) is an induced subgraph of G. So by Interlacing Theorem 2.1, A3(G) > A3(H). On the other hand A3(H) > 0, a contradiction. Similarly we obtain a2,..., ai0 < 3. Also one can
286
Ars Math. Contemp. 12 (2017) 383-413
see that at most one of the numbers a^ ..., a10 is 3. For example if a1 = 3 and a2 = 3, then K = B10(3,3,1,1,1; 1,1,1,1,1) is an induced subgraph of G. So by Interlacing Theorem 2.1, A3(G) > A3(K) while A3(K) > 0, a contradiction. Since a1,..., a10 < 3 and at most one of them is 3, a1 + • • • + a10 < 21. Thus the order of G is at most 21. Now by computer one can check the result.	□
Theorem 3.13. Let G = B11(a1, a2, a3, a4, a5; a6, a7, a8, ag, a1o; an), where a1,..., an are some positive integers. Then A2 (G) > 0 and A3(G) < 0 if and only if G is isomorphic to one of the following 5 graphs:
1.	B11(1,1,1,1,1; 1,1,1,1,1; 1),
2.	B11(1,1,1,1,1; 1,1,1,1,1; 2), B11(1,1,1,1, 2; 1,1,1,1,1; 1),
3.	B11(1, 2,1,1,1; 1,1,1,1,1; 1), B11(1,1, 2,1,1; 1,1,1,1,1; 1).
Theorem 3.14. Let G = B12(a1, a2, a3, a4, a5, a6; a7, a8, ag, a10, an, a12), where a1,..., a12 are some positive integers. Then A2(G) > 0 and A3(G) < 0 if and only if G = B12(1,1,1,1,1,1; 1,1,1,1,1,1).
Acknowledgements
The author is grateful to the referees for their useful comments. References
[1]	A. Abdollahi, Sh. Janbaz and M. R. Oboudi, Distance between spectra of graphs, Linear Algebra Appl. 466 (2015), 401-408.
[2]	A. Abdollahi and M. R. Oboudi, Cospectrality of graphs, Linear Algebra Appl. 451 (2014), 169-181.
[3]	D. M. Cvetkovic, M. Doob and H. Sachs, Spectra of graphs: Theory and application, Academic Press, Inc., New York-London, 1980.
[4]	C. Godsil and G. Royle, Algebraic graph theory, Springer-Verlag, New York, 2001.
[5]	M. R. Oboudi, Bipartite graphs with at most six non-zero eigenvalues, Ars Math. Contemp. 11 (2016), 315-325.
[6]	M. R. Oboudi, Cospectrality of complete bipartite graphs, Linear Multilinear Algebra 64 (2016), 2491-2497.
[7]	M. R. Oboudi, On the third largest eigenvalue of graphs, Linear Algebra Appl. 503 (2016), 164-179.
[8]	M. R. Oboudi, On the difference between the spectral radius and the maximum degree of graphs, to appear.
[9]	M. Petrovic, Graphs with a small number of nonnegative eigenvalues, Graphs Combin. 15 (1999), 221-232.
[10] J. H. Smith, Symmetry and multiple eigenvalues of graphs, Glasnik Mat. Ser. III 12 (1977), 3-8.