ARS MATHEMATICA CONTEMPORANEA ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 17 (2019) 319-347 https://doi.org/10.26493/1855-3974.1516.58f (Also available at http://amc-journal.eu) On graphs with exactly two positive eigenvalues* Fang Duan t College of Mathematics and Systems Science, Xinjiang University, Urumqi, P. R. China School of Mathematics Science, Xinjiang Normal University, Urumqi, P. R. China Qiongxiang Huang * College of Mathematics and Systems Science, Xinjiang University, Urumqi, P. R. China Xueyi Huang § School of Mathematics and Statistics, Zhengzhou University, Zhengzhou, P. R. China Received 27 October 2017, accepted 28 May 2019, published online 30 October 2019 The inertia of a graph G is defined to be the triplet In(G) = (p(G), n(G), n(G)), where p(G), n(G) and n(G) are the numbers of positive, negative and zero eigenvalues (including multiplicities) of the adjacency matrix A(G), respectively. Traditionally p(G) (resp. n(G)) is called the positive (resp. negative) inertia index of G. In this paper, we introduce three types of congruent transformations for graphs that keep the positive inertia index and negative inertia index. By using these congruent transformations, we determine all graphs with exactly two positive eigenvalues and one zero eigenvalue. Keywords: Congruent transformation, positive (negative) inertia index, nullity. Math. Subj. Class.: 05C50 *The authors are grateful to the anonymous referees for their useful and constructive comments, which have considerably improved the presentation of this paper. t Supported by the Scientific Research Projects of Universities in Xinjiang Province (No. XJEDU2019Y030). * Corresponding author. Supported by the National Natural Science Foundation of China (Nos. 11671344, 11531011). § Supported by the China Postdoctoral Science Foundation (No. 2019M652556), and the Postdoctoral Research Sponsorship in Henan Province (No. 1902011). E-mail addresses: fangbing327@126.com (Fang Duan), huangqx@xju.edu.cn (Qiongxiang Huang), huangxy@zzu.edu.cn (Xueyi Huang) Abstract ©® This work is licensed under https://creativecommons.org/licenses/by/4.0/ 320 Ars Math. Contemp. 17 (2019) 291-310 1 Introduction All graphs considered here are undirected and simple. For a graph G, let V(G) and E(G) denote the vertex set and edge set of G, respectively. The order of G is the number of vertices of G, denoted by |G|. For v e V(G), we denote by NG(v) = {u e V(G) | uv e E(G)} the neighborhood of v, NG[v] = NG(v) U {v} the closed neighborhood of v and d(v) = |NG(v)| the degree of v. A vertex of G is said to be pendant if it has degree 1. By ¿(G) we mean the minimum degree of vertices of G. As usual, we denote by G + H the disjoint union of two graphs G and H, Kni . . . the complete multipartite graph with 1 parts of sizes n^ ..., n;, and Kn, Cn, Pn the complete graph, cycle, path on n vertices, respectively. The adjacency matrix of G,denotedby A(G) = (aij), is the square matrix with aij = 1 if vi and vj are adjacent, and aij = 0 otherwise. Clearly, A(G) is a symmetric matrix with zeros on the diagonal, and thus all the eigenvalues of A(G) are real, which are defined to be the eigenvalues of G. The multiset consisting of eigenvalues along with their multiplicities is called the spectrum of G denoted by Spec(G). To characterize graphs in terms of their eigenvalues has always been of the great interests for researchers, for instance to see [2, 4, 5, 8, 9] and references therein. The inertia of a graph G is defined as the triplet In(G) — (p(G), n(G), n(G)), where p(G), n(G) and n(G) are the numbers of positive, negative and zero eigenvalues (including multiplicities) of G, respectively. Traditionally p(G) (resp. n(G)) is called the positive (resp. negative) inertia index of G and n(G) is called the nullity of G. Obviously, p(G) + n(G) = r(G) = n — n(G) if G has n vertices, where r(G) is the rank of A(G). Let B and D be two real symmetric matrices of order n. Then D is called congruent to B if there is an real invertible matrix C such that D = CTBC. Traditionally we say that D is obtained from B by congruent transformation. The famous Sylvester's law of inertia states that the inertia of two matrices is unchanged by congruent transformation. Since the adjacency matrix A(G) of G has zero diagonal, we have p(G) > 1 if G has at least one edge. One of the attractive problems is to characterize those graphs with a few positive eigenvalues. In [9] Smith characterized all graphs with exactly one positive eigenvalue. Recently, Oboudi [6] completely determined the graphs with exactly two nonnegative eigenvalues, i.e., those graphs satisfying p(G) = 1 and n(G) = 1 or p(G) = 2 and n(G) = 0. In this paper, we introduce three types congruent transformations for graphs. By using these congruent transformations and Oboudi's results in [6], we completely characterize the graphs satisfying p(G) = 2 and n(G) = 1. 2 Preliminaries In this section, we will introduce some notions and lemmas for the latter use. Theorem 2.1 (Interlacing theorem [1]). Let G be a graph of order n and H be an induced subgraph of G with order m. Suppose that Ai(G) > • • • > An(G) and Ai(H) > • • • > Am(H) are the eigenvalues of G and H, respectively. Then for every 1 < i < m, Aj(G) > Ai(H) > An-m+i (G). Lemma 2.2 ([1]). Let H be an induced subgraph of graph G. Then p(H) < p(G). F. Duan, Q. Huang and X. Huang: On graphs with exactly two positive eigenvalues 321 Lemma 2.3 ([3]). Let G be a graph containing a pendant vertex, and let H be the induced subgraph of G obtained by deleting the pendant vertex together with the vertex adjacent to it. Then p(G) = p(H) + 1, n(G) = n(H) + 1 and n(G) = n(H). Lemma 2.4 (Sylvester's law of inertia). If two real symmetric matrices A and B are congruent, then they have the same positive (resp., negative) inertia index, the same nullity. Theorem 2.5 ([9]). A graph has exactly one positive eigenvalue if and only if its nonisolated vertices form a complete multipartite graph. Let Gi be a graph containing a vertex u and G2 be a graph of order n that is disjoint from G1. For 1 < k < n, the k-joining graph of G1 and G2 with respect to u, denoted by G1 (u) ©k G2, is a graph obtained from G1 U G2 by joining u to arbitrary k vertices of G2. By using the notion of k-joining graph, Yu et al. [11] completely determined the connected graphs with at least one pendant vertex that have positive inertia index 2. Theorem 2.6 ([11]). Let G be a connected graph with pendant vertices. Then p(G) = 2 if and only if G = K1,r (u) ©k Kni,...,ni, where u is the center of K1,r and 1 < k < n1 +-----+ ni. Theorem 2.7 ([6]). Let G be a graph of order n > 2 with eigenvalues A 1(G) > • • • > An(G). Assume that A3(G) < 0, then the following hold: (1) If A 1(G) > 0 and A 2(G) = 0, then G = Kx + Kn-1 or G = K„ \ e for e G E (Kn); (2) If A1(G) > 0 and A2(G) < 0, then G = Kn. Let H be set of all graphs satisfying A2(G) > 0 and A3(G) < 0 (in other words, p(G) = 2 and n(G) = 0). Oboudi [6] determined all the graphs of H. To give a clear description of this characterization, we introduce the class of graphs Gn defined in [6]. For every integer n > 2, let Kpn] and Kpnj be two disjoint complete graphs with vertex set V = {v1,..., vpn]} and W = {w1,..., w\_nj}. Gn is defined to be the graph obtained from Kpn] and Kpnj by adding some edges distinguishing whether n is even or not below: 2 2 (1) If n is even, then add some new edges to Kn + Kn satisfying 0 = Nw(V1) C NW(V2) = {wn} C NW(V3) = {wn,wn-1} C ••• C NW(v2-1) = {w2,..., w3} C nw (vn) = {wn,..., w2}. (2) If n is odd, then add some new edges to K n+i + K n-i satisfying 2 2 0 = NW(v1) C NW(v2) = {wn—i } C NW(v3) = {wn—i , wn—i-1} C • • • C Nw (v n+i -1) = {w n-i , . . . , w2} C Nw (v n+i ) = {w n-i , . . . , w1}. By deleting the maximum (resp. minimum) degree vertex from Gn+1 if n is an even (resp. odd), we obtain Gn. It follows the result below. Remark 2.8 (See [6]). Gn is an induced subgraph of Gn+1 for every n > 2. 322 Ars Math. Contemp. 17 (2019) 291-310 Figure 1: G5, G6, Gt and Gt+1. For example, G2 = 2K1, G3 = P3 and G4 = P4. The graphs G5 and G6 are shown in Figure 1. In general, Gt and Gt+1 are also shown in Figure 1 for an even number t. Let G be a graph with vertex set {v1,..., vn}. By G[Ktl,..., Ktn] we mean the generalized lexicographic product of G (by Ktl, Kt2,..., Ktn), which is the graph obtained from G by replacing the vertex vj with Ktj and connecting each vertex of Kti to each vertex of Ktj if vj is adjacent to vj in G. Theorem 2.9 ([6]). Let G e H of order n > 4 with eigenvalues A1(G) > • • • > An(G). (1) If G is disconnected, then G = Kp + Kq for some integers p, q > 2; (2) If G is connected, there exist some positive integers s and t1,... ,ts such that G = Gs[Ktl,..., Kts ] where 3 < s < 12 and t1 + • • • + ts = n. Furthermore, Oboudi gave all the positive integers t1,... ,ts such that Gs [Ktl,..., Kts] e H in Theorems 3.4-3.14 of [6]. Let G be the set of all graphs with positive inertia index p(G) = 2 and nullity n(G) = 1. In next section, we introduce some new congruent transformations for graph that keep to the positive inertia index. By using such congruent transformations we characterize those graphs in G based on H. 3 Three congruent transformations of graphs In this section, we introduce three types of congruent transformations for graphs. Lemma 3.1 ([10]). Let u, v be two non-adjacent vertices of a graph G. If u and v have the same neighborhood, then p(G) = p(G — u), n(G) = n(G — u) and n(G) = n(G — u) +1. Remark 3.2. Two non-adjacent vertices u and v are said to be congruent vertices ofl-type if they have the same neighbors. Lemma 3.1 implies that if one of congruent vertices of I-type is deleted from a graph then the positive and negative inertia indices left unchanged, but the nullity reduces just one. Conversely, if we add a new vertex that joins all the neighbors of some vertex in a graph (briefly we refer to add a vertex of I-type in what follows) then the positive and negative inertia indices left unchanged, but the nullity adds just one. The graph transformation of deleting or adding vertices of I-type is called the (graph) transformation of I-type. Since Spec(Ks) = [(s — 1)1, ( —1)s-1]. By applying the transformation of I-type, we can simply find the inertia of Kni jn2 ... ns. F. Duan, Q. Huang and X. Huang: On graphs with exactly two positive eigenvalues 323 Corollary 3.3. Let G = Kn be a multi-complete graph where n1 > n2 > • • • > ns and i0 = min{1 < i < s | n > 2}. Then G has the inertia index: In(G) = (p(G), n(G), n(G)) = (1, ni0 + nio+1 +-----+ ns - s + io - 1, s - 1). The following transformation was mentioned in [4], but the author didn't prove the result. For the completeness we give a proof below. Lemma 3.4. Let {u, v, w} be an independent set of a graph G. If N (u) is a disjoint union of N(v) and N(w), thenp(G) = p(G — u), n(G) = n(G — u) and n(G) = n(G — u) +1. Proof. Since u,v,w are not adjacent to each other, we may assume that (0,0,0, aT), (0,0,0,flT) and (0,0, 0,yt) are the row vectors of A(G) corresponding to the vertices u, v, w, respectively. Thus A(G) can be written as A(G) 000 000 000 \ flT \a fl Y A(G — u — v — w)y Since N (u) = N (v) U N (w) and N (v) n N (w) = 0, we have a = fl + y .By letting the u-th row (resp. u-th column) minus the sum of the v-th and w-th rows (resp. the sum of the v-th and w-th columns) of A(G), we get that A(G) is congruent to 000 000 000 0T flT yt \ \0 fl Y A(G — u — v — w)/ 0 0T 0 A(G — u) Thus p(G) = p(G — u), n(G) = n(G — u) and n(G) = n(G — u) + 1 by Lemma 2.4. □ Remark 3.5. The vertex u is said to be a congruent vertex ofII-type if there exist two non-adjacent vertices v and w such that N(u) is a disjoint union of N(v) and N(w). Lemma 3.4 implies that if one congruent vertex of II-type is deleted from a graph then the positive and negative indices left unchanged, but the nullity reduces just one. Conversely, if there exist two non-adjacent vertices v and w such that N(v) and N(w) are disjoint, we can add a new vertex u that joins all the vertices in N(v) U N(w) (briefly we refer to add a vertex of II-type in what follows), then the positive and negative inertia indices left unchanged, but the nullity adds just one. The graph transformation of deleting or adding vertices of II-type is called the (graph) transformation ofII-type. An induced quadrangle C4 = uvxy of G is called congruent if there exists a pair of independent edges, say uv and xy in C4, such that N(u) \ {v, y} = N(v) \ {u, x} and N(x) \ {y, v} = N(y) \ {x, u}, where uv and xy are called a pair of congruent edges of C4. We call the vertices in a congruent quadrangle the congruent vertices ofIII-type. Lemma 3.6. Let u be a congruent vertex ofIII-type in a graph G. Then p(G) = p(G — u), n(G) = n(G — u) and n(G) = n(G — u) + 1. a Y Proof. Let C4 = uvxy be the congruent quadrangle of G containing the congruent vertex u. Then (0,1,0,1, aT), (1,0,1,0, aT), (0,1,0,1, flT), (1,0,1,0, flT) are the row vectors 324 Ars Math. Contemp. 17 (2019) 291-310 A(G) of A(G) corresponding to the vertices u, v, x and y, respectively. Thus A(G) can be presented by aT \ aT P T P T A(G — u — v — x — y) J By letting the u-th row (resp. u-th column) minus the x-th row (resp. x-th column) of A(G), and letting the v-th row (resp. v-th column) minus the y-th row (resp. y-th column) of A(G), we obtain that A(G) is congruent to 0 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0 a a P P B I 0 0 0 0 0 0 00 0 1 1 0 \a — P a — P P aT — PT aT — PT PT PT P A(G — u — v — x — y)y 0 0 0 0 0T \ 0 0 1 0 aT 0 1 0 1 PT 0 0 1 0 PT 0 a P P A(G — u — v — x — y)/ Again, by letting the u-th row (resp. u-th column) minus the v-th row (resp. v-th column) of B, and adding the y-th row (resp. y-th column) to the v-th row (resp. v-th column) of B, we obtain that B is congruent to 0 0T 0 A(G — u) Thus p(G) = p(G — u), n(G) = n(G — u) and n(G) = n(G — u) + 1 by Lemma 2.4. □ Remark 3.7. The Lemma 3.6 confirms that if a congruent vertex of III-type is deleted from a graph then the positive and negative inertia indices left unchanged, but the nullity reduces just one. Conversely, if we add a new vertex to a graph that consists of a congruent quadrangle with some other three vertices in this graph (briefly we refer to add a vertex of III-type in what follows) then the positive and negative inertia indices left unchanged, but the nullity adds just one. The graph transformation of deleting or adding vertices of III-type is called the (graph) transformation of III-type. Remark 3.2, Remark 3.5 and Remark 3.7 provide us three transformations of graphs that keep the positive and negative inertia indices and change the nullity just one. By applying these transformations we will construct the graphs in G. Let Gi be the set of connected graphs each of them is obtained from some H G H by adding one vertex of I-type, G2 be the set of connected graphs each of them is obtained from some H g H by adding one vertex of II-type and G3 be the set of connected graphs each of them is obtained from some H G H by adding one vertex of III-type. At the end of this section, we would like to give an example to illustrate the constructions of the graphs in Gi (i =1,2, 3). Example 3.8. We know the path P4, with spectrum Spec(P4) = {1.6180,0.6180, —0.6180, —1.6180}, is a graph belonging to H. By adding a vertex u of I-type to P4 we obtain H1 G G1 (see Figure 2) where Spec(H1) = {1.8478,0.7654,0, —0.7654, —1.8478}, F. Duan, Q. Huang and X. Huang: On graphs with exactly two positive eigenvalues 325 adding a vertex u of II-type to P4 we obtain H2 G £2 where Spec(H2) = {2.3028,0.6180, 0, -1.3028, -1.6180}. Finally, by adding a vertex u of III-type to P4 we obtain H3 G £3, where Spec(H3) = {2.4812,0.6889,0,-1.1701, -2}. In fact, uv and xy is a pair of independent edges in H3. Clearly, N(u) \ {v, y} = N(v) \ {u, x} = {w} and N(x) \ {y, v} = N(y) \ {x, u} = 0. Thus C4 = uvxy is a congruent quadrangle of H3. Clearly, G = K12 U P2 is a non-connected graph in £, and all such graphs we collect in £- = {G G £ | G is disconnected}. Additionally, H1 and H2 shown in Figure 2 are graphs with pendant vertex belonging to £, and all such graphs we collect in £+ = {G g £ | G is connected with a pendant vertex}. In next section, we firstly determine the graphs in £- and £+. 4 The characterization of graphs in G- and G+ The following result completely characterizes the disconnected graphs of £. Theorem 4.1. Let G be a graph of order n > 5. Then G G £- if and only if G = Ks + Kt + Ki,H + Ki or Ks + Kn-s \ e for e G E(Kn-s), where H gH is connected and s + t = n - 1, s, t > 2. Proof. All the graphs displayed in Theorem 4.1 have two positive and one zero eigenvalues by simple observation. Now we prove the necessity. Let G G £-, and Hi, H2,..., Hk (k > 2) the components of G. Since Ai(Hi) > 0 for i = 1,2,..., k and A4(G) < 0, G has two or three components and so k < 3. First assume that G = H1 + H2 + H3. It is easy to see that G has exactly one isolated vertex due to n(G) = 1 and p(G) = 2. Without loss of generality, let H3 = K1. Since A3(G) = 0 and A^Hi) > 0 (i = 1, 2), we have A2(H^ < 0 and A2(H2) < 0. By Theorem 2.7 (2), G = Ks + Kt + K1 as desired, where s +1 = n - 1 and s, t > 2. Next assume that G = H1 + H2. If H1 = K1, then A1(G) = A1 (H2) > A2(G) = A2(H2) > A3(G) = 0 = A1(H1) > A4(G) = A3(H2) < 0. Thus H2 H G H, and so G = H + K1 as desired. If |Hi| > 2 for i = 1, 2, then one of A2(H1) and A2(H2) is equal to zero and another is less than zero because A3(G) = 0 and A4(G) < 0. Without loss of generality, let A2(H1) < 0 and A2(H2) = 0. We have A3(H1) < A2(H1) < 0, in addition, A3(H2) < 0 since n(G) = 1. By Theorem 2.7 (2), H1 = Ks for some s > 2 and by Theorem 2.7 (1), H2 = Kn-s \ e. We complete this proof. □ In terms of Theorem 2.6, we will determine all connected graphs with a pendant vertex satisfying p(G) = 2 and n(G) = d for any positive integer d. 326 Ars Math. Contemp. 17 (2019) 291-310 Theorem 4.2. Let G be a connected graph of order n with a pendant vertex. Then p(G) = 2 and n(G) = d > 1 ifandonly if G = K^r (u) ©k Kni,...,ni, where r + ni + n2 + • • • + n, - (l + 1) = d. Proof. Let G = K1,r(u) ©k Kni,...,ni and vu is a pendant edge of G. By deleting v and u from G we obtain H = G — {u, v} = (r — 1)K1 U Kni ,...,ni. It is well known that p(Kni,...,ni) = 1 and n(Kni,...,ni) = n1 + • • • + n; — l. From Lemma 2.3, we have p(G) = p(H) + 1 = p(K„i,...,ni) + 1 = 2, n(G) = n(H) = (r — 1) + (ni + • • • + n; — l) = d. Conversely, let G be a graph with a pendant vertex and p(G) = 2. By Theorem 2.6, we have G = K1r (u) ©k Kni,...,ni. According to the arguments above, we know that n(G) = r + n1 + n2 + ••• + n; —' (l + 1) = d. □ From Theorem 4.2, it immediately follows the result that completely characterizes the graphs in G+. Corollary 4.3. A connected graph G G G+ if and only if G = K1,2(u) ©k Kn-3 or G ^ K1,1(u) ©k K„-2 \ e for e G E(K„_2). Proof. By Theorem 4.2, we have G G G+ if and only if G = K1,r(u) ©k Kni,...,ni, where r + n1 + n2 + • • • + n; — (l +1) = 1 and r, l, n1,..., n; > 1. It gives two solutions: one is r = 2, n1 = n2 = • • • = n; = 1 and l = n — 3 which leads to G = K12(u) ©k Kn-3; another is r =1, n1 = 2, n2 = • • • = n; = 1 and l = n — 2 which leads to G = KM(u) ©k K„_2 \ e for e G E(K„_2). □ Let G* denote the set of all connected graphs in G without pendant vertices. Then G = G- U G+ U G*. Therefore, in order to characterize G, it remains to consider those graphs in G *. 5 The characterization of graphs in G * First we introduce some symbols which will be persisted in this section. Let G G G*. The eigenvalues of G can be arranged as: A1(G) > A2(G) > As(G) =0 > A4(G) > • • • > A„(G). We choose v* g V(G) such that dG(v*) = ¿(G) = t, and denote by X = NG(v*) and Y = V(G) — NG[v*]. Then t = |X| > 2 since G has no pendant vertices. In addition, |Y | > 0 since otherwise G would be a complete graph. First we characterize the induced subgraph G[Y] in the following result. Lemma 5.1. G[Y] = K„_t-1 \ e, K1 + K„_t-2 or Kn_i_1. Proof. First we suppose that Y is an independent set. If |Y| > 3, then A4(G) > A4(G[YU{v*}]) = 0 by Theorem 2.1, a contradiction. Hence |Y| < 2, and so G[Y] = K1 or G[Y] = K2 \ e = 2K1. Next we suppose that G[Y] contains some edges. We distinguish the following three situations. F. Duan, Q. Huang and X. Huang: On graphs with exactly two positive eigenvalues 327 If A2(G[Y]) > 0, we have p(G[Y]) > 2. For any x e X, the induced subgraph G[{v*,x}U Y] has a pendant vertex v* by our assumption. By Lemma 2.2 and Lemma 2.3, we have p(G) > p(G[{v*,x}U Y ]) = p(G[Y]) + 1 > 3, a contradiction. If A2(G[Y]) < 0, by Theorem 2.7 (2) we have G[Y] = Kn-t-1 as desired. At last assume that A2(G[Y]) = 0. If A3(G[Y]) < 0, by Theorem 2.7 (1), we have G[Y] = Kn-t-1 \ e, Ki + Kn-t-2 as desired. If A3(G[Y]) = 0, by Lemma 2.3 we have p(G[{v*,x}u Y]) = p(G[Y]) + 1 = 2 and n(G[{v*,x}U Y]) = n(G[Y]) > 2, which implies that A4(G) > A4(G[{v*, x} U Y]) = 0, a contradiction. We complete this proof. □ First assume that Y = {y1}. If G[X] = Kt, then G = Kn \ v*y1. However Kn \ v*y1 e G* since p(Kn \ v*y1) = 1. Thus there exist x1 x2 in X. Then NG(x1) = NG(x2) and NG(v*) = NG(y1). It follows that n(G) > 2 by Lemma 3.1. Next assume that Y = {y1,y} is an independent set. We have NG(v*) = NG(y1) = NG(y) since dG(y1),dG(y) > dG(v*) = ¿(G). Thus, by Lemma 3.1 we have n(G) = n(G - y1) + 1 = n(G - y1 - y) + 2 > 2. Thus we only need to consider the case that G[Y] contains at least one edge. Concretely, we distinguish three situations in accordance with the proof of Lemma 5.1: (a) G[Y] = K„-t-2 + K1 in case of A2(G[Y]) =0 and A3(G[Y]) < 0, where n - t - 2 > 2; (b) G[Y] = K„-t-1 \ e in case of A2(G[Y]) = 0 and A3(G[Y]) < 0, where |Y| = n - t - 1 > 3; (c) G[Y] = Kn-t-1 in case of A2(G[Y]) < 0, where |Y| = n - t - 1 > 2. In the following, we deal with situation (a) in Lemma 5.2, (b) in Lemma 5.3 and (c) in Lemma 5.4, 5.7 and Lemma 5.15. We will see that the graph G e G* illustrated in (a) and (b) can be constructed from some H eH by the graph transformations of I-, II- and III-type, but (c) can not. Lemma 5.2. If G[Y] = Kn-t-2 + Kx, where n - t - 2 > 2, then G e G1. Proof. Since G[Y] is isomorphic to Kn-t-2 + K1 (n -1 - 2 > 2), Y exactly contains one isolated vertex of G[Y], say y. We have NG (v*) = NG (y) and thus y is a congruent vertex of I-type. By Lemma 3.1, we have p(G) = p(G - y) and n(G) = n(G - y) + 1. Notice that G - y is connected, we have G - y e H, and so G e G1. Such a graph G, displayed in Figure 3 (1), we call the v* -graph of I-type. □ In Figure 3 and Figure 5, two ellipses joining with one full line denote some edges between them. A vertex and an ellipse joining with one full line denote some edges between them, and with two full lines denote that this vertex joins all vertices in the ellipse. Two vertices join with same location of an ellipse denote that they have same neighbours in this ellipse. It needs to mention that the v*-graph of I-type characterized in Lemma 5.2, is a graph obtained from H e H by adding a new vertex joining the neighbors of a minimum degree vertex of H. For S C V(G) and u e V(G), let NS(u) = NG(u) n S and NS[u] = NG[u] n S. Lemma 5.3. Let G[Y] = Kn-t-1 \ e, where n -1 - 1 > 3 and e = yy'. Then G e G1 if NX (y) = NX(y') and G e G2 otherwise. 328 Ars Math. Contemp. 17 (2019) 291-310 Figure 3: The structure of some graphs. Proof. Since n - t - 1 > 3, there is y* G Y other than y and y'. It is clear that NG(y) = Nx (y) u (Y \ {y, y'}) and NG(y') = Nx (y') U (Y \ {y, y'}), and thus NG(y) = NG(y') if and only if NX (y) = NX (y'). We consider the following cases. Case 1. Nx(y) = Nx(y'). By assumption, NG(y) = NG(y'), thus y and y' are congruent vertices of I-type. By Lemma 3.1, we have p(G) = p(G - y) and n(G) = n(G - y) + 1. Since G - y is connected, we have G - y G H and so G G Gi. Such a G, displayed in Figure 3 (2), we call the Y-graph of I-type. Case 2. Nx(y) = Nx(y'). First suppose that exactly one of NX (y) and NX(y') is empty, say NX(y) = 0 and NX (y') = 0. Then yy* is a pendant edge of the induced subgraph G[X U {y, y', y*, v*}]. By Lemma 2.2 and Lemma 2.3, we have 2 = p(G) > p(G[X U {y, y', y*, v*}]) = p(G[X U {y', v*}]) + 1 > 2. Thus p(G[X U{y,y',y*,v*}]) = 2 and p(G[X U{y',v*}]) = 1. We see that A2(G[X U {y', v*}]) = 0 (since otherwise A2 (G[X U {y', v*}]) < 0 and then G[X U {y', v*}] is a complete graph, but y' ^ v*). If A3(G[X U {y', v*}]) = 0, we have n(G[X U {y, y', y*, v*}]) = n(G[X U {y', v*}]) > 2, which implies A4(G) > A4(G[X U{y,y',y*,v*}]) = 0, a contradiction. If A3(G[XU{y',v*}]) < 0, then G[XU{y',v*}] = K+ \e or Ki+i +Ki by Theorem 2.7 (1). Notice that G[X U {y', v*}] is connected, we get G[X U {y', v*}] = Ki+2 \ e where e = v*y'. Thus Nx (y') = X and so NG(y') = X U (Y \ {y,y'}) = NG(v*) U NG(y) is a disjoint union. Additionally, {y', v*, y} is an independent set in G, we see that y' is a congruent vertex of II-type. Thus p(G) = p(G - y') and n(G) = F. Duan, Q. Huang and X. Huang: On graphs with exactly two positive eigenvalues 329 Figure 4: The graphs r, r2,..., r 14. n(G - y') + 1 by Lemma 3.4. This implies that G - y' e H, and so G e G2. Such a G, displayed in Figure 3 (3), we call the (v*, Y)-graph ofII-type. Next suppose that NX(y),NX(y') = 0, without loss of generality, assume that NX(y') \ NX(y) = 0. Then there exists x' e NX(y') \ NX(y). Thus x' - y' and x' — y. Now by taking some x e NX (y), we see that C6 = v*xyy*y'x' is a 6-cycle in G. Note that x may joins each vertex in {x', y', y*} and x' may joins y*. By distinguishing different situations in according with the number of edges we have C6 no edge; r or r2 one edges; G[v*,x, y, y*,y',x'] = ^ r3, r4 or r5 two edges; r6, r7 or r8 three edges; r9 four edges. However C6 and ri,..., r8 and r9 are all forbidden subgraphs of G (see Figure 4). We complete this proof. □ It remains to characterize the graph G G G* satisfying G[Y] = Kn-t-1. Such a graph G we call X-complete if G[X] is also complete graph, and X-imcomplete otherwise. The following result characterizes the X-imcomplete graphs. Lemma 5.4. Let G[Y] = Kn_t_1, where n — t — 1 > 2, and G is X-imcomplete. Then G G G1 if there exist two non-adjacent vertices x1 ^ x2 in G[X] such that NY (x1) = Ny (x2) and G G G3 otherwise. Proof. Let X = jxb x2,...,xt} and Y = {y1,y2,... ,yn-t-1}. Then V(G) = {v*} U X U Y and Y induces Kn-t-1. Let x and x' be two non-adjacent vertices in X. Since dG(x) > dG(v*) and n — t — 1 > 2, we have |NY(x)| > 1 and |Y| > 2, respectively. First we give some claims. Claim 5.5. If x ^ x' in G[X] then one of NY(x) and NY(x') includes another If Ny(x) c Ny(x') then |NY(x)| = 1 and NY(x') = Y. 330 Ars Math. Contemp. 17 (2019) 291-310 Proof. On the contrary, let y e Ny(x) \ Ny(x') and y' e Ny(x') \ Ny(x), then G[v*, x, x', y, y'] = C5. Thus one of Ny(x) and Ny(x') includes another. Now assume that Ny(x) c Ny(x'). If |Ny(x)| > 2, say {y, y'} C Ny(x), then x' - y, y' and exists y* e Ny(x') \ Ny(x). Thus G[v*,x, x',y, y', y*] — r10 (see Figure 4). However p(r10) = 3. Hence |Ny(x)| = 1, and we may assume that Ny(x) = {y}. If Ny(x') = Y, then there exists y' e Y \ Ny (x'). Also, there exists y* e Ny (x') \ Ny (x). We have G[v*, x, x', y, y', y*] — r4 (see the labels in the parentheses of Figure 4), but p(r4) = 3. Thus Ny(x') = Y. □ Claim 5.6. If x - x' in G[X] then Nx (x) = Nx (x'). Proof. On the contrary, we may assume that x* e NX (x') \ NX (x). Then x* — x' and x* — x, thus |Ny(x)| > 2 since |NG(x)| > t. By Claim 5.5, we have Ny(x*), Ny(x') C Ny(x). Then either Ny(x*) = Ny(x') = Ny(x) or one of Ny(x*) and Ny(x') is a proper subset of Ny(x) (without loss of generality, assume that Ny(x*) c Ny(x), and then |Ny(x*)| = 1 and Ny (x) = Y by Claim 5.5). Suppose that Ny(x) = Ny(x*) = Ny(x'). Take y, y' e Ny(x), we see that G[v*,x,x*,x', y,y'] — rn (seeFigure4). Howeverp(rn) = 3. Suppose that |Ny (x* )| = 1 and Ny (x) = Y. Let Ny (x*) = {y} and there exists another y' e Y. Then G[v*, x, x*, x', y, y'] is isomorphic (see Figure 4) if x' — y, y', or isomorphic to (see Figure 4) if x' — y and x' — y', or isomorphic to rb4 (see Figure 4) if x' — y and x' — y'. Howeverp(r12) = p(r13) = 3 and A4(r14) = 0. We are done. □ Now we distinguish the following cases to prove our result. Case 1. There exist x1 — x2 such that Ny (x1) = Ny (x2). Since x1 — x2, we have NX(x1) = NX(x2) by Claim 5.6, so NG(x1) = NG(x2). Thus x1 and x2 are congruent vertices of I-type. By Lemma 3.1, p(G) = p(G - x1) and n(G) = n(G - x1) + 1. Thus G - x1 e H and so G e G1. Such a G, displayed in Figure 5 (1), we call the X-graph of I-type. Case 2. For each pair of x — x' e X, Ny (x) = Ny (x'). By Claim 5.5, without loss of generality, assume that Ny (x) c Ny (x') and then Ny (x) = {y} and Ny (x') = Y. Thus y — x, x' and furthermore we will show that X C NG(y). In fact, let x* e X \ {x, x'} (if any), if x — x*, we have Ny (x*) D Ny (x) = {y} by Claim 5.6. Thus y — x*. Otherwise, x — x* and thus x' — x* since NX (x) = NX(x') by Claim 5.6. Now take y' e Y \ {y}. If y — x*, then G[v*, x, x', x*, y, y'] is isomorphic to r12 (see the first labels in the parentheses of Figure 4) while x* — y', or isomorphic to r13 (see the labels in the parentheses of Figure 4) while x* — y',but p(r12) = p(r13) = 3. It follows that Ng (y) = X U (Y \ {y}) since Y induces a clique. On the other hand, since dG(x) > |X| = t, x — x' and Ny(x) = {y}, we have Nx (x) = X \ {x, x'} and so Nx(x') = X \ {x,x'} by Claim 5.6. Thus Ng(x) = (X \ {x, x'}) U {v*, y} and NG(x') = (X \ {x,x'}) U Y U {v*}. Hence the quadrangle C4 = xv*x'y is congruent, where xv* and x'y is a pair of congruent edges of C4. It gives that x, v*, x', y are congruent vertices of III-type. By Lemma 3.6, we have p(G) = p(G - x) and n(G) = n(G - x) + 1 thus G - x e H, and so G e G3. Such a G, displayed in Figure 5 (2), we call the (v*, X, Y)-graph of III-type. We complete this proof. □ F. Duan, Q. Huang and X. Huang: On graphs with exactly two positive eigenvalues 331 X-graph of I-type (v*, X, Y)-graph of Ill-type (X, Y)-graph of Ill-type (1) (2) (3) Figure 5: The structure of some graphs. At last we focus on characterizing X-complete graph G G G*, i.e., G[X] = Kt and G[Y] = Kn_t-1. A X-complete graph G G G* is called reduced if one of NY(xj) and NY (xj) is a subset of another for any xj = xj G X and non-reduced otherwise. Thus the X-complete graphs are partitioned into a disjoint union of the reduced and non-reduced X-complete graphs. Concretely, for a reduced X-complete graph G g G*, we may assume that 0 = Ny (v*) C Ny (x1) C Ny (x2) C ••• C NY (xt); for a non-reduced (X, Y )-complete graph G G G*, there exist some x = x' G X such that NY (x) \ NY (x') = 0 and Ny(x') \ Ny(x) = 0. Such vertices x and x' are called non-reduced vertices. It remains to characterize the reduced and non-reduced X-complete graphs in what follows. Lemma 5.7. Let G G G* be a non-reduced X-complete graph and x, x' be non-reduced vertices. Then G G G3. Proof. Since x,x' are non-reduced vertices, there exist y G NY (x) \ NY (x') and y' G Ny (x') \ Ny(x). Then x, x', y', y induces C4 (see Figure 5 (3)). It suffices to verify that C4 is congruent. Clearly, NG(x) D (X \ {x}) U {v*} and Ng(x') D (X \ {x'}) U {v*}. If there exists y* G NY(x) \ NY(x') other than y, then G[v*, x, x', y', y, y*] = r12 (see the second labels in the parentheses of Figure 4), however r12 is a forbidden subgraph of G. Hence NY(x) \ NY(x') = {y}. Similarly, NY(x') \ NY(x) = {y'}. On the other aspect, x G Nx (y)\Nx (y') and x' G Nx (y')\Nx (y). If there exists x* g Nx (y)\Nx (y') other than x, then G[v*, x, x', x*, y, y'] = r10 (see the labels in the parentheses of Figure 4), however r10 is a forbidden subgraph of G. Hence NX(y) \ NX(y') = {x}. Similarly, Nx (y')\Nx (y) = {x'}. Hence Nx (y)\{x} = Nx (y')\{x'}. Note that NG(y) D Y\{y} and NG(y') D Y \ {y'}, we have NG(y) \{y',x} = (Y \{y,y'}) U (Nx(y) \ {x}) = NG(y') \ {x', y}. Hence the quadrangle C4 = xx'y'y is congruent, where xx' and y'y is a pair of congruent edges. It follows that x, x', y', y are congruent vertices of III-type. By Lemma 3.6, we havep(G) = p(G - x) and n(G) = n(G - x) + 1. Thus G - x G H, and so G G G3. Such a G, displayed in Figure 5 (3), we call the (X, Y)-graph of III-type. We complete this proof. □ To characterize the reduced X-complete graph, we need the notion of canonical graph which is introduced in [7]. For a graph G, a relation p on V(G) we mean that upv iff u ^ v and Ng(u) \ v = Ng(v) \ u. Clearly, p is symmetric and transitive. In accordance with p, 332 Ars Math. Contemp. 17 (2019) 291-310 the vertex set is decomposed into classes: V(G) = Vi U V2 U • • • U Vfc, (5.1) where vj G Vj and V = {x G V(G) | xpv.j}. By definition of p, Vj induces a clique Kni where n1 + n2 + • • • + nk = n = | V(G) |, and vertices of Vj join that of Vj iff vj ~ vj in G. We call the induced subgraph G[{v1; v2,..., vk }] as the canonical graph of G, denoted by Gc. Thus G = Gc[Kni, K„2,..., K„fc ] is a generalized lexicographic product of Gc (by K„i ,K„2 ). Let G be a reduced X-complete graph. From (5.1) we have G = Gc[Kni, Kn2,..., Knk], where Gc = G[{v1; v2,..., vk}] and Vj = {x G V(G) | xpvj} induces clique K„.. Without loss of generality, assume v1 = v*. Let Xc = NGc (v1) and Yc = {v2, v3,..., vk} \ Xc. Clearly, Gc[Xc] is a clique since Xc is a subset of X and X induces a clique in G. Furthermore, Gc[Yc] is a clique since Yc is a subset of Y and Y induces a clique in G. Thus Gc is also a Xc-complete graph. Additionally, since G is reduced, Gc is also reduced. Let tc = dGc (v1) and Xc = {x1; x2,..., xtc}, Yc = {yi,y2, ...,yfc-tc-i}. We may assume Ny-c(vi) C Ny-c(xi) C ••• C Ny-c(xic) and Nx0(yi) C • • • C Nx0(yfc-te-i). Therefore, 0 = |Nyc(vi)| < |Nyc(xi)| < • • • < |Nyc(xic)| < |YC| = k — tc - 1, (5.2) and 0 < |Nx0(yi)| < |Nx0(y2)| < • • • < |NXo(yfc-t„-i)| < |XC| = tc. (5.3) From Equation (5.2), we have tc < k — tc — 1. Similarly, k — tc — 2 < tc from Equation (5.3). Thus k — 2 < 2tc < k — 1, and so tc = [f ] — 1. If k is even, then tc = f — 1. From Equation (5.2), we have |NYc(xj)| = i for i = 1, 2,..., tc. Thus we may assume that NYc (vi) = 0, (xi) = {y k }, NYc (x n-2) = {y k Nyc (x n-i) = {yk ,...,y2}. This implies that G = Gk where Gk is defined in Section 2. Similarly, G = Gk if k is odd. Thus we obtain the following result. Lemma 5.8. Let G be a reduced X-complete graph. Then Gc = Gk where k > 2 is determined in (5.1). Let G g G* be a reduced X-complete graph. The following lemma gives a characterization for G. First we cite a result due to Oboudi in [5]. Lemma 5.9 ([5]). Let G = G3[Kni, Kn2, Kn3], where ni, n2, n3 are some positive integers. Then the following hold: (1) If ni = n2 = n3 = 1, that is G = P3, then A3(G) = —%/2; (2) If ni = n2 = 1 and n3 > 2, then A3(G) = —1; F. Duan, Q. Huang and X. Huang: On graphs with exactly two positive eigenvalues 333 (3) If nin2 > 1, then A3(G) = -1. We know that any graph G is a generalized lexicographic product of its canonical graph, i.e., G = Gc [Kni, K„2,..., K„fc]. We also have Gc = Gk if G is reduced X-complete by Lemma 5.8. Furthermore, the following result prove that 4 < k < 13. Lemma 5.10. Let G G G* be a reduced X-complete graph. Then there exists 4 < k < 13 such that G = Gk [Kni, Kn2,..., Knk]. Proof. By Lemma 5.8, G = Gk [Kni, Kn2,..., K„fc] for some k. If k = 1 or 2 then G = K„ G G*, and so k > 3. If k = 3, then G = Gs[Kni, K„2, K„3]. Thus A3(G) < 0 by Lemma 5.9, a contradiction. Hence k > 4. On the other hand, since Gc — Gk is an induced subgraph of G, we have A4(Gk) < A4(G) < 0 by Theorem 2.1. Note that G14 is an induced subgraph of Gk (by Remark 2.8) for k > 15, we have A4(Gk) > A4(G14) = 0. It implies that k < 13. □ Next we consider the converse of Lemma 5.10. In other words, we will try to find the values of ni,... ,nfc such that p(Gfc[Kni,... ,K„fc]) = 2 and n(Gfc [Kni,... , K„fc]) = 1, where 4 < k < 13 and n = n1 + n2 + • • • + nk. For the simplicity, we use notation in [8] to denote G2S[K„i,... ,K„2s] = B2S(ni,... ,ns;ns+i,... ,n2S) and G2 s + 1 [Kni , . . . , Kn2s + i ] = B2s + 1 (n1, . . . ,ns; ns + ^ . . . ,n2s; n2s + 1). By Remark 3.2 in [6], we know Ho = B2S(n1,... ,ns; ns+1,... ,n2S) = B2S(ns+1... ,n2S; n1,... ,ns) = H0 and H1 = B2S+1(n1,..., ns; ns+1,..., n2S; n2S+1) = B2S+1(ns+1,... ,n2S; n1,... ,ns; n2S+1) = H'1. In what follows, we always take H0 and H1, in which (n1,..., ns) is prior to (ns+1,..., n2s) in dictionary ordering, instead of H0 and H'. For example we use B6(4,3, 2; 4, 3,1) instead of B6(4,3,1; 4, 3,2) and B7(5,3,2; 5, 2,4; 8) instead of B7(5, 2,4; 5,3, 2; 8). For 4 < k < 13, let Bfc(n) = {G = Bfc(n1,. .., nfc) | n = n1 +-----+ nfc, nj > 1}. Let B+(n), B0o(n), B0(n) and B-(n) denote the set of graphs in Bk (n) satisfying A3(G) > 0 for G G B+(n), A4(g) = A3(G) =0 for G G B00(n), A4(G) < A3(G) = 0 for G G B0(n) and A3(G) < 0 for G G B-(n), respectively. Clearly, Bk(n) = B+(n) U B00 (n) U B0(n) U B-(n) is disjoint union and G = G k [Kni, Kn2,..., Knk] G B 0 (n) if G G G* is a reduced X-complete graph by Lemma 5.10. In what follows, we further show that n < 13. First, one can verify the following result by using computer. Lemma 5.11. B°(14) = 0 for 4 < k < 13 (it means that there are no reducedX-complete graphs of order 14). Proof. For 4 < k < 13, the k-partition of 14 gives a solution (n1,n2,... ,n k) of the equation n1 + n2 + • • • + nk = 14 that corresponds a graph G = Bk(n1, n2,..., nk) G Bk (14). By using computer, we exhaust all the graphs of Bk (14) to find that there is no any graph G G Bk(14) with A4(G) < A3(G) = 0. It implies that B0(14) = 0. □ 334 Ars Math. Contemp. 17 (2019) 291-310 In [6], Oboudi gave all the integers n1,..., nk satisfying A2(Bk(n1,..., nk)) > 0 and A3(Bk (n1,..., nk)) < 0 for 4 < k < 9. For simplicity, we only cite this result for k = 5 and the others are listed in Appendix B. Theorem 5.12 ([6]). Let G = B5(n1, n2; n3, n4; n5), where n1, n2, n3, n4, n5 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) B5(a,w;1,1; 1); (6) B5(a1; x,w;1); (11) B5(x, w; 1, d; 1); (2) B5(a,x; 1, d; 1); (7) B;(a, 1; x,y; e); (12) B5(x,w;1,1; e); (3) B5(a,x;1,y; z); (8) B;(a, 1;1,d; e); (13) B5(1, b; 1, d; 1); (4) B5(a,x;1,1; e); (9) B5(w,x; y, 1; e); (14) B5(1,b;1,x; y); (5) B5(a, 1; c, 1; e); (10) B5(x,b;1,1;1); (15) B5(1,x;1,y; e); (16) 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. Lemma 5.13. Let G G Bk (n), where 4 < k < 9 and n > 14. If G G B-(n), then G has an induced subgraph r G Bk (14) \ B-(14). Proof. We prove this lemma by induction on n. If n = 14, since G G Bk (14)\B-(14), our result is obviously true by taking r = G. Let n > 15 and G' G Bk (n — 1) be an induced subgraph of G. If G' G B-(n — 1),then G' has an induced subgraph r G Bfc(14)\B-(14) by induction hypothesis, and so does G. Hence it suffices to prove that G contains an induced subgraph G' g Bk (n — 1) \ B- (n — 1) for n > 15 in the following. We will prove that there exists G' G B5(n — 1) \ B-(n — 1) for n > 15, and it can be similarly proved for the other k which we keep in the Appendix B. Let G = B5(n1, n2; n3, n4; n5) G B5(n). Then one of H1 = B5(n1 — 1,n2; n3,n4; n5), H2 = B5(n1,n2 — 1; n3,n4; n5), H3 = B5(n1,n2; n3 — 1,n4; n5), H4 = B5(n1,n2; n3,n4 — 1; n5) and H5 = B5(n1,n2; n3,n4; n5 — 1) must belong to B5(n— 1). On the contrary, assume that Hj G B-(n — 1) for i = 1, 2,..., 5. Then H is a graph belonging to (1) — (15) in Theorem 5.12 since |Hj| = n — 1 > 14. First we consider H1. If H1 is a graph belonging to (1) of Theorem 5.12, then H1 = B5(a, w; 1,1; 1) where n1 — 1 = a, n2 = w, n3 = n4 = n5 = 1, and hence G = B5(a +1, w; 1,1; 1) G B-(n), a contradiction. Similarly, H1 cannot belong to (2)-(8) of Theorem 5.12. If H1 is a graph belonging to (9) of Theorem 5.12, then H1 = B5(w, x; y, 1; e) where n1 — 1 = w, n2 = x, n3 = y, n4 = 1, n5 = e. Since w < 3, we have n1 < 4. If n1 < 4 then w + 1 < 3 and G = B5(w +1, x; y, 1; e) G B-(n), a contradiction. Now assume that n1 = 4. Then H1 = B5(3, x; y, 1; e). Since x, y G {1,2}, we have G g {B5(4,1;1,1; e), ^5(4,2; 1,1; e), B;(4,1;2, 1; e), B;(4, 2; 2,1; e)}. However B5(4,1; 1,1; e), ^5(4,2; 1,1; e), £5(4,1; 2, 1; e) belong to (4), (5) of Theorem 5.12 which contradicts our assumption. Thus G = B5(4, 2; 2,1; e). By Theorem 5.12, G = F. Duan, Q. Huang and X. Huang: On graphs with exactly two positive eigenvalues 335 B5(4,2; 2,1; e) G B5-(n), and also its induced subgraph Bs(4, 2; 2,1; e — 1) £ B5-(n — 1), a contradiction. Hence Hi belongs to (10) - (15) of Theorem 5.12, from which we see that ni — 1 is either x or 1. Thus ni < 3 due to x < 2. By the same method, we can verify that n2 < 3 if H2 e B-(n — 1); n3 < 3 if H3 g B-(n — 1); n4 < 3 if H4 G B-(n — 1) and n5 < 2 if H5 G B5-(n — 1). Hence n = ni + • • • + n5 < 14, a contradiction. We are done. □ Lemma 5.14 ([6]). If n > 14, then B-(n) = 0 for 10 < k < 13. Lemma 5.15. Given 4 < k < 13, B0(n) = 0 for n > 14 (it means that there are no reduced X-complete graphs of order n > 14). Proof. Let G e B0 (n) and n > 14. Then A4(G) < A3(G) = 0. First we assume that 4 < k < 9. Since G £ B-(n), G has an induced subgraphs r e B (14) \ B-(14) by Lemma 5.13. Thus A3(r) > 0. Furthermore, we have A3(r) = 0 since otherwise 0 < A3(r) < A3(G). Additionally, A4(r) < A4(G) < 0, we have r e B0(14), contrary to Lemma 5.11. Next we assume that 10 < k < 13. By deleting n — 14 vertices from G, we may obtain an induced subgraph r e Bk (14). By Lemma 5.14, we have A3(r) > 0, and then A3(r) =0 by the arguments above. Additionally, A4(r) < A4(G) < 0, we have r e B0 (14) which also contradicts Lemma 5.11. □ By Lemma 5.15, we know that, for any reduced X-complete graph G e G*, there exists 4 < k < 13 and n < 13 such that G e B0(n). Let B* = {G = Bk(ni, n2,..., nk) e B0(n) | 4 < k < 13 and n < 13}. Thus G e G* is a reduced X-complete graph if and only if G e B*. Remark 5.16. Clearly, B = U4 5. Then G e G if and only if G is isomorphic to one of the following graphs listed in (1), (2) and (3): (1) Ki,2(u) ©k Kn-3 or Ki,i(u) ©k Kn_2 \ e for e e E(Kn-2); (2) the graphs belonging to Gi, G2 or G3; (3) the 802 specific graphs belonging to B* some of which we list in Table 1. If G* is obtained from G e G by adding one vertex of I, II or III-type, then the positive and negative indices of G* left unchanged, but the nullity adds just one. Repeating this process, we can get a class of graphs which has two positive eigenvalues and s zero eigenvalues, where s > 2 is any integer. However, by using the I, II and III-type (graph) transformations, we can not get all such graphs. For example, H = Bi0(1,1,2,3, 2; 1,1,1,1,1) is a graph satisfying p(H) = 2 and n(H) = 2 that can not be constructed by above (graph) transformation. Hence the characterization of graphs with p(H) = 2 and n(H) = s (especially n(H) = 2) is also an attractive problem. 336 Ars Math. Contemp. 17 (2019) 291-310 Table 1: All graphs of B* B* S4 3, 2 3, 2); £4(4, 3; 2 £4 3, 4 2, 3), £4(4,1; 3 £4 7, 2 2, 2), £4(3, 6; 2 £4 3, 6 3, 1), £4(6,1; 3 £5 2, 2 2, 2 1); £5(2,3 £5 3, 4 1, 2 1), £5(1, 3 £5 4, 2 3, 1 1); £5(4, 5 £5 1, 4 1, 2 4), £5(3, 2 £5 1, 4 1, 4 2), £5(3, 2 £5 3, 1 2, 5 1), 55(4,1 £5 2, 7 1, 1 2), £5(6, 3 £5 2, 7 1, 2 1), £5(6, 3 £5 1, 3 1, 2 6), £5(2, 2 £5 2, 4 1, 5 1), £5(3, 3 £5 7, 2 2, 1 1), £5(4, 2 £5 5, 1 2, 4 1), £5(3, 2 Number 2), B4(4, 3; 3,1); £4(5,4; 2,1), £4(5, 2; 2, 3), 4), £4(5, 2; 4,1); £4(7, 3; 2,1), £4(4, 6; 2,1), 2), £4(4, 2; 2, 5), £4(3, 3; 2, 5), £4(7, 2; 3,1), 3), £4(6,1; 4, 2). 18 ; 2), £5 ; 3), £5 ; 1), £5 ;4), £5 ; 2), £5 ; 2); £5 ; 2), £5 ; 1), £5 ; 6), £5 ; 1), £5 ;4), £5 ;4), £5 (3, 3 (2, 2 (2, 5 (2, 5 (5, 2 (3, 7 (2, 4 (1, 6 (1, 6 (2, 2 (2, 3 (6, 1 2, 1 1, 3 1, 1 1, 3 2, 1 1, 1 1, 1 1, 2 1, 3 1, 6 2, 1 3, 2 ß5(3,4; 1,1; 2), £5(2,4; ß5(4, 3; ß5(4, 3; £5(3,1; £5(6,4; £5(3, 3; ß5(5, 2; ß5(5, 2; £5(2, 7; £5(5,1; 2, 3; 2) 47 See Table 2 of Appendix A 138 See Table 3 of Appendix A 161 See Table 4 of Appendix A 205 See Table 5 of Appendix A 124 10 See Table 6 of Appendix A 78 11 ßii(1 ßii(1 ßii(1 ßii(1 £ii(1 ßii(2 £ii(1 £ii(1 £ii(1 £ii(1 ßii(1 ßii(2 1), ßii(2,1 1), ßii(1,1 1), ßii(1,1 1), ßii(1, 2 1), ßii(1, 3 1), ßii(2, 2 2), ßii(1,1 2), ßii(1,1 1), ßii(1,1 1), ßii(1, 2 1), ßii(1, 2 1), ßii(1, 2 1); 1), 1), 1), 1), 1), 2), 3), 1), 1), 1), 1). 24 12 Si2(1 Si2(1 £i2 (1 1, 1), Si2(1 1, 1), Si2(1 1, 1), Si2(2 1, 1, 1), 1, 1, 1), 1, 1, 1). 13 ßis(1 1, 1; 1). k 4 5 6 7 8 9 6 1 1 1 1 1 1 1 1 1 References [1] D. M. Cvetkovic, M. Doob and H. Sachs, Spectra of Graphs: Theory and Application, volume 87 of Pure and Applied Mathematics, Academic Press, New York, 1980. [2] C. Godsil and G. Royle, Algebraic Graph Theory, volume 207 of Graduate Texts in Mathemat- F. Duan, Q. Huang and X. Huang: On graphs with exactly two positive eigenvalues 337 ics, Springer-Verlag, New York, 2001, doi:10.1007/978-1-4613-0163-9. [3] H. Ma, W. Yang and S. Li, Positive and negative inertia index of a graph, Linear Algebra Appl. 438 (2013), 331-341, doi:10.1016/j.laa.2012.07.014. [4] M. R. Oboudi, Bipartite graphs with at most six non-zero eigenvalues, Ars Math. Contemp. 11 (2016), 315-325, doi:10.26493/1855-3974.749.264. [5] M. R. Oboudi, On the third largest eigenvalue of graphs, Linear Algebra Appl. 503 (2016), 164-179, doi:10.1016/j.laa.2016.03.037. [6] M. R. Oboudi, Characterization of graphs with exactly two non-negative eigenvalues, Ars Math. Contemp. 12 (2017), 271-286, doi:10.26493/1855-3974.1077.5b6. [7] M. Petrovic, On graphs with exactly one eigenvalue less than -1, J. Comb. Theory Ser. B 52 (1991), 102-112, doi:10.1016/0095-8956(91)90096-3. [8] M. Petrovic, Graphs with a small number of nonnegative eigenvalues, Graphs Combin. 15 (1999), 221-232, doi:10.1007/s003730050042. [9] J. H. Smith, Symmetry and multiple eigenvalues of graphs, Glasnik Mat. Ser. III 12 (1977), 3-8, https://books.google.com/books?id=I1nZvGaOcscC&pg=PA3. [10] A. Torgasev, On graphs with a fixed number of negative eigenvalues, Discrete Math. 57 (1985), 311-317, doi:10.1016/0012-365x(85)90184-0. [11] G. Yu, L. Feng and H. Qu, Signed graphs with small positive index of inertia, Electron. J. Linear Algebra 31 (2016), 232-243, doi:10.13001/1081-3810.1976. 338 Ars Math. Contemp. 17 (2019) 291-310 Appendix A Five tables Appendix A contains 5 tables, in which there are 706 specific graphs: 4 graphs of order 10, 32 graphs of order 11, 150 graphs of order 12, and 520 graphs of order 13. Table 2: k = 6. n B* 10 Be 1 2 2; 1 2 2) Be 2 2 1; 1 2 2) Be 1 3 3; 1 1 2) , Be 2 3 2; 1 1 2) , Be 3 3 1; 1 1 2) , Be 1 3 3 1 2 1), 11 b6 2 3 2; 1 2 1) , Be 3 3 1; 1 2 1) , Be 2 1 1; 1 3 3) , Be 3 2 1;2 1 2), Be 2 2 2; 2 2 1) , Be 3 1 2; 3 1 1) Be 1 4 4; 1 1 1) , Be 2 4 3; 1 1 1) , Be 3 4 2; 1 1 1) , Be 4 4 1 1 1 1), Be 1 2 4; 1 1 3) , Be 1 4 2; 1 1 3) , Be 2 2 3; 1 1 3) , Be (2 4 1 1 1 3), Be 3 2 2; 1 1 3) , Be 4 2 1; 1 1 3) , Be 1 3 1; 1 2 4) , Be (2 1 2 1 2 4), Be 3 1 1; 1 2 4) , Be 1 4 2; 1 3 1) , Be 2 2 3; 1 3 1) , Be (2 4 1; 1 3 1), 12 Be 3 2 2; 1 3 1) , Be 4 2 1; 1 3 1) , Be 2 1 2; 1 4 2) , Be (3 1 1; 1 4 2), Be 2 3 3; 2 1 1) , Be 4 1 3; 2 1 1) , Be 4 3 1; 2 1 1) , Be (2 3 2; 2 1 2), Be 3 2 2; 2 1 2) , Be 4 1 2; 2 1 2) , Be 2 3 1; 2 1 3) , Be (4 1 1; 2 1 3), Be 3 1 3; 2 2 1) , Be 3 2 2; 2 2 1) , Be 3 3 1; 2 2 1) , Be (3 1 1; 2 2 3), Be 2 3 1; 2 3 1) , Be 3 2 2; 3 1 1) , Be 4 2 1; 3 1 1) , Be (4 1 1; 4 1 1); Be 1 3 6; 1 1 1) , Be 1 6 3; 1 1 1) , Be 2 3 5; 1 1 1) , Be (2 6 2; 1 1 1), Be 3 3 4; 1 1 1) , Be 3 6 1; 1 1 1) , Be 4 3 3; 1 1 1) , Be (5 3 2; 1 1 1), Be 6 3 1; 1 1 1) , Be 1 2 6; 1 1 2) , Be 1 6 2; 1 1 2) , Be (2 2 5; 1 1 2), Be 2 6 1; 1 1 2) , Be 3 2 4; 1 1 2) , Be 4 2 3; 1 1 2) , Be (5 2 2; 1 1 2), Be 6 2 1; 1 1 2) , Be 1 2 3; 1 1 5) , Be 1 3 2; 1 1 5) , Be (2 2 2; 1 1 5), Be 2 2 5; 1 2 1) , Be 2 6 1; 1 2 1) , Be 3 2 4; 1 2 1) , Be (4 2 3; 1 2 1), Be 5 2 2; 1 2 1) , Be 2 3 1; 1 1 5) , Be 3 2 1; 1 1 5) , Be (1 2 6; 1 2 1), Be 1 6 2; 1 2 1) , Be 6 2 1; 1 2 1) , Be 1 5 1; 1 2 3) , Be (2 1 4; 1 2 3), Be 3 1 3; 1 2 3) , Be 4 1 2; 1 2 3) , Be 5 1 1; 1 2 3) , Be (2 1 1; 1 2 6), Be 1 5 1; 1 3 2) , Be 2 1 4; 1 3 2) , Be 3 1 3; 1 3 2) , Be (4 1 2; 1 3 2), Be 5 1 1; 1 3 2) , Be 2 2 2; 1 5 1) , Be 2 3 1; 1 5 1) , Be (3 2 1; 1 5 1), 13 Be 2 1 1; 1 6 2) , Be 2 2 5; 2 1 1) , Be 2 5 2; 2 1 1) , Be (3 1 5; 2 1 1), Be 3 2 4; 2 1 1) , Be 3 3 3; 2 1 1) , Be 3 4 2; 2 1 1) , Be (3 5 1; 2 1 1), Be 4 2 3; 2 1 1) , Be 4 3 2; 2 1 1) , Be 5 2 2; 2 1 1) , Be (6 1 2; 2 1 1), Be 6 2 1; 2 1 1) , Be 2 2 4; 2 1 2) , Be 2 5 1; 2 1 2) , Be (3 1 4; 2 1 2), Be 3 2 3; 2 1 2) , Be 6 1 1; 2 1 2) , Be 2 2 3; 2 1 3) , Be (3 1 3; 2 1 3), Be 2 2 2; 2 1 4) , Be 3 1 2; 2 1 4) , Be 2 2 1; 2 1 5) , Be (3 1 1; 2 1 5), Be 2 5 1; 2 2 1) , Be 4 2 2; 2 2 1) , Be 5 1 2; 2 2 1) , Be (5 2 1; 2 2 1), Be 3 1 3; 2 2 2) , Be 4 1 2; 2 2 2) , Be 5 1 1; 2 2 2) , Be (3 1 2; 2 2 3), Be 4 1 2; 2 3 1) , Be 4 2 1; 2 3 1) , Be 3 1 2; 2 3 2) , Be (4 1 1; 2 3 2), Be 3 1 2; 2 4 1) , Be 3 2 1; 2 4 1) , Be 3 1 1; 2 4 2) , Be (3 3 2; 3 1 1), Be 3 4 1; 3 1 1) , Be 6 1 1; 3 1 1) , Be 3 3 1; 3 2 1) , Be (4 2 1; 3 2 1), Be 5 1 1; 3 2 1) , Be 4 1 1; 3 3 1) F. Duan, Q. Huang and X. Huang: On graphs with exactly two positive eigenvalues 339 Table 3: k = 7. n B* 10 Br 2 2 1 1 1 2 1) Br 2 1 2 2 1 1 1); Br 3 3 1 1 1 1 1) Br 2 1 3 1 1 1 2) Br 2 2 2 1 1 2 1) Br 2 1 2 1 1 2 2) 11 B7 1 2 1 1 1 3 2) Br 2 1 1 1 1 3 2) Br 1 2 3 1 2 1 1) Br 1 2 2 1 2 2 1) Bt 2 1 1 1 2 3 1) Br 2 2 2 2 1 1 1) Br 3 2 1 2 1 1 1) Br 3 1 1 3 1 1 1); B7 1 3 4 1 1 1 1) Br 3 1 4 1 1 1 1) Br 3 3 2 1 1 1 1) Br 1 2 4 1 1 1 2) Bt 2 2 3 1 1 1 2) Br 2 4 1 1 1 1 2) Br 3 2 2 1 1 1 2) Br 4 2 1 1 1 1 2) Br 1 1 4 1 1 1 3) Br 3 1 2 1 1 1 3) Br 1 3 3 1 1 2 1) Br 2 2 3 1 1 2 1) Br 3 1 3 1 1 2 1) Br 1 1 3 1 1 2 3) Br 1 3 1 1 1 2 3) Br 3 1 1 1 1 2 3) 12 Br 1 3 2 1 1 3 1) Br 3 1 2 1 1 3 1) Br 1 2 2 1 1 3 2) Br 1 3 1 1 1 4 1) Br 3 1 1 1 1 4 1) Br 2 1 4 1 2 1 1) Br 2 2 3 1 2 1 1) Br 2 3 2 1 2 1 1) Br 4 2 1 1 2 1 1) Br 2 1 2 1 2 1 3) Br 1 2 2 1 2 2 2) Br 1 3 1 1 2 2 2) Br 2 4 1 1 2 1 1) Br 2 1 2 1 2 2 2) Br 3 1 1 1 2 2 2) Br 2 1 2 1 2 3 1) Br 1 3 2 1 3 1 1) Br 3 1 1 1 3 2 1) Br 2 3 2 2 1 1 1) Br 2 3 1 2 1 1 2) Br 4 1 1 2 1 1 2) Br 3 2 1 2 2 1 1) Br 3 1 1 2 2 1 2) Br 1 2 6 1 1 1 1) Br 1 5 3 1 1 1 1) Br 2 1 6 1 1 1 1) Br 2 2 5 1 1 1 1) Br 2 3 4 1 1 1 1) Br 2 4 3 1 1 1 1) Br 2 5 2 1 1 1 1) Br 2 6 1 1 1 1 1) Br 3 2 4 1 1 1 1) Br 3 3 3 1 1 1 1) Br 4 2 3 1 1 1 1) Br 5 1 3 1 1 1 1) Br 5 2 2 1 1 1 1) Br 6 2 1 1 1 1 1) Br 1 1 6 1 1 1 2) Br 1 4 3 1 1 1 2) Br 2 3 3 1 1 1 2) Br 2 4 2 1 1 1 2) Br 5 1 2 1 1 1 2) Br 1 3 3 1 1 1 3) Br 2 3 2 1 1 1 3) Br 1 2 3 1 1 1 4) Br 2 2 2 1 1 1 4) Br 2 3 1 1 1 1 4) Br 3 2 1 1 1 1 4) Br 1 1 3 1 1 1 5) Br 2 1 2 1 1 1 5) Br 1 2 5 1 1 2 1) Br 1 5 2 1 1 2 1) Br 2 1 5 1 1 2 1) Br 2 2 4 1 1 2 1) Br 5 1 2 1 1 2 1) Br 1 1 5 1 1 2 2) Br 1 2 4 1 1 2 2) Br 1 3 3 1 1 2 2) Br 1 4 2 1 1 2 2) Br 1 5 1 1 1 2 2) Br 5 1 1 1 1 2 2) Br 1 2 3 1 1 2 3) Br 1 3 2 1 1 2 3) Br 1 2 2 1 1 2 4) Br 1 1 2 1 1 2 5) Br 1 2 1 1 1 2 5) Br 2 1 1 1 1 2 5) Br 1 2 4 1 1 3 1) Br 1 5 1 1 1 3 1) Br 2 1 4 1 1 3 1) Br 5 1 1 1 1 3 1) Br 1 1 4 1 1 3 2) Br 1 2 3 1 1 3 2) Br 1 2 3 1 1 4 1) Br 2 1 3 1 1 4 1) 13 Br 1 2 2 1 1 5 1) Br 2 1 2 1 1 5 1) Br 1 2 1 1 1 6 1) Br 2 1 1 1 1 6 1) Br 1 5 2 1 2 1 1) Br 3 2 3 1 2 1 1) Br 4 1 3 1 2 1 1) Br 4 2 2 1 2 1 1) Br 1 4 2 1 2 1 2) Br 2 3 2 1 2 1 2) Br 3 2 2 1 2 1 2) Br 4 1 2 1 2 1 2) Br 1 3 2 1 2 1 3) Br 2 2 2 1 2 1 3) Br 2 3 1 1 2 1 3) Br 3 2 1 1 2 1 3) Br 1 2 2 1 2 1 4) Br 1 5 1 1 2 2 1) Br 2 1 4 1 2 2 1) Br 3 1 3 1 2 2 1) Br 4 1 2 1 2 2 1) Br 5 1 1 1 2 2 1) Br 1 2 2 1 2 2 3) Br 2 1 1 1 2 2 4) Br 2 1 3 1 2 3 1) Br 3 1 3 1 3 1 1) Br 3 2 2 1 3 1 1) Br 2 2 2 1 3 1 2) Br 2 3 1 1 3 1 2) Br 3 1 2 1 3 1 2) Br 3 2 1 1 3 1 2) Br 2 1 3 1 3 2 1) Br 3 1 2 1 3 2 1) Br 2 1 2 1 3 2 2) Br 2 1 1 1 3 2 3) Br 2 1 3 1 4 1 1) Br 2 2 2 1 4 1 1) Br 2 3 1 1 4 1 1) Br 3 2 1 1 4 1 1) Br 2 1 2 1 4 1 2) Br 2 1 2 1 4 2 1) Br 2 1 1 1 4 2 2) Br 2 1 1 1 5 2 1) Br 2 4 2 2 1 1 1) Br 2 5 1 2 1 1 1) Br 6 1 1 2 1 1 1) Br 2 2 1 2 1 1 4) Br 3 1 1 2 1 1 4) Br 2 4 1 2 2 1 1) Br 5 1 1 2 2 1 1) Br 2 3 1 2 2 1 2) Br 2 2 1 2 2 1 3) Br 2 3 1 2 3 1 1) Br 3 2 1 2 3 1 1) Br 4 1 1 2 3 1 1) Br 3 1 1 2 4 1 1). 340 ArsMath. Contemp. 17 (2019) 319-347 Table 4: k = 8. n B* 11 Bg 1 2 1 2 1 1 1 2) , Bg 2 2 1 1 1 1 1 2) , Bg 1 2 2 1 1 1 2 1), Bg 1 2 1 1 1 1 2 2) , Bg 2 1 2 1 1 2 1 1) , Bg 2 1 1 1 1 2 1 2); Bg 1 1 3 3 1 1 1 1) , Bg 1 3 1 3 1 1 1 1) , Bg 1 3 3 1 1 1 1 1), Bg 2 1 3 2 1 1 1 1) , Bg 2 3 1 2 1 1 1 1) , Bg 3 1 3 1 1 1 1 1), Bg 3 3 1 1 1 1 1 1) , Bg 1 1 2 3 1 1 1 2) , Bg 1 2 2 2 1 1 1 2), Bg 1 3 2 1 1 1 1 2) , Bg 2 1 2 2 1 1 1 2) , Bg 2 2 2 1 1 1 1 2), Bg 3 1 2 1 1 1 1 2) , Bg 1 1 1 3 1 1 1 3) , Bg 1 3 1 1 1 1 1 3), Bg 2 1 1 2 1 1 1 3) , Bg 3 1 1 1 1 1 1 3) , Bg 1 1 3 2 1 1 2 1), Bg 1 2 2 2 1 1 2 1) , Bg 1 3 1 2 1 1 2 1) , Bg 2 1 3 1 1 1 2 1), 12 Bg 2 2 2 1 1 1 2 1) , Bg 2 3 1 1 1 1 2 1) , Bg 2 1 1 1 1 1 2 3), Bg 1 1 3 1 1 1 3 1) , Bg 1 3 1 1 1 1 3 1) , Bg 1 2 1 3 1 2 1 1), Bg 1 2 2 2 1 2 1 1) , Bg 1 2 3 1 1 2 1 1) , Bg 2 2 1 2 1 2 1 1), Bg 2 2 2 1 1 2 1 1) , Bg 3 2 1 1 1 2 1 1) , Bg 2 1 1 1 1 2 2 2), Bg 2 1 1 2 1 3 1 1) , Bg 3 1 1 1 1 3 1 1) , Bg 2 1 1 1 1 3 2 1), Bg 2 2 1 2 2 1 1 1) , Bg 3 1 2 1 2 1 1 1) , Bg 2 2 1 1 2 1 1 2), Bg 3 1 1 1 2 1 1 , Bg 2 1 2 1 2 1 2 1) , Bg 2 2 1 1 2 1 2 1), Bg 3 1 1 1 3 1 1 1) Bg 1 1 2 5 1 1 1 1) , Bg 1 1 5 2 1 1 1 1) , Bg 1 2 1 5 1 1 1 1), Bg 1 2 2 4 1 1 1 1) , Bg 1 2 3 3 1 1 1 1) , Bg 1 2 4 2 1 1 1 1), Bg 1 2 5 1 1 1 1 1) , Bg 1 3 2 3 1 1 1 1) , Bg 1 3 3 2 1 1 1 1), Bg 1 4 2 2 1 1 1 1) , Bg 1 5 1 2 1 1 1 1) , Bg 1 5 2 1 1 1 1 1), Bg 2 1 2 4 1 1 1 1) , Bg 2 1 5 1 1 1 1 1) , Bg 2 2 1 4 1 1 1 1), Bg 2 2 2 3 1 1 1 1) , Bg 2 2 3 2 1 1 1 1) , Bg 2 2 4 1 1 1 1 1), Bg 2 3 2 2 1 1 1 1) , Bg 2 3 3 1 1 1 1 1) , Bg 2 4 2 1 1 1 1 1), Bg 2 5 1 1 1 1 1 1) , Bg 3 1 2 3 1 1 1 1) , Bg 3 2 1 3 1 1 1 1), Bg 3 2 2 2 1 1 1 1) , Bg 3 2 3 1 1 1 1 1) , Bg 3 3 2 1 1 1 1 1), Bg 4 1 2 2 1 1 1 1) , Bg 4 2 1 2 1 1 1 1) , Bg 4 2 2 1 1 1 1 1), 1 Q 13 Bg 5 1 2 1 1 1 1 1) , Bg 5 2 1 1 1 1 1 1) , Bg 1 1 1 5 1 1 1 2), Bg 1 1 4 2 1 1 1 2) , Bg 1 2 3 2 1 1 1 2) , Bg 1 2 4 1 1 1 1 2), Bg 1 5 1 1 1 1 1 2) , Bg 2 1 1 4 1 1 1 2) , Bg 2 1 4 1 1 1 1 2), Bg 2 2 3 1 1 1 1 2) , Bg 3 1 1 3 1 1 1 2) , Bg 4 1 1 2 1 1 1 2), Bg 5 1 1 1 1 1 1 2) , Bg 1 1 3 2 1 1 1 3) , Bg 1 2 3 1 1 1 1 3), Bg 2 1 3 1 1 1 1 3) , Bg 1 1 2 2 1 1 1 4) , Bg 1 2 2 1 1 1 1 4), Bg 2 1 2 1 1 1 1 4) , Bg 1 2 1 1 1 1 1 5) , Bg 2 1 1 1 1 1 1 5), Bg 1 1 2 4 1 1 2 1) , Bg 1 1 5 1 1 1 2 1) , Bg 1 2 1 4 1 1 2 1), Bg 1 2 2 3 1 1 2 1) , Bg 1 5 1 1 1 1 2 1) , Bg 2 1 2 3 1 1 2 1), Bg 2 2 1 3 1 1 2 1) , Bg 2 2 2 2 1 1 2 1) , Bg 3 1 2 2 1 1 2 1), Bg 3 2 1 2 1 1 2 1) , Bg 3 2 2 1 1 1 2 1) , Bg 4 1 2 1 1 1 2 1), Bg 4 2 1 1 1 1 2 1) , Bg 1 1 2 3 1 1 2 2) , Bg 1 1 3 2 1 1 2 2), continued on next page F Duan, Q. Huang andX. Huang: On graphs with exactly two positive eigenvalues 341 continued from previous page n B* Bg 1 1 4 1 1 1 2 2) , Bg 2 1 1 3 1 1 2 2) , Bg 2 1 2 2 1 1 2 2), Bg 2 1 3 1 1 1 2 2) , Bg 3 1 1 2 1 1 2 2) , Bg 3 1 2 1 1 1 2 2), Bg 4 1 1 1 1 1 2 2) , Bg 1 1 3 1 1 1 2 3) , Bg 2 1 2 1 1 1 2 3), Bg 1 2 1 3 1 1 3 1) , Bg 2 1 2 2 1 1 3 1) , Bg 2 2 1 2 1 1 3 1), Bg 3 1 2 1 1 1 3 1) , Bg 3 2 1 1 1 1 3 1) , Bg 2 1 1 2 1 1 3 2), Bg 2 1 2 1 1 1 3 2) , Bg 3 1 1 1 1 1 3 2) , Bg 1 2 1 2 1 1 4 1), Bg 2 1 2 1 1 1 4 1) , Bg 2 2 1 1 1 1 4 1) , Bg 2 1 1 1 1 1 4 2), Bg 1 2 1 1 1 1 5 1) , Bg 1 3 2 2 1 2 1 1) , Bg 1 4 1 2 1 2 1 1), Bg 1 4 2 1 1 2 1 1) , Bg 2 1 1 4 1 2 1 1) , Bg 2 3 2 1 1 2 1 1), Bg 2 4 1 1 1 2 1 1) , Bg 3 1 1 3 1 2 1 1) , Bg 4 1 1 2 1 2 1 1), Bg 5 1 1 1 1 2 1 1) , Bg 1 2 3 1 1 2 1 2) , Bg 1 3 2 1 1 2 1 2), Bg 1 4 1 1 1 2 1 2) , Bg 1 2 2 1 1 2 1 3) , Bg 1 3 1 2 1 2 2 1), Bg 1 4 1 1 1 2 2 1) , Bg 2 1 1 3 1 2 2 1) , Bg 2 2 1 2 1 2 2 1), Bg 2 3 1 1 1 2 2 1) , Bg 3 1 1 2 1 2 2 1) , Bg 3 2 1 1 1 2 2 1), 13 Bg 4 1 1 1 1 2 2 1) , Bg 2 1 1 2 1 2 3 1) , Bg 2 2 1 1 1 2 3 1), Bg 3 1 1 1 1 2 3 1) , Bg 2 1 1 1 1 2 3 2) , Bg 2 1 1 1 1 2 4 1), Bg 1 3 1 2 1 3 1 1) , Bg 1 3 2 1 1 3 1 1) , Bg 2 3 1 1 1 3 1 1), Bg 2 2 1 1 1 3 2 1) , Bg 2 2 1 1 1 4 1 1) , Bg 2 1 1 1 1 5 1 1), Bg 2 1 1 4 2 1 1 1) , Bg 2 1 2 3 2 1 1 1) , Bg 2 1 3 2 2 1 1 1), Bg 2 1 4 1 2 1 1 1) , Bg 2 2 2 2 2 1 1 1) , Bg 2 2 3 1 2 1 1 1), Bg 2 3 2 1 2 1 1 1) , Bg 2 4 1 1 2 1 1 1) , Bg 3 1 1 3 2 1 1 1), Bg 3 1 2 2 2 1 1 1) , Bg 3 2 1 2 2 1 1 1) , Bg 3 2 2 1 2 1 1 1), Bg 3 3 1 1 2 1 1 1) , Bg 4 1 1 2 2 1 1 1) , Bg 4 2 1 1 2 1 1 1), Bg 5 1 1 1 2 1 1 1) , Bg 2 1 1 3 2 1 1 2) , Bg 2 1 2 2 2 1 1 2), Bg 2 1 3 1 2 1 1 2) , Bg 2 2 2 1 2 1 1 2) , Bg 3 1 1 2 2 1 1 2), Bg 2 1 2 1 2 1 1 3) , Bg 2 1 2 2 2 1 2 1) , Bg 3 1 1 2 2 1 2 1), Bg 3 2 1 1 2 1 2 1) , Bg 4 1 1 1 2 1 2 1) , Bg 3 1 1 1 2 1 2 2), Bg 3 1 1 1 2 1 3 1) , Bg 2 2 2 1 2 2 1 1) , Bg 2 3 1 1 2 2 1 1), Bg 3 1 1 2 2 2 1 1) , Bg 3 2 1 1 2 2 1 1) , Bg 4 1 1 1 2 2 1 1), Bg 3 1 1 1 2 2 2 1) , Bg 3 1 1 1 2 3 1 1) , Bg 3 2 1 1 3 1 1 1). Table 5: k = 9. B* 11 B9(2 ,1, 2 ,1; 1 ,1,1,1; 1), B9(2 ,1 ,1 ,1; 1,1,1 , 2; 1), B9(1,1, 2 ,1; 1 ,1, 2 ,1; 1), B9(2 ,1,1,1; 2 , 1,1,1; 1); 12 B9(1, 2 , 1, 3; 1 , 1,1,1; 1), B9(1, 2 , 3 , 1; 1,1,1 , 1; 1), B9(2 , 1, 2 , 2; 1 , 1,1,1; 1), B9(2 , 2 , 2 , 1; 1 , 1,1,1; 1), B9(3 , 2 , 1 , 1; 1,1,1 , 1; 1), B9(1,1,1, 3; 1 , 1,1,1; 2), continued on next page n 342 Ars Math. Contemp. 17 (2019) 291-310 continued from previous page n B* Bg 1 1 3 1 1 1 1 1 2) Bg 2 1 1 2 1 1 1 1 2) , Bg 3 1 1 1 1 1 1 1 2), Bg 1 2 1 2 1 1 1 2 1) , Bg 2 1 1 2 1 1 1 2 1) , Bg 1 1 2 1 1 1 1 2 2), 12 Bg 1 2 1 1 1 1 1 3 1) , Bg 1 1 2 2 1 1 2 1 1) , Bg 1 2 1 2 1 1 2 1 1), Bg 2 1 1 1 1 1 2 1 , Bg 1 2 1 1 1 1 2 2 1) , Bg 2 1 1 1 1 1 2 2 1), Bg 1 2 1 1 1 1 3 1 1) , Bg 3 1 1 1 1 2 1 1 1) , Bg 2 1 1 1 1 2 2 1 1), Bg 2 2 1 1 2 1 1 1 1) Bg 1 1 1 5 1 1 1 1 1) , Bg 1 1 2 4 1 1 1 1 1) , Bg 1 1 3 3 1 1 1 1 1), Bg 1 1 4 2 1 1 1 1 1) , Bg 1 1 5 1 1 1 1 1 1) , Bg 1 2 2 3 1 1 1 1 1), Bg 1 2 3 2 1 1 1 1 1) , Bg 1 3 2 2 1 1 1 1 1) , Bg 1 4 1 2 1 1 1 1 1), Bg 1 4 2 1 1 1 1 1 1) , Bg 2 1 1 4 1 1 1 1 1) , Bg 2 1 2 3 1 1 1 1 1), Bg 2 2 1 3 1 1 1 1 1) , Bg 2 2 2 2 1 1 1 1 1) , Bg 2 3 1 2 1 1 1 1 1), Bg 2 3 2 1 1 1 1 1 1) , Bg 2 4 1 1 1 1 1 1 1) , Bg 3 1 1 3 1 1 1 1 1), Bg 3 2 1 2 1 1 1 1 1) , Bg 4 1 1 2 1 1 1 1 1) , Bg 5 1 1 1 1 1 1 1 1), Bg 1 1 2 3 1 1 1 1 2) , Bg 1 1 3 2 1 1 1 1 2) , Bg 1 2 2 2 1 1 1 1 2), Bg 1 3 1 2 1 1 1 1 2) , Bg 1 3 2 1 1 1 1 1 2) , Bg 2 2 1 2 1 1 1 1 2), Bg 2 3 1 1 1 1 1 1 2) , Bg 1 1 2 2 1 1 1 1 3) , Bg 1 2 1 2 1 1 1 1 3), Bg 1 2 2 1 1 1 1 1 3) , Bg 2 2 1 1 1 1 1 1 3) , Bg 1 1 1 2 1 1 1 1 4), Bg 1 1 2 1 1 1 1 1 4) , Bg 2 1 1 1 1 1 1 1 4) , Bg 1 1 1 4 1 1 1 2 1), Bg 1 1 2 3 1 1 1 2 1) , Bg 1 1 3 2 1 1 1 2 1) , Bg 1 1 4 1 1 1 1 2 1), Bg 1 2 2 2 1 1 1 2 1) , Bg 1 2 3 1 1 1 1 2 1) , Bg 1 3 2 1 1 1 1 2 1), Bg 1 4 1 1 1 1 1 2 1) , Bg 2 1 1 3 1 1 1 2 1) , Bg 1 1 1 3 1 1 1 2 2), Bg 1 1 2 2 1 1 1 2 2) , Bg 1 2 1 2 1 1 1 2 2) , Bg 1 2 2 1 1 1 1 2 2), 13 Bg 1 3 1 1 1 1 1 2 2) , Bg 1 1 1 2 1 1 1 2 3) , Bg 1 2 1 1 1 1 1 2 3), Bg 1 1 1 3 1 1 1 3 1) , Bg 1 1 2 2 1 1 1 3 1) , Bg 1 1 3 1 1 1 1 3 1), Bg 1 2 2 1 1 1 1 3 1) , Bg 1 1 2 1 1 1 1 4 1) , Bg 1 1 2 3 1 1 2 1 1), Bg 1 4 1 1 1 1 2 1 1) , Bg 2 1 1 3 1 1 2 1 1) , Bg 2 2 1 2 1 1 2 1 1), Bg 2 3 1 1 1 1 2 1 1) , Bg 3 1 1 2 1 1 2 1 1) , Bg 3 2 1 1 1 1 2 1 1), Bg 4 1 1 1 1 1 2 1 1) , Bg 1 3 1 1 1 1 2 1 2) , Bg 2 2 1 1 1 1 2 1 2), Bg 1 2 1 1 1 1 2 1 3) , Bg 1 1 2 2 1 1 2 2 1) , Bg 2 1 1 2 1 1 2 2 1), Bg 1 2 1 1 1 1 2 2 2) , Bg 2 1 1 2 1 1 3 1 1) , Bg 2 2 1 1 1 1 3 1 1), Bg 3 1 1 1 1 1 3 1 1) , Bg 2 1 1 1 1 1 3 2 1) , Bg 2 1 1 1 1 1 4 1 1), Bg 1 2 2 2 1 2 1 1 1) , Bg 1 3 1 2 1 2 1 1 1) , Bg 1 3 2 1 1 2 1 1 1), Bg 2 1 1 3 1 2 1 1 1) , Bg 2 2 1 2 1 2 1 1 1) , Bg 2 3 1 1 1 2 1 1 1), Bg 3 1 1 2 1 2 1 1 1) , Bg 1 2 1 2 1 2 1 1 2) , Bg 1 2 2 1 1 2 1 1 2), Bg 2 1 1 2 1 2 1 1 2) , Bg 2 2 1 1 1 2 1 1 2) , Bg 2 1 1 1 1 2 1 1 3), Bg 1 2 2 1 1 2 1 2 1) , Bg 1 3 1 1 1 2 1 2 1) , Bg 1 3 1 1 1 2 2 1 1), Bg 2 1 1 2 1 2 2 1 1) , Bg 2 2 1 1 1 2 2 1 1) , Bg 2 1 1 2 1 3 1 1 1), Bg 2 2 1 1 1 3 1 1 1) , Bg 2 1 1 1 1 3 1 1 2) , Bg 2 1 1 1 1 4 1 1 1), Bg 2 3 1 1 2 1 1 1 1) , Bg 2 2 1 1 2 2 1 1 1) F. Duan, Q. Huang and X. Huang: On graphs with exactly two positive eigenvalues 343 Table 6: k = 10. n B* Bio(1 1 2 1 2 1 1 1 1 1) Bio 1 2 1 2 1 1 1 1 1 1) Bio(2 1 2 1 1 1 1 1 1 1) Bio 1 1 1 1 2 1 1 1 1 2) 12 Bio(1 2 1 1 1 1 1 1 1 Bio 2 1 1 1 1 1 1 1 1 2) Bio(1 1 2 1 1 1 1 1 1) Bio 1 2 1 1 1 1 1 1 1) Bio(1 1 2 1 1 1 1 1 1) Bio 2 1 1 1 1 1 1 1 1); Bio(1 1 1 1 4 1 1 1 1 1) Bio 1 1 1 2 3 1 1 1 1 1) Bio(1 1 1 3 2 1 1 1 1 1) Bio 1 1 1 4 1 1 1 1 1 1) Bio(1 1 2 2 2 1 1 1 1 1) Bio 1 1 2 3 1 1 1 1 1 1) Bio(1 1 3 2 1 1 1 1 1 1) Bio 1 1 4 1 1 1 1 1 1 1) Bio(1 2 1 1 3 1 1 1 1 1) Bio 1 2 1 2 2 1 1 1 1 1) Bio(1 2 2 1 2 1 1 1 1 1) Bio 1 2 2 2 1 1 1 1 1 1) Bio(1 2 3 1 1 1 1 1 1 1) Bio 1 3 1 1 2 1 1 1 1 1) Bio(1 3 2 1 1 1 1 1 1 1) Bio 1 4 1 1 1 1 1 1 1 1) Bio(2 1 1 1 3 1 1 1 1 1) Bio 2 1 1 2 2 1 1 1 1 1) Bio(2 1 1 3 1 1 1 1 1 1) Bio 2 1 2 2 1 1 1 1 1 1) Bio(2 2 1 1 2 1 1 1 1 1) Bio 2 2 1 2 1 1 1 1 1 1) Bio(2 2 2 1 1 1 1 1 1 1) Bio 2 3 1 1 1 1 1 1 1 1) Bio(3 1 1 1 2 1 1 1 1 1) Bio 3 1 1 2 1 1 1 1 1 1) Bio(3 2 1 1 1 1 1 1 1 1) Bio 4 1 1 1 1 1 1 1 1 1) Bio(1 1 1 2 2 1 1 1 1 2) Bio 1 1 1 3 1 1 1 1 1 2) Bio(1 1 2 2 1 1 1 1 1 2) Bio 1 1 3 1 1 1 1 1 1 2) 13 Bio(1 2 2 1 1 1 1 1 1 2) Bio 2 1 1 2 1 1 1 1 1 2) Bio(1 1 1 2 1 1 1 1 1 3) Bio 1 1 2 1 1 1 1 1 1 3) Bio(1 1 1 2 2 1 1 1 2 1) Bio 1 1 1 3 1 1 1 1 2 1) Bio(1 1 2 2 1 1 1 1 2 1) Bio 1 2 1 1 2 1 1 1 2 1) Bio(2 1 1 1 2 1 1 1 2 1) Bio 2 1 1 2 1 1 1 1 2 1) Bio(2 2 1 1 1 1 1 1 2 1) Bio 3 1 1 1 1 1 1 1 2 1) Bio(1 1 2 1 1 1 1 1 2 2) Bio 2 1 1 1 1 1 1 1 2 2) Bio(2 1 1 1 1 1 1 1 3 1) Bio 1 2 1 1 2 1 1 2 1 1) Bio(1 2 2 1 1 1 1 2 1 1) Bio 1 3 1 1 1 1 1 2 1 1) Bio(2 1 1 1 2 1 1 2 1 1) Bio 2 1 1 2 1 1 1 2 1 1) Bio(2 2 1 1 1 1 1 2 1 1) Bio 3 1 1 1 1 1 1 2 1 1) Bio(1 2 1 1 1 1 1 2 2 1) Bio 2 1 1 1 1 1 1 2 2 1) Bio(1 2 1 1 1 1 1 3 1 1) Bio 2 1 1 1 1 1 1 3 1 1) Bio(1 2 1 1 2 1 2 1 1 1) Bio 1 2 2 1 1 1 2 1 1 1) Bio(1 3 1 1 1 1 2 1 1 1) Bio 2 2 1 1 1 1 2 1 1 1) Bio(2 1 1 1 1 1 2 2 1 1) Bio 2 1 1 1 2 2 1 1 1 1) Bio(2 1 1 2 1 2 1 1 1 1) Bio 2 1 2 1 1 2 1 1 1 1) Bio(2 2 1 1 1 2 1 1 1 1) Bio 3 1 1 1 1 2 1 1 1 344 Ars Math. Contemp. 17 (2019) 291-310 Appendix B Some theorems and lemmas Theorem B.1 ([6]). 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); (3) B4(a, 1; c, 1); (5) B4(a, 1; x, d); (7) B4(w,x; y, d); (2) B4(a, x; y, 1); (4) B4(a, 1; w,x); (6) B4(w, b; x, 1); (8) B4(x, b; y, d); (9) 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. Lemma B.2. Let G G B4(n), where n > 14. If G G B—(n), then G has an induced subgraph r G $4(14) \ B-(14). Proof. By the proof of Lemma 5.13, it suffices to prove that G contains an induced subgraph G' G B4(n - 1) \ B-(n - 1) for n > 15 in the following. Let G = B4(n1, n2; n3, n4) G B4(n). Then one of Hi = B4(ni - 1, n2; n3, n4), H3 = B4(ni,n2; n3 — 1,n4) and H2 = B4(ni,n2 — 1; n-3,«4), H4 = B4(ni, n2; n3, n — 1) must belong to B4(n — 1). On the contrary, assume that H G B—(n — 1) (i = 1, 2, 3,4). Then H is a graph belonging to (1)-(8) in Theorem B.1 since n > 15. First we consider Hi. If Hi is a graph belonging to (1) of Theorem B.1, then Hi = B4(a, b; 1, d) where ni — 1 = a, n2 = b, n3 = 1 and n4 = d, hence G = B4(a + 1, b; 1, d) G B— (n), a contradiction. Similarly, Hi cannot belong to (2)-(5) of Theorem B.1. Hence Hi is belong to (6) - (8) of Theorem B.1 from which we see that ni — 1 is either w or x. Thus ni < 4 due to w < 3 and x < 2. By the same method, we can verify that n2 < 3 if H2 G B—(n — 1); n3 < 4 if H3 g B—(n — 1) and n4 < 3 if H4 G B— (n — 1). Hence n = ni + • • • + n4 < 14, a contradiction. We are done. □ Theorem B.3 ([6]). Let G = Be(ai, a2, a3; a4, a5, a6 ), where ai,..., 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); (2) B6(a, 1, c; 1, e, 1); (3) Bs(a, 1, c; 1,x,y); (4) B6(a, 1, c; 1,1,f ); (5) B6(a, 1,1; x, e, 1); (6) B6(x,b, 1; y, 1,1); (7) B6(x,y, 1;1,e, 1); (8) B6(x,y, 1; 1,1,f); (9) B6(x, 1, c; y, 1,f ); (10) B6(1, b, x; 1,1,1); (11) B6(1,b, 1;1,e, 1); (12) B6(1,b, 1; 1, x, y); (13) B6(1,x,y;1,1, f ); (14) 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. F. Duan, Q. Huang and X. Huang: On graphs with exactly two positive eigenvalues 345 Lemma B.4. Let G G Be(n), where n > 14. If G G B6 (n), then G has an induced subgraph r G Be (14) \ B- (14). Proof. By the proof of Lemma 5.13, it suffices to prove that G contains an induced subgraph G' G Be(n — 1) \ B-(n — 1) for n > 15 in the following. Let G = Be(n1, n2, n3; n4, n5, ne) G Be(n). Then one of H1 = Be(n1 — 1,n2,n3; n4,n5,ne), H2 = Be(n1,n — 1,n3; n4,n5,ne), H3 = Be(n1,n2,n3 — 1; n4,n5,ne), H4 = Be(n1,n2,n3; n4 — 1,n5,ne), H5 = Be(n1,n2,n3; n4,n5 — 1,ne) and He = Be(n1,n2,n3; n4,n5,ne — 1) must belong to Be(n — 1). On the contrary, assume that H G B- (n — 1) (i = 1, 2,..., 6). Then H is a graph belonging to (1)-(13) in Theorem B.3 since n > 15. Let us consider H3. If H3 is a graph belonging to (1) of Theorem B.3, then H3 = Be (a, x, c; 1,1,1) where n = a, n2 = x, n3 — 1 = c, n4 = n5 = ne = 1, hence G = Be(a, x, c +1; 1,1,1) G B-(n), a contradiction. Similarly, H3 cannot belong to (2) - (4) and (9) of Theorem B.3. If H3 is a graph belonging to (10) of Theorem B.3, then H3 = Be(1, 6, x; 1,1,1), where n1 = 1, n2 = 6, n3 — 1 = x, n4 = n5 = ne = 1. Since x < 2, we have n3 < 3. If n3 < 3 then x + 1 < 2 and G = Be(1, 6, x + 1; 1,1,1) G B-(n), a contradiction. Now assume that n3 = 3. Then H3 = Be(1, 6,2; 1,1,1), and so G = Be(1,6, 3; 1,1,1). By Theorem B.3, G G B-(n), and also its induced subgraph Be(1,6 — 1,3; 1,1,1) G B-(n — 1), a contradiction. Similarly, H3 cannot belong to (13) of Theorem B.3. Hence H3 is belong to (5) - (8) and (11) - (12) of Theorem B.3 from which we see that n3 — 1 < 1. Thus n3 < 2. By the same method, we can verify that n1 < 3 if H1 G B-(n — 1); n2 < 3 if H2 G B-(n — 1); n4 < 2 if H4 G B-(n — 1); n5 < 2 if H5 G B-(n — 1) and ne < 2 if He G B- (n — 1). Hence n = n1 + • • • + ne < 14, a contradiction. We are done. □ Theorem B.5 ([6]). Let G = B7(a1, a2, a3; a4, a5, ae; 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); (4) B7(x,y, 1;1,e, 1; g); (7) B7 (1,6,1;1,e, 1; g); (2) B7(a, 1,1; 1, e, 1; g); (5) B7(x, 1,1; y, 1,1; g); (8) B7 (1,1,c;1,1, f; 1); (3) B7(a, 1,1; 1,1,x;1); (6) B7(1,6,x;1,1,1;g); (9) 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. Lemma B.6. Let G G B7(n), where n > 14. If G G B-(n), then G has an induced subgraph r G B7(14) \ B- (14). Proof. By the proof of Lemma 5.13, it suffices to prove that G contains an induced subgraph G' G B7(n — 1) \ B-(n — 1) for n > 15 in the following. Let G = B7(n1, n2, n3; n4, n5, ne; n7) G B7(n). Then one of H1 = B7(n1 — 1,n2,n3; n4,n5,ne; n7), H2 = B7(n1,n2 — 1,n3; n4,n5,ne; n7), H3 = B7(n1,n2,n3 — 1; n4,n5,n; n7), 346 Ars Math. Contemp. 17 (2019) 291-310 #4 = Br(ni,n2,n3; «.4 - 1,n5,n6; «7), H5 = Br(ni, «2, «3; «4, «5 - 1, «6; nr); #6 = Br(«i, «2, «3; «4, «5, «6 — 1; «r) and #r = Br(«i, «2, «3; «4, «5, «6; «7 — 1) must belong to B7(« — 1). On the contrary, assume that # G B—(« — 1) (i = 1,2,..., 7). Then # is a graph belonging to (1)-(8) in Theorem B.5 since « > 15. Let us consider H1. If H1 is a graph belonging to (1) of Theorem B.5, then H1 = Br (a, 1, x; 1, e, 1; 1) where «1 — 1 = a, «2 = 1, «3 = x, «4 = 1, «5 = e, «6 = «7 = 1, hence G = Br(a + 1,1,x; 1, e, 1; 1) G B—(«), a contradiction. Similarly, H1 cannot belong to (2)-(3) of Theorem B.5. If H1 is a graph belonging to (4) of Theorem B.5, then #1 = Br(x, y, 1; 1, e, 1; g), where «1 — 1 = x, «2 = y, «3 = «4 = 1, «5 = e, «6 = 1 and «r = g. Since x < 2, we have «1 < 3. If «1 < 3 then x + 1 < 2 and G = Br(x + 1, y, 1; 1, e, 1; g) G B—(«), a contradiction. Now assume that «1 = 3. Then H1 = Br(2, y, 1; 1, e, 1; g), and so G = Br(3, y, 1; 1, e, 1; g). Since y G {1, 2}, we have G G {Br(3,1,1; 1, e, 1; g), Br(3, 2,1; 1, e, 1; g)}. However Br(3,1,1; 1, e, 1; g) belongs to (2) of Theorem B.5 which contradicts our assumption. Thus G = Br(3, 2,1; 1, e, 1; g). By Theorem B.5, G G B—(«), and also its induced subgraph Br(3,2,1; 1, e — 1,1; g) or Br(3,2,1; 1, e, 1; g — 1) is not in B—(« — 1), a contradiction. Similarly, H1 cannot belong to (5) of Theorem B.5. Hence H1 belongs to (6)-(8) of Theorem B.5 from which we see that «1 — 1 < 1. Thus «1 < 2. By the same method, we can verify that «2 < 2 if H2 G B—(« — 1); «3 < 2 if H3 g B—(« — 1); «4 < 2 if H4 g B—(« — 1); «5 < 2 if H5 G B—(« — 1), «6 < 2 if H6 g B—(« — 1) and «r < 2 if Hr G B—(« — 1). Hence « = «1 + • • • + «r < 14, a contradiction. We are done. □ Theorem B.7 ([6]). Let G = B8(a1, a2, a3, a4; a5, a6, ar, a8), where a1,..., a8 are some positive integers. Then A2(G) > 0 and A3(G) < 0 if and only if G ¿s isomorphic to one of the following graphs: (1) B8(a, 1,1, d; 1,1,g, 1); (2) B8(1,b, 1,1;1,f, 1,1); (3) 134 specific graphs: 12 graphs of order 10, 42 graphs of order 11, and 80 graphs of order 12, where a, b, d, f, g are some positive integers. Lemma B.8. Let G G B8(«), where « > 14. If G G B—(«), then G has an induced subgraph r G B8(14) \ B—(14). Proof. By the proof of Lemma 5.13, it suffices to prove that G contains an induced subgraph G' g B8(« — 1) \ B—(« — 1) for « > 15 in the following. Let G = B8(«1, «2, «3, «4; «5, «6, «r, «8) G B8(«) and #1 = B8(«1 — 1, «2, «3, «4; «5, «6, «7, «8), #2 = B8(«1,«2 — 1, «3, «4; «5, «6, «7, «8), #3 = B8(«1,«2,«3 — 1, «4; «5, «6, «7, «8), #4 = B8(«1, «2, «3,«4 — 1; «5, «6, «7, «8), #5 = B8(«1, «2, «3,«4; «5 — 1, «6, «7, «8), F. Duan, Q. Huang and X. Huang: On graphs with exactly two positive eigenvalues 347 H6 = Bg(ni,n2,n3,n4; n5,n6 — 1,nr,ng), H7 = B8(ni, n2, n3, n4; n5, n6, n7 — 1, ng) and Hg = Bg(ni, n2, n3, n4; n5, n6, n7, ng — 1). If n3 > 3, then H3 e Bg(n — 1) \ B—(n — 1) by Theorem B.7 as desired. If n3 = 2, then at least one of ni, n2, n4, n5, n6, n7, ng is greater than 1 since n > 15, say n2. Thus H2 g Bg(n — 1) \ B—(n — 1) by Theorem B.7 as desired. Hence let n3 = 1. Similarly, let n5 = ng = 1. Thus one of Hi, H2, H4, H6, H7 must belong to Bg(n — 1). On the contrary, assume that Hi e B— (n — 1) (i = 1,2,4, 6, 7). Then Hi is a graph belonging to (1) - (2) in Theorem B.7 since n > 15. Let us consider Hi. If Hi is a graph belonging to (1) of Theorem B.7, then Hi = Bg(a, 1,1, d; 1,1,g, 1); where ni — 1 = a, n2 = n3 = 1, n4 = d, n5 = n6 = 1, n7 = g and ng = 1, hence G = Bg(a + 1,1,1, d; 1,1, g, 1) e B—(n), a contradiction. Hence Hi belongs to (2) of Theorem B.7 from which we see that ni = 2 due to ni — 1 = 1. By the same method, we can verify that ni = 2 if Hi e B- (n — 1) for i = 2,4, 6, 7. Hence n = ni + • • • + ng < 13, a contradiction. We are done. □ Theorem B.9 ([6]). Let G = Bg(ai, a2, a3, a4; a5, a6, a7, ag; 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. Lemma B.10. Let G e Bg(n), where n > 14. If G £ B—(n), then G has an induced subgraph r e Bg(14) \ B— (14). Proof. By the proof of Lemma 5.13, it suffices to prove that G contains an induced subgraph G' e Bg (n — 1) \ B— (n — 1) for n > 15 in the following. Let G = Bg (ni, n2, n3, n4; n5, n6, n7, ng; ng) e Bg (n). On the contrary, suppose that every induced subgraphs G' e Bg(n — 1) of G belongs to B—(n — 1). If ni > 3, then Hi = Bg(ni — 1, n2, n3, n4; n5, n6, n7, ng; ng) £ B—(n — 1) by Theorem B.9, a contradiction. If ni = 2, then at least one of n2, n3, n4, n5, n6, n7, ng, ng is greater than 1 since n > 15, say n2. Thus H2 = Bg(ni, n2 — 1, n3, n4; n5, n6, n7, ng; ng) £ B—(n — 1) by Theorem B.9, a contradiction. Hence ni = 1. Similarly, n3 = n4 = n5 = n7 = ng = 1. But now G = Bg (1, n2,1,1; 1, n6,1,1; ng) e B—(n) by Theorem B.9, a contradiction. We are done. □