¿^creative , ars mathematica ^commons contemporánea Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 11 (2016) 277-284 The modified Wiener index of some graph operations Ali Reza Ashrafi , Hossein Shabani Department of Pure Mathematics, Faculty of Mathematical Sciences, University ofKashan, Kashan 87317-53153, I. R. Iran Received 20 January 2015, accepted 22 August 2015, published online 16 December 2015 Abstract Graovac and Pisanski [On the Wiener index of a graph, J. Math. Chem. 8 (1991) 53 -62] applied an algebraic approach to generalize the Wiener index by symmetry group of the molecular graph under consideration. In this paper, exact formulas for this graph invariant under some graph operations are presented. Keywords: Modified Wiener index, graph operation, automorphism group. Math. Subj. Class.: 20C15, 20D15 1 Introduction Throughout this paper graph means simple connected graphs. The distance between the vertices u, v of a graph G, dG (u, v) (or d(u, v) for short), is defined as the number of edges in a shortest path connecting them. The sum of all distances between vertices in G is called the Wiener index of G [9]. The first study of this number were made by Harold Wiener in 1947 who realized that there are correlations between this graph invariant and the boiling points of paraffin. We encourage the reader to consult [1, 2] and references therein for information about the effect of this graph invariant on trees and hexagonal systems and [4] for some applications in chemistry. Let G = (V, E) be a simple graph with the vertex set V and the edge set E. Grao-vac and Pisanski [3] in a seminal paper applied the symmetry group of the graph under consideration to generalize the Wiener index. To explain, we assume that r is the automorphism group of G. Then the distance number of an automorphism g, 5(g), is defined as the average of d(u, g(u)) over all vertices u G V(G) and 5(g) = M ^5(g)= rn\V(G)\ ^ ^d(u,g(u)). 1 1 ger 1 11 v M uev(g) ger E-mail addresses: ashrafi@kashanu.ac.ir (Ali Reza Ashrafi), shabani@grad.kashanu.ac.ir (Hossein Shabani) ©® This work is licensed under http://creativecommons.Org/licenses/by/3.0/ 278 Ars Math. Contemp. 11 (2016) 231-245 Define: W (G) = ^Vjff ^ ^ d(u,g(u)). It can be easily shown that uev(G)ger W (G) = 1 |V (G)|2J(G). The authors of [3], in their pioneering work used the name "modified Wiener index" for this graph invariant. Suppose e = uv G E(G) and V(e) = {u, v}. The line graph L(G) is a graph with E(G) as vertex set. Two different vertices of V(L(G)) are adjacent if and only if they have a common vertex in G. The subdivision graph S (G) is the graph obtained by inserting an additional vertex in each edge of G. In other words, each edge of the subdivision graph is replaced by a path of length 2. Suppose G is a graph. Following Yan et al. [8], we set EE(G) = {{e, f} | e, f G E(G) & |V(e) n V(f)| = 1} and EV(G) = {{e,v} | v G V(G) & v G V(e) & e G E(G)}, where V(e) is the set of all end vertices of the edge e. Define the line graph L(G), the subdivision graph S(G), the total graph T(G) and the graphs R(G) and Q(G) as follows: V (L(G)) = E (G), E(L(G)) = EE(G), V(S(G)) = V(G) U E(G), E(S(G)) = EV(G), V(T(G)) = V(G) U E(G), E(T(G)) = E(G) U EV(G) U EE(G), V(R(G)) = V(G) U E(G), E(R(G)) = E(G) U EV(G), V(Q(G)) = V(G) U E(G), E(Q(G)) = EV(G) U EE(G). Throughout this paper we use the standard notations of group theory and graph theory. We refer to [5], for the main properties of product graphs. If G is a connected graph then the diameter d = diam(G) is defied as the length of the largest distance between two vertices in G. Moreover, define D(g, i) = |{{u, g(u)} | u G V(G) & dG(u, g(u)) = i}|; 1 < i < d, and D(r,i) = ^ger D(g, i); 1 < i < d. The number of {u,v} such that d(u, v) = i in W(G) is equal to D(G, i) = D(r, i). Suppose x and y are vertices of G. We write x y to show that x, y are adjacent in G. They are called equivalent, x «G y, if there exists an automorphism a such that a(x) = y. The path, cycle and complete graphs with n vertices are denoted by Pn, Cn and Kn, respectively. The number of edges in a path P is denoted by 1(P) and named the length of P. Our other notations are standard and taken mainly from the standard books on these topics. Main Theorem. Suppose G is a tree of diameter d. Then the following relations hold: 1. W(L(G)) = n-1 W(G) - n-! Hi D(G,i), 2. W(S(G)) = ^n2W(G) + 4-2W(L(G)), 3. W(T(G)) = ^W(G) + 2n-!W(L(G)), A. R. Ashrafi andH. Shabani: The modified Wiener index of some graph operations 279 4. W(Q(G)) = ^W(G), 5. ^(r(g)) > ^ |A„t!R(G))i ^ 2 Proof of the Main Theorem In [6], a character theoretical method for computing the modified Wiener index of graphs is presented and in [8], the authors computed exact formulas for the Wiener index under five graph operations. The aim of this paper is to continue these papers by computing the modified Wiener index of trees under the graph operations L(-), S(-), T(—), Q( —) and R( —). For simplicity of our argument, we assume that r = Aut(G) and W(G) = W(G) then W(G) = Yn=i i.D(G, i). We will start by stating a well-known result in algebraic graph theory. Lemma 2.1. Suppose G is a tree with at least three vertices. Then Aut(L(G)) = Aut(G). Proof. It is an immediate consequence of [7, Corollary 1.4]. □ Theorem 2.2. Let G be a tree with n > 3 vertices and r = Aut(G). Then, W(L(G)) = n—1 w(G) — n^ Ed=i D(G,i). Proof. Suppose e = uv and f = xy are vertices of L(G) such that e ~L(G) f and dL(G)(e, f) = i. So, there are a G Aut(G) and a G Aut(L(G)) such that a(e) = f, a(u) = x and a(v) = y. Choose a shortest path e = e0, e1;..., ei = f in L(G). Set e = eo = uoui, ei = ui«2,. .., ej—i = Uj_iUj, f = ei = MjMj+i, u = uo, v = ui, y = u and x = ui+i. Since G is a tree, u = u0, ui,..., u®, ui+i = x is a shortest path in G connecting u = u0 and x = ui+i. Thus dG(u, x) = i +1. Therefore, for any vertices e and f of L(G) at distance i, we fined two vertices ue and uf of G at distance i + 1, corresponding to e and f, respectively. We now assume that r and s are vertices in G at distance i and r = v0, vi,..., vj—i, vi = s is the unique shortest path connecting r and s. Then the edges v0vi and vi—ivj are at distance i — 1 in L(G). Hence, D(L(G), i) = D(G, i + 1). Therefore, W (L(G)) = £ iD(L(G),i) i = £(i — 1)D(G,i) i = ^ iD(G,i) — ^ D(G,i) ii = W (G) — ^ D(G,i). i Therefore, ^„ffG)?1 W(L(G)) = ^GjW(G) — Ei D(G, i), which completes our argument. □ Lemma 2.3. Suppose G is a tree. Then Aut(S(G)) = Aut(G). Proof. Define $ : Aut(G) —> Aut(S(G)) given by $(a)|V(G) = a and if e = xy G E(G) then $(a)(e) = a(x)a(y) G E(G). Notice that if x y and t,t' are vertices 280 Ars Math. Contemp. 11 (2016) 231-245 in S(G) such that x ~s(g) t ~s(g) y and $(a)(x) ~s(g) t' ~s(g) $(a)(y) then $(a)(t) = $(a)(t'). It can easily be proved that $(a) is a permutation of S(G). We show that ab G E(S(G)) if and only if $(a)(a)$(a)(b) G E(S(G)). Suppose a ~S(G) b and a G G. Then there exists c G G such that a c and a ~S(G) b ~S(G) c. Since a G Aut(G), ac G E(G) if and only if a(a)a(c) G E(G). Hence, there exists l G S(G) such that $(a)(a) ~S(G) l ~S(G) $(a)(c). This implies that $(a)(b) = l. So, ab G E(S(G)) if and only if $(a)(a)$(a)(b) G E(S(G)). Similarly, if a G Aut(S(G)) then a = a|G G Aut(G). Thus, $ is invertible. □ Theorem 2.4. Let G be a tree with n > 3 vertices. Then „—. 4n — 2^ 4n — 2-~- W (S (G)) =-W (G) +-- W (L(G)). n n — 1 Proof. Suppose x, y G V(S(G)) are in the same orbit of Aut(S(G)), dS(G)(x,y) = k and t(x) = y, where t g Aut(S(G)). It is obvious that both of x and y must be together in V(G) or E(G). We first assume that x, y G V(G). Choose the shortest path P1 : x = mo, ui,..., «ft = y in S(G). Obviously, if i is even then uj G G and so k = 2k'. Since G is tree, P2 : x = u0, u2,..., «fc' = y is the unique path connecting x and y in G. Hence, ds(G)(x, y) = 2dG(x,y). Next we assume that x, y G V(G), P3 : x = u0, u1,..., uk = y is a shortest path in S(G). Choose edges ab, cd G E(G) such that a ~S(G) x ~S(G) b and c ~S(G) y ~S(G) d. Suppose that x and y are corresponding vertices of x and y in L(G), respectively. Since S(G) is tree, the path P3 is unique and so the vertices «j, i is even, are corresponding to vertices Uj in L(G). This proves that k is even, say k = 2k'. In a similar way, there exists a path P2 : x = U0, U1,..., Uk' = y in L(G). So, we have again dS(G)(x, y) = 2dL(G)(x,y). Thus, W(S(G)) = 2 E iD(S(G), i) j = 1 E 2iD(G,i) + 2 E 2iD(L(G),i) jj = 2W (G) + 2W(L(G)). Therefore, W(S(G)) = ^^W(G) + W(¿(G)), which completes our proof. □ Lemma 2.5. Suppose G is a tree with at least three vertices. Then Aut(T(G)) = Aut(G). Proof. The map $ : Aut(G) —> Aut(T(G)) defined in a similar way as Lemma 2.3, is an isomorphism. Since if a G Aut(G) then $(a) G Aut(T(G)) and for p G Aut(T(G)) we have a = p|G G Aut(G), as desired. □ Theorem 2.6. With hypothesis of Lemma 2.5, W (T (G)) = ^ W (G) + 2—1W (L(G)). Proof. Suppose x and y are vertices of T(G) such that x (G) y and dT(G) (x, y) = k. If x, y G G then we claim that dG(x, y) = k. To prove, we first notice that G is a subgraph of T(G). Next we assume that P : x = u0, u1,..., uh = y is the unique path in G A. R. Ashrafi andH. Shabani: The modified Wiener index of some graph operations 281 and P' : x = v0, v1,..., vk = y is a shortest path in L(G) connecting x and y. If v1 is a vertex in L(G) and v2 is a vertex in G then by interchanging v0, v1, v2 by v0, v2 we obtain another path P" in L(G) such that 1(P") < Z(P'), a contradiction. Thus, if vi G V(L(G))) then v2, vs,..., vfc_i G V(L(G)) and 1(P) < Z(P'). This shows that v1 G V(L(G)). By continuing this method, one can see that all vertices of P' are in vertices of G. Therefore, P = P'. A similar argument shows that in other case that x and y are corresponding to vertices in L(G), a shortest path in L(G) and T(G) will be the same and so W(T(G)) = W(G) + W(L(G)). Therefore, ^(ffig»)1 W(T(G)) = |y(GôT W (G) + ^(IS1 W (L(G)), which completes the proof. □ Lemma 2.7. Suppose G /s a free with at least three vertices. Then Aut(Q(G)) = Aut(G). Proof. Since Q(G) = L(G) U S(G), Lemmas 2.1, 2.3 and a similar argument as Lemma 2.3 completes the proof. □ Theorem 2.8. With hypothesis of Lemma 2.7, W (Q(G)) = ^ W (G). Proof. Suppose x and y are vertices of Q(G) such that x ~q(g) y. If x, y are corresponding to the vertices of L(G) then dQ(G)(x, y) = dL(G)(x, y). Suppose x, y are vertices of G with distance k and P : x = u0, u^ ..., uk_i, = y is a shortest path in G connecting x and y. If x and y are adjacent in G then distance between them in Q(G) will be 2. In other case, the path P' : x = u0, e1,..., ek, uk = y has length k + 1, where ei — u^i_i u^i, 1 < i < k. In the case that x, y G L(G), the sum of distances is J2i iD(L(G), i) and in the second case the summation will be J2i D(G, i) + ^i D(G, i). Then we have W(Q(G)) = W(G) + 1 D(G, i) + W(L(G)). By applying Theorem 1, the result is obtained. □ Lemma 2.9. Suppose G is a tree with at least three vertices. Then Aut(G) is isomorphic to a proper subgroup of Aut(R(G)). Proof. It is easy to see that the mapping $ : Aut(G) —> Aut(R(G)) given by the same definition as Lemma 2.3 is a one-to-one homomorphism, as desired. Since G is a tree, it has at least a pendant vertex and so R(G) has an automorphism of order 2 in Aut(R(G)) \ $(Aut( G)), proving the lemma. □ Theorem 2.10. With hypothesis of Lemma 2.9, W (R(G)) > ^ ^"RG;)) )| W (G). Proof. Suppose x and y are vertices in R(G). Similar to Theorem 2.8, if x, y G G then dR(G)(x, y) = dG(x, y). In this case, the sum of distances is at least iD(G, i). If x and y are corresponding to vertices w and z of L(G) such that dL(G)(w, z) = k then dR(G)(x, y) = k + 1 and so the sum of distances is at least J2i iD(L(G), i) + J2i D(G, i). Now, we assume that u and v are two pendants in G and in the same orbits under the action of Aut(G) on vertices and e and f are edges such that u is incident to e and f is incident to v. Then e and f are in the same orbits under the action of Aut(G) on edges. Hence, in R(G), all elements of {u, v, e, f} are in the same orbits under the action of Aut(R(G)). Since, corresponding to dG(u, v) in W(G) there exists at least a quantity in the form of dR{G) (u, v) + dR{G) (e, f) + dR{G) (u, f) + dR{G) (v, e) + dR{G) (u, e) + 282 Ars Math. Contemp. 11 (2016) 231-245 dR(G)(v,/) in W(R(G)), by Theorem 1, W(R(G)) > 2W(G), which completes our argument. □ 3 Examples In this section, we apply our results in the pervious section. We denote the cyclic group of order n by Zn and the symmetric group on n symbols by Sym(n). We notice that by Lemmas 2.1-2.7, if G is a tree with at least three vertices then Aut(G) = Aut(L(G)) = Aut(S(G)) = Aut(T (G)) = Aut(Q(G)), and also by Lemma 2.9, Aut(G) < Aut(R(G)). Example 3.1. In this example, W(PJ, W(L(P„)), W(S(Pn)), W(T(P„)), W(Q(P„)) and W(R(Pn)) are calculated where Pn is a path with n vertices. To do this, we assume that V(Pn) = {vj}"=1 and E(Pn) = {ej = VjVj+i}":--!11. We first notice that the automorphism group of Pn is generated by an element a of order 2, where | (vi, v„)(v2, vn_i)... (vn, v n+2) n is even a = < 2 2 I (v1, vn)(v2, vn_i)... (v n-1, v n+1) n is odd. Therefore, Aut(Pn) = Z2. The modified Wiener index of Pn was computed in [3, Example 5.6] as W (Pn)= T n 1SeVen n _n n 1s odd. On the other hand, if n is even, then D(Pn,i) 0 i 1s even 2 i 1s odd, and if n is odd, then D(Pn,i) 2 i 1s even 0 i 1s odd. Therefore, 1 E^(Pn,i) i=1 n n 1s even n — 1 n 1s odd. 3 A. R. Ashrafi andH. Shabani: The modified Wiener index of some graph operations 283 By applying Theorems 2.2-2.10, we obtained the following equations, W (L(Pn)) = W (S (Pn)) = W (T (Pn)) = W (Q(Pn)) = n3-3n2 + 2n 8 (n-1)3 n is even n is odd, 2n3 - 3n2 + n 4 , 2n3 - 3n2 + n 4 , f 2n3-n2 4 n is even 2n3-n4-2n+1 n is odd, n is even 0,e e E(G)}. The function w : E(Gw) ^ W(Gw) is called a weight function of Gw. It is obvious that each weighted graph corresponds to a weight function. The adjacency matrix of Gw is defined as the matrix A(Gw) = (a ij) such that a,ij = w(vivj) if ViVj e E(Gw) and 0 otherwise. The eigenvalues X2,... ,Xn of *Financially supported by the National Natural Science Foundation of China (Grant Nos. 11271149, 11371162) and the Special Fund for Basic Scientific Research of Central Colleges (Grant No. CCNU13F020). E-mail addresses: 750861119@qq.com (Shibing Deng), lscmath@mail.ccnu.edu.cn (Shuchao Li), 928046810@qq.com (Feifei Song) ©® This work is licensed under http://creativecommons.org/licenses/by/3.0/ 286 Ars Math. Contemp. 11 (2016) 231-245 A(Gw) are said to be the eigenvalues of the weighted graph Gw. The inertia of Gw is defined to be the triple In(Gw) = (i+(Gw),i_(Gw),i0(Gw)), where i+(Gw),i_(Gw) and i0(Gw) are the numbers of the positive, negative and zero eigenvalues of A(Gw) including multiplicities, respectively. i+(Gw) and i_(Gw) are called the positive, negative index of inertia (for short, positive, negative index) of Gw, respectively. The number io(Gw) is called the nullity of A(Gw). The nullity and the rank of A(Gw) are also called the nullity and the rank of Gw, and denoted by n(G) and R(G), respectively. Obviously, R(Gw) = i+(Gw) + i_(Gw) and i+(Gw) + i_(Gw) + i0(Gw) = n. For convenience, in the whole context, we let G denote the unweighted graph with respect to the weighted graph Gw; G can be also viewed as a trivial weighted graph in which the weight for each edge is 1. An induced subgraph of Gw is an induced subgraph of G having the same weights with those of Gw. For an induced weighted subgraph Hw of Gw, let Gw - Hw be the subgraph obtained from Gw by deleting all vertices of Hw and all incident edges. A m-cyclic graph is a simple connected graph in which the number of edges equals the number of vertices plus m -1. A weighted path and a weighted cycle of order n are denoted by (Pn )w, (Cn) w, respectively. An isolated vertex is denoted by K1. The study of eigenvalues of graph has been received a lot of attention due to its applications in chemistry (see [2,7,10,15] for details). Gregory et al. [8] studied the subadditivity of the positive, negative indices of inertia and developed certain properties of Hermitian rank which were used to characterize the biclique decomposition number. Gregory et al. [9] investigated the inertia of a partial join of two graphs and established a few relations between the inertia and biclique decompositions of partial joins of graphs. Daugherty [3] characterized the inertia of unicyclic graphs in terms of matching number and obtained a linear-time algorithm for computing it. Yu et al. [19] investigated the minimal positive index of inertia among all unweighted bicyclic graphs of order n with pendants, and characterized the bicyclic graphs with positive index 1 or 2. Very recently, it is interesting to see that Marina et al. [1] studied the inertia set of a signed graph in algebraic approach. The nullity of unweighted graphs has been studied extensively in the literature. Tan and Liu [18] gave the nullity set of unicyclic graphs and characterized the unicyclic graphs with maximum nullity. In addition, Nath and Sarma [17] presented another version of characterization of an acyclic or unicyclic graph to be singular. One of the present authors [13] studied the nullity of graphs with pendant vertices. Fan and Qian [6] characterized the bipartite graphs with the second largest nullity and the regular bipartite graphs with the third largest nullity. Fan and Wang [5] characterized the unicyclic signed graphs of order n with nullity n — 2, n — 3, n — 4, n — 5, respectively. Our paper is motivated directly by [4, 11, 13, 19, 20, 21]. On the one hand, Fan et al. [4] studied the nullity of signed bicyclic graph (which is, in fact, the bicyclic graph with edge weight 1 or —1); Li [13] and Hu [11] studied the nullity of unweighted bicyclic graph. On the other hand, Yu et al. [20] characterized all n-vertex weighted uicyclic graphs with positive index 1 or 2; Tan and Liu [21] studied the nullity of unweighted (k — 1)-cyclic graphs. It is natural and interesting for us to consider the extremal problems on the inertia of weighted (k — 1)-cyclic graphs, which may generalize the corresponding results obtained in [20, 21]. This paper is organized as follows. In Section 2, some preliminaries are presented. In Section 3, we define two classes of weighted (k — 1)-cyclic graph, denoted by ©k and rn k_1. Moreover, we give a method to determine the inertia of a weighted graph in ©fc. S. Deng et al.: On the inertia of weighted (k — l)-cyclic graphs 287 In Section 4, we characterize all weighted (k — 1)-cyclic graphs in r„jfc_i having just one or two positive (resp. negative) eigenvalues. In Section 5, we characterize all weighted (k - 1)-cyclic graphs in r„jfc-1 of rank 2, 3,4, respectively. 2 Preliminaries In this section, we list some lemmas which will be used to prove our main results. Suppose M, N are two Hermitian matrices of order n, if there exists an invertible matrix Q of order n such that QMQT = N, where QT denotes the conjugate transpose of Q, then we say that M is congruent to N, denoted by M = N. Lemma 2.1 ([12]). Let M, N be two Hermitian matrices of order n satisfying M = N. Then i+(M) = i+(N), i_(M) = i_(N) and io(M) = io(N). Let M be a Hermitian matrix. We denote three types of elementary congruence matrix operations (ECMOs) on M as follows: (1) interchanging i-th and j-th rows of M, while interchanging i-th and j-th columns of M; (2) multiplying i-th row of M by a non-zero number k, while multiplying i-th column of M by k; (3) adding i-th row of M multiplied by a non-zero number k to j-th row, while adding i-th column of M multiplied by k to j-th column. By Lemma 2.1, the ECMOs do not change the inertia of a Hermitian matrix. Lemma 2.2 ([14]). Let Hw be an induced subgraph of Gw. Then i+(Hw) < i+(Gw) and i_(Hw) < i_(Gw). Lemma 2.3 ([14]). Let Gw be a weighted graph containing a pendant vertex v with its unique neighbor u. Then i+(Gw) = i+(Gw — u —v) + 1 andi_(Gw) = i_(Gw-u-v) + 1. The following result is a direct consequence of Lemma 2.3. Lemma 2.4. Let (Pn)w be a weighted path of order n. Then In((Pn )w) = (n, §, 0) if n is even and (§_1, §__1, 1) otherwise. By Lemma 2.4, we can show that the adjacency matrix of (P2k)w is invertible. In fact, let {v1, v2,..., v2k } be the vertex set of the weighted path (P2k )w such that vjvi+1 g E ((P2k) w) (i = 1,..., 2k — 1) and wu = w(v2i_iv2i) (i = 1,...,k), wM+i = w(v2iv2i+1) (i = 1,..., k — 1). Then the adjacency matrix of (P2k)w has the following block form: Mn A12 A21 A22 0 0 0 \ 0 A 0 0 ... Afc_1,fc_1 Afc_1,fc \ 0 0 ... Afcjfc_1 Afcjfc / 288 Ars Math. Contemp. 11 (2016) 231-245 Let B = (Bj )kj=1, where "0 J- 1 Wjj 0 B, W,,,+ 1 . . . Wj_1 j wi,i . . . wj,j 0 Wi,i+1 . . . Wj_1,j' 0 - wM . . . Wj,j 00 if i = j; if i < j and j — i = 0 (mod 2); if i < j and j — i = 1 (mod 2); if i > j. Lemma 2.5. Let A and B be the matrices defined as above. Then AB = I. Proof. Let C = (Cj )kj=1 = AB. It suffices to show that C,, = I2 for i = 1,..., k, where I2 is the identity matrix of order 2, and Cj = 0 if i = j. Note that the first (resp. last) row of A contains just two non-zero blocks, whereas each of the rest rows of A contains just three non-zero blocks, the proofs are a little different between them. First we consider the cases that i = 1, k. If 1 < i = j < k, then Cii — / . AisBsi — Ai,i_1Bi_1,i + AiiBii + A s=1 0 wi_1i 0 _0 0 Wj- 1 Wi_1,i_1Wiii + ii,i+1Bi+1,i 0 W, = I2 + I2. 00 ^¿,¿+1 01 \ — 0 0 0 / V — 0 1 Wi. 1 Wii 0 WiiWi+1,i+1 If 1 < i < j < k, we distinguish the following three possible cases to prove our result. Case 1: j — i = 0 (mod 2). In this case, we have C, k ij - / y AisBsj = Ai,i_1Bi_1,j + Ai,iBi,j + Ai,i+1Bi+1,j s =1 n \ /n Wi_i,i...Wj_i,j 0 W,_1,i\ /0 — Wi_i,i_i...W33 0 0 0 0 n \ /O Wi,i+i...Wj_i, 0 Wi \ /0 —-d.—1 + + 00 Wi i...Wj 0 0 0\ /0 Wi+i,i+2...Wj_i,j ' ' Wi+i,i+i .... Wi,i+1 0/ \0 0. 0 0 w 0 w 0 S. Deng et al.: On the inertia of weighted (k — l)-cyclic graphs 289 Case 2: j - i = 1. In this case, we have Cij ^^ AisBSj = Ai,i-iBi-i,j + Ai,iBi,j + Ai,i+\Bi+\,j s=1 0 wj_i,j 0 0 Wi_1,iWi,j \ i_1,i_lWiiWjj \ + 0 0 Wii 0 - Wii 0 00 + 0. 00 Wi,i+1 0 W jj Case 3: j - i = 1 (mod 2) and j - i > 1. In this case, we have Cij ^^ AisBsj = Ai,i_1Bi_1,j + Ai,iBi,j + Ai,i+1Bi+1,j S=1 wi_1,^0 Wi_1,i ...Wj_1j N 00 Wi_1,i_1 . .. Wjj 00 0 W \ /0 - Wi,i+1 . . . Wj_1,j-+ I WiM Wi,i . . . Wjj 'Wii V\0 , 0 j + 0. 0 0\ /0 Wi,i+1 0J I 0 Wi+1,i+2 . . . Wj_1j Wi+1,i+1 . . .Wjj 0 For i =1 or i = k, all the proofs above are still correct if we set the corresponding blocks to be 0 whenever one of its subscripts equals 0 or k + 1, such as A10 = Ak,k+1 = 0. If 1 < j < i < k, the proof is similar to the case 1 < i < j < k. We omit the procedure here. □ 3 The inertia of weighted graphs in 6k For m > 1, a m-cyclic graph is a simple connected graph in which the number of edges equals the number of vertices plus m - 1. Let Pri be a path of order ri (ri > 2) and {Pri |1 < i < k} be the set of k (k > 2) vertex-disjoint paths, where there exists at most one path of order 2. Identify the k initial vertices as u0 and terminal vertices as v0, respectively. The resultant graph, denoted by 0(r1, r2,..., rk), is called a ©-graph. Denote by ©k the set of all n-vertex weighted ©-graphs having form 0(r1, r2,..., rk)w. Note that any weighted ©-graph is also a weighted (k - 1)-cyclic graph. Denote the set of all weighted (k - 1)-cyclic graphs of order n, which contain a weighted ©-graph as an induced subgraph, by rn,k_1. In this section, we'll give a method to determine the inertia of weighted graphs in ©k. W ij 0 W 0 1 0 W 1 0 290 Ars Math. Contemp. 11 (2016) 231-245 Let Gw := <){r\. /•■_,...., rk)w be a graph of order n. Let n, be the number of r/s which satisfy rj — 2 = i (mod 4), 1 < j < k, 0 < i < 3 and set t := n\ + n3 and q := t + n2. It is easy to see that Gw e we arrange the structure of Gw as follows: First come the paths Pri,..., Pr with /'1 s' r-> s' ... s' r„ and r, = :! (mod 4), i = 1, 2,... ,ni; next PTni+1, • • • ,-Pn withr„1 + i < r„1+2 < ... < rt and r» = 1 (mod 4), i = m + 1, ni + 2,..., t; then Prt+l ,...,PTq with rt+i < ri+2 < ... < rq and Ti = 2 (mod 4), i = t + 1, t + 2,..., q; finally Pr(!+1 ,...,PTk with rg+1 < rg+2 < ... < rfc and ri = 0 (mod 4), i = q + l,q + 2,... ,k. Let ui be the neighbor of vq in the odd path Pri, i = 1,2,... ,t. Let Pl = u\u\ ... u\Si (1 < i < k) be the path in Pri (1 < i < k) obtained by deleting u0, v0 and a, if r, is odd; see Fig. 1. Further on we will label the weight for each edge of Gw according to the following possible cases. Case 1: min{ri, r2,..., /7. j = 4. In this case, partition the vertex set of Gw as follows: {uo},V(P1),...,V(Pk),{u1,...,ut},{v0}. Let aj = w(u0u\) (i = 1 ,...,k), hi = w{uiu\Si) (i = 1 ,■■■ ,t), bj = w{v0u32s.) (j = t + 1,. .. ,k), di = w(v0Ui) (i = l,...,t), wjj = w(ut2j_1ut2j) (i = 1 ,...,k;j = l,...,\\V{Pi)\) and w),j+i = w(u\ju ij+1) (i = 1 ,...,k;j = 1,..., ^¡ViP^l - 1). Then the adjacency matrix of Gw has the following form: 0 T T ax ... at T T a-t+i ■ ■ ■ ak 0 0 \ T T at Ai At 0 Pl I3t 0 T at+i T ak 0 At+i Ak 0 0l+i Pl 0 Pi Pi 0 0 di dt 0 0 PT+l ■ ■ ■ 0k di . . . dt 0 / where af = (ai; 0,..., 0) and (if = (0,..., 0, h). We apply theECMOs on A(GW): using -ajA^1 to multiply the (i + l)-throw, then adding it to the first row, we can cancel aj{i = I,..., k) in the first row. Similarly, S. Deng et al.: On the inertia of weighted (k — l)-cyclic graphs 291 using —pfA-1 to multiply the (i + 1)-th row, then adding it to (k + i + 1)-th row if i < t, and adding it to the last row if t +1 < i < k, we can cancel pT (i = 1,..., k). After that, column operations are applied so that each ai and pi are reduced to 0s. By Lemma 2.5, —af A-1 a = — PfA-1 Pi = 0 and ci = —af A-1Pi = — pfA-1ai, where ci = «biwi2w23 .. ,-1, wl 1w22... aibiw12w23 . . . wl 1w22 . . i,Si if |Ai| = 2si = 2 (mod 4); if |Ai| = 2si = 0 (mod 4). So A(Gw) can be reduced to the following matrix: B = 0 0 c1 Ct \ s A1 At A t+1 Ak C1 ... Ct ¿1 ... dt 0 0 d1 dt 0 0 0 0 0 0 0 0 0 0 0 0 0 where s = J2 i i=t+1 ' Define D 0 s C1 ... ct s 0 d1 . . . dt c1 d1 0 ct dt / (3.1) After interchanging rows and columns, we get the equivalent matrix of B: D A1 Ai / (3.2) 292 Ars Math. Contemp. 11 (2016) 231-245 It follows that ) = i+(D) + £ i+(Afc) = i+(D) + - £ |Ai| j=i j=i = i+(D) + - (£(r - 3)+ £ (r - 2) U' = ! j=t+1 = i+(D) + - (£(ri - 2) - t VJ=1 = i+(D) + -(n - 2 - t). Similarly, «-(G^) = i-(D) + ±(n - 2 - t),«o(Gw) = t + 2 - R(D). Case 2.: min{r1, r2,..., rk} = 3. We suppose, without loss of generality, that the first t paths Pi = u0uiv0 (i = 1,..., t) are of length 3. Partition the vertex of Gw as follows: {uo}, V(P£+1),..., V(Pk), {ui,..., u£},{u£+1, ..., ut}, {vo}. Then we label the weight for each edge of Gw as follows: ci = w(u0ui) (i = 1,..., t), di = w(voui) (i = 1, .. ., t), ai = w(uou1) (i = t + 1, .. ., k), bi = w(u,iu\s ) (i = t + 1,... ,t), bj = w(vou2s.) (j = t + 1,..., k) and wj = w(u2j-1u2j) (i = t + 1,..., k; j = 1,..., 1 |^(Pi)|), wjj+1 = w(u2j u2j+1) (i = t +1,...,k; j = 1,..., 1 |V(Pi)| - 1). Then the adjacency matrix of Gw has the following form: A(Gw) ( 0 *£+1 *t+1 C1 C£ 0 T T «1+1 . .. at A £+1 At ft TT at+1...at A t+1 Ak C1 . . . C£ d1 . . . d£ A d£+1 . . . dt 0 ^T+1 ^T d£+1 0 0 0 0 0 a t 0 0 0 a k d 1 0 0 0 0 d 0 0 0 0 d t 0 After applying ECMOs on the above matrix, we can get a diagonal matrix similar to (3.2), hence the result is still holds in this case. S. Deng et al.: On the inertia of weighted (k — l)-cyclic graphs 293 Case 3: minjri, r2,..., rk} = 2. Let ci+1 = w(wovo), then we only need to delete the row and the column corresponding to Ai+1 and replace the upper right and the lower left elements of A(Gw) with ct+1, and the rest arguments are similar. Theorem 3.1. Let Gw = 0(r1, r2,..., rk )w be a weighted graph of order n. Denote by U the number of rj's which satisfy rj — 2 = i (mod 4) (1 < j < k, 0 < i < 3) and let t = n1 + n3. The matrix D is defined as in (3.1). Then (i+(Gw ),i-(Gw ),io(Gw)) = ^i+(D) + 1(n — 2 — t),i_(D) + 1(n — 2 — t),t + 2 — R(D)^ . (3.3) In particular, (i) if n1 + n3 = 0, s = 0, then (i+(Gw), i_(Gw), i0(Gw)) = n — 1, ^n — 1, 2). (ii) if n1 + n3 = 0, s = 0, then (i+(Gw),i_(Gw),io(Gw)) = n, 2n,0). (iii) if n1n3 > 0, then (i+(Gw),i_(Gw),io(Gw)) = Q(n — t) + 1, 2(n — t) + 1,t — 2^ . (iv) if n1 + n3 = 0, n1n3 = 0 and dict = cidt holds for some i € {1, 2,..., t — 1}, then ' 1 , , _ 1 (i+(Gw),i_(Gw),io(Gw)) = (j(n — t) + 1, 2(n — t) + 1,t — 2J . (v) if n1 + n3 = 0, n1n3 = 0, s > 0 and dict = cidt holds for i = 1, 2,..., t, then (i+(Gw ),i_(Gw),io(Gw)) = (1 (n — t), 2(n — t) + 1,t — 1) , if m > 0,n3 = 0; (2(n — t) + 1, 1 (n — t), t — 1) , if n3 > 0, n1 = 0. (vi) if n1 + n3 = 0, n1n3 = 0, s = 0 and dict = cidt holds for i = 1, 2,..., t, then (i+(Gw),i_(Gw),io(Gw)) = Q(n — t), 2(n — t),^ . (vii) if n1 + n3 = 0, n1n3 = 0, s < 0 and dict = cidt holds for i = 1, 2,..., t, then (i+(G ), i_(G ),io(Gw)) (1 (n — t) + 1, 1 (n — t), t — 1) , if n1 > 0, n3 = 0; (1 (n — t), 2(n — t) + 1,t — 1) , if n3 > 0,n1 = 0. 294 Ars Math. Contemp. 11 (2016) 231-245 Proof. By the discussion of Cases 1-3 above, the first part of Theorem 3.1 follows directly. Furthermore, by the first part of Theorem 3.1 it is routine to check that (i) and (ii) hold. (iii) If n^3 > 0, applying ECMOs on D yields the following matrix: /0 s 0 ... ct \ 0 s 0 ... ct s 0 «1 ... dt 0 «1 0 ct dt / where a = d - d* Q. Noted that ci > 0 and ct < 0, hence a1 =0, which implies that i+(D) = ¿-(D) = 2 and R(D) = 4. By (3.3), we have (i+ (Gw),i_(Gw),i0(Gw)) = (2 (n -t), 2 (n - t) +1, t - 1). By a similar discussion as in the proof of (iii), we can show that (iv) also holds. (v) In this case, applying ECMOs to D yields the following matrix: ( 0 s s 0 00 00 \ 2 ctdt j s / If n1 > 0, n3 = 0, then -< 0 for ct > 0, hence i+(D) = 1,i-(D) = 2 and R(D) = 3. In view of (3.3), we have (S«+(Gw),i-(Gw),io(Gw)) = (2(n-t), 2 (n-t) + 1,t -2). If n1 = 0,n3 > 0, then -2c(dt > 0 for ct < 0, hence i+(D) = 2,i-(D) = 1 and R(D) = 3. In view of (3.3), we have((i+(Gw), i-(Gw), io(Gw)) = (1 (n - t) + 1,1 (n - t),t - 2). By a similar discussion, we can also show that (vi) and (vii) hold. This completes the proof. □ 0 0 0 0 4 Characterization of weighted graphs in rn,k-1 with small positive (negative) indices In this section, we'll characterize all the weighted graphs in rn fc-1 with 1 or 2 positive (negative) indices. Theorem 4.1. Let Gw G rn,k-1. Then i+(Gw) = 1 if and only if Gw is one of the following graphs: the weighted graph 0(3,..., 3)w with ckd = cjdfc, i = 1,2,..., k; the weighted graph 0(3,..., 3, 2)w with ck-1dj = cdk-1, i =1, 2,..., k - 1. Proof. The sufficiency follows directly from Theorem 3.1. Here we only show the necessity in what follows. Note that if Gw G r„ifc-1 with pendants, then assume, without loss of generality, that x is a pendent vertex of Gw. Let N(x) = {y} and G'w = Gw - {x, y}. It's routine to check that Gw is not a weighted empty graph, which contradicts to the fact that i+(Gw) = 1. Now we consider the case that Gw contains no pedants and i+(Gw) = 1. In view of Theorem 3.1, • t = 0 and s = 0. In this subcase, we have i+(Gw) = 2n - 1 = 1 holds for n = 4. Then Gw = 0(2,4)w with weighted condition c1w21 = a2b2 for s = 0. Note that the S. Deng et al.: On the inertia of weighted (k — l)-cyclic graphs 295 weighted graph 0(2,4)w with c1w21 = a2b2 is, in fact, the weighted graph 0(3,3)w with c2dj = Cjd2, i =1, 2. • t = 0 and s = 0. In this subcase, we have n > 4, hence i+(Gw) = n > 2. • n1 > 0 and n3 > 0. In this subcase, we have n — t > 4, hence i+ (Gw) = 2 (n — t) + 1 > 3. • Just one of n1 and n3 is 0, and djct = cjdt holds for some i G {1,2,... ,t}. In this subcase, we have n — t > 2 if n3 = 0 and n — t > 6 if n1 =0. Hence i+(Gw) = 2 (n — t) + 1 > 2. • Just one of n1 and n3 is 0, s = 0 and djct = cjdt holds for i = 1, 2,..., t. In this subcase, we have n — t > 2 if n3 = 0 and n — t > 6 if n1 =0. Hence, i+(Gw) = 1 if and only if n — t = 2 and n3 = 0. This gives that Gw must be the weighted graph 0(3,..., 3)w with ckdj = cjdk holding for i = 1, 2,..., k. • Just one of n1 and n3 is 0, s > 0 and djct = cjdt holds for i = 1, 2,..., t. In this subcase, we have n — t > 2 if n3 = 0 and n — t > 4 if n1 =0. Hence, i+ (Gw) = 1 if and only if n — t = 2 and n3 = 0. This gives that Gw must be the weighted graph 0(3,..., 3, 2)w with ck_1di = cidk_1 holding for i = 1, 2,..., k — 1. • Just one of n1 and n3 is 0, s < 0 and djct = cjdt holds for i = 1, 2,..., t. In this subcase, we have n — t > 4 if n3 = 0 and n — t > 6 if n1 =0, which implies that i+(Gw) = 1 (n —1) + 1 > 1. Hence, we conclude that i+(Gw) = 1 if and only if Gw is the weighted graph 0(3,..., 3)w with ckdj = cjdk holding for i = 1, 2,..., k or, Gw is the weighted graph 0(3,..., 3, 2)w with ck_1dj = cjdk_1 holding for i =1, 2,..., k — 1. □ Theorem 4.2. Lei Gw G ©k. Then i+(Gw) = 2 if and only if Gw is one of the following graphs: the weighted graph 0(2,4,4)w with c1 = a22r2 + aa3ra; the weighted wii wii graph 0(3,..., 3)w with djct = cjdk for some i G {1,2,..., k}; the weighted graph 0(3,..., 3, 2)w with djck_1 = cjdk_1 for some i G {1, 2,..., k — 1}; the weighted graph 0(3,..., 3, 2,4)w with ck_2dj = cjdk_2, i = 1, 2,..., k — 2 and ck_1wk1 > akbk. Proof. The sufficiency is clear by Theorem 3.1. To prove the necessity, suppose that Gw G ©k with i+(Gw) = 2. We proceed by distinguishing the following subcases. • t = 0 and s = 0. In this subcase, i+(Gw) = 1n — 1 = 2, hence we have n = 6. Then Gw maybe 0(2,4,4)w, 0(2,6)w or 0(4,4)w. If Gw is the weighted graph 0(2,4,4)w, then c1w21 = a2b2 for s = 0, whereas the s of 0(2,6)w is positive and the s of 0(4,4)w is negative, which contradicts the assumption that s = 0. • t = 0 and s = 0. In this subcase, i+(Gw) = 1n = 2, hence we have n = 4. Then Gw is just the weighted graph 0(2,4)w with c1w21 = a2b2. In fact, the weighted graph 0(2,4)w with c1w21 = a2b2 is also the weighted graph 0(3,3)w with ckdj = cjdk for i = 1, 2. • n1 > 0, n3 > 0. In this subcase, we have n—t > 4. Hence, i+(Gw) = 2(n—1) + 1 > 3, which implies that there does not exist such weighted graph Gw. • Just one of n1 and n3 is 0, and djct = cjdt holds for some i G {1, 2,..., t}. In this subcase, by a similar discussion in the proof of Theorem 4.1, i+(Gw) = 2 holds only if 296 Ars Math. Contemp. 11 (2016) 231-245 n3 = 0 in which i+(GW) = 1 (n - t) + 1. So we have n - t = 2. Hence Gw must be the weighted graph 0(3,..., 3)w with djct = cjdfc for some i € {1, 2,..., k}, or the weighted graph 0(3,..., 3, 2)w with djCfc-1 = c®dk-1 for some i € {1,2,..., k - 1}. • Just one of n1 and n3 is 0, s = 0 and djct = c®dt holds for i = 1, 2,..., t. In this subcase, i+(GW) = 2 (n - t). Hence, by a similar discussion in the proof of Theorem 4.1, i+(GW) =2 if and only if n - t = 4 and n3 = 0, which implies that Gw must be the weighted graph 0(3,..., 2,4)w with cfc-2dj = Cjdfc-2 i = 1,2,..., k - 2 and Cfc-iwfi = afc6fc. • Just one of n1 and n3 is 0, s > 0 and djct = c®dt holds for i € {1, 2,..., t}. In this subcase, i+(GW) = 1 (n - t). Hence, by a similar discussion in the proof of Theorem 4.1, i+(GW) = 2 if and only if n - t = 4 and n3 = 0, which implies that Gw must be the weighted graph 0(3,..., 2,4)w with cfc-2dj = Cjdfc-2 for i € {1,2,..., k - 2} and cfc-iwfi > afc6fc. • Just one of n1 and n3 is 0, s < 0 and djct = c®dt holds for i € {1,2,..., t}. In this subcase, by a similar discussion in the proof of Theorem 4.1, we have n -1 > 4 if n3 = 0 and n - t > 6 if n1 =0. Hence, we have i+(GW) = 2(n -1) + 1 > 2. This completes the proof. □ Theorem 4.3. Let Gw € rn,k with pedants. Then i+(GW) = 2 if and only if G = G1, G2,..., G9 or G10 (see Fig. 2) and the corresponding weighted conditions are as shown in Table 1, where the empty cell means that there is no correlation between the inertia index of Gw and its weight set. Table 1: The weighted condition for each Gw g r(n, k) with pedants satisfying i+(Gw) = 2. weighted graph Gw weighted conditions of Gw Gl g^ G^ G4 Gw, Gw, Gw, Gw GW Cfc-idj = Cjdfc-i (1 < i < k - 1) Gw, Gw cfcdj = Cjdfc (1 < i < k) GW cfc-idj = Cjdfc-i (2 < i < k - 1) G9 G10 Gw, Gw ck-idj = Cjdfc-i (1 < i < k - 1) Proof. It is routine to check that i+(GW) = 2 holds for i = 1,2,..., 10. To show the converse, suppose that i+(GW) = 2. Since Gw has at least one pendent x, let N(x) = {y} and Gw = Gw — { x, y} = + pK1, where is obtained from GW by deleting all the isolated vertices. By Lemma 2.3 we have 2 = i+(GW) = i+(GW) + 1 = i+(HW) + 1. Hence, i+(HW) = 1. Recall that Gw contains a ©-graph as an induced subgraph, we conclude that is either isomorphic to a weighted star or one of the weighted graphs described in Theorem 4.1. If is a star, then G must be isomorphic to G®, i = 1,2, 3,4. If is the weighted graph 0(3,..., 3)w, then G must be isomorphic to G®, i = 5, 6, 7 and if is the weighted graph 0(3,..., 3, 2)w, then G must be isomorphic to G®, i = 8, 9,10. S. Deng et al.: On the inertia of weighted (k — l)-cyclic graphs 297 Figure 2: Graphs G\ G2,..., G9 and G10. If G is isomorphic to G5, without loss of generality, assume that x is adjacent to the internal vertex of the A-tli path P3 (see Fig. 2), so the weighted condition is that a , tl, = Cj(ifc_i holds for i = 1.2..... /;• — I. Iff/ is isomorphic to G6 or G7, the weighted condition is cj~di = Cidk for i = 1, 2,..., k. If G is isomorphic to G8, without loss of generality, assume that x is adjacent to the internal vertex of the first path P3 (see Fig. 2), so the weighted condition is that a , d, = <'/dj. holds for i = 2, 3,..., k — 1. If G is isomorphic to G9 or G10, the weighted condition is cu-idi = Cidk-i for i = 1,2,..., k — 1. □ Similarly, we can have the following theorems: Theorem 4.4. Let Gw G rnifc_i. Then i-(Gw) = 1 if and only if Gw is the weighted 0(3,..., 3)w with the weighted condition that ckdi = Cidk holds for i = 1, 2,..., k. Theorem 4.5. Let Gw G Then i-(Gw) = 2 if and only if Gw is one of the following graphs: the weighted graph 0(3,... ,3,2)w with an arbitrary weighted condition; the weighted graph 0(2,4,4)™ with weighted condition c\ = -^r1 + ^r3-; the wn wn weighted graph 0(3,... ,3)w with the weighted condition that dick ^ Cidk holds for some i G {1,2,... ,k}; the weighted graph 0(3,... ,3,2,4)w with the weighted condition that cu-idi = Cidk-2 holds for i = 1,2,... ,k — 2 and cnwfj < a>kbk', the weighted graph 0(3,... ,3, A)w with the weighted condition that Ck-idi = Cidk-i holds for i = 1, 2,..., k — 1. Theorem 4.6. Let Gw G with pedants. Then i-(Gw) = 2 if and only if Gw is one of the following graphs: the weighted graph Gw has G1 (resp. G2, G3, GA) as its unweighted graph and its weight set is arbitrary; the weighted graph Gw has G5 as its unweighted graph satisfying the weighted condition Ck-idi = cjc4_i, i = 1,2,..., k — 1; the weighted graph Gw has G6 (resp. G7) as its unweighted graph satisfying the weighted condition Ckdi = Cidk, i = 1,2,... ,k. 5 Weighted graphs in I '„./,_ i with rank 2, 3, or 4 In this section, we characterize all the weighted (k — 1)-cyclic graphs in I',, /, with rank 2, 3, 4, respectively. 298 Ars Math. Contemp. 11 (2016) 231-245 Theorem 5.1. Let Gw g rn,k_1. Then R(Gw) = 2 if and only if Gw is the weighted 0(3,..., 3)w with the weighted condition ck d = cjdk holding for i = 1, 2,..., k. Proof. Let Gw g rn,k_1, i+(Gw) > 1 and i_(Gw) > 1 since it contains P2 as an induced subgraph. Then r(Gw) = 2 if and only if i+(Gw) — i_(Gw) — 1. By Theorems 4.1—4.6, we know Gw must be the weighted 0(3,..., 3)w satisfying the weighted condition that ckdj = cjdk for any 1 ^ i ^ k. □ Theorem 5.2. Let Gw g rn,k_1. Then R(Gw) = 3 if and only if Gw is the weighted 0(3,..., 3,2)w with the weighted condition that ck_1di = cidk_1 holds for i = 1, 2,..., k - 1. Proof. Let Gw g rn,k_1, i+(Gw) > 1 and i_(Gw) > 1 since it contains P2w as an induced subgraph. Then R(Gw) = 3 if and only if i+(Gw) = 1,i_(Gw) = 2 or i+(Gw) = 2,i_(Gw) = 1. Note that either i+(Gw) or i_(Gw) equals 1, hence by Theorems 4.1 and 4.4 we know Gw must be the weighted graph 0(3,..., 3)w satisfying cfcdj = c.jdfc for 1 < i < k. □ Theorem 5.3. Let Gw G ©k. Then R(Gw ) = 4 if and only if Gw is one of the following graphs: the weighted graph 0(2,4,4)w with weighted condition ci = ^^ + aa3ra; the weighted graph 0(3,..., 3) with the weighted condition that djcfc = Cjdfc holds for some i G {1, 2,..., k}; the weighted graph 0(3,..., 3, 2)w with the weighted condition that djck-i = cjdk-i holds for some i G {1,2,..., k — 1}; the weighted graph 0(3,..., 3,2,4)w with the weighted condition that ck_2dj = cjdk_2 holds for i = 1, 2,..., k — 2 and ck_iwk1 = ak. Proof. Let Gw be a weighted (k — 1)-cyclic graph, it is routine to check that i+(Gw) > 1 and i_(Gw) > 1. Then R(Gw) = 4 if and only if (i+(Gw),i_(Gw)) = (1,3) or (i+(Gw ),i_ (Gw )) = (3,1) or (i+(Gw ),i_ (Gw )) = (2,2). If one of i+(GJ and i_(Gw ) equals 1, by Theorems 4.1 and 4.4, Gw must be the weighted graph 0(3,..., 3)w or 0(3,..., 3,2)w. In this case, by Theorems 4.1, 4.2, 4.4 and 4.5 we know the rank of such graph Gw is no less than 3. Hence, it should only consider that (i+(Gw ), i_(Gw )) = (2, 2). In this case, based on Theorems 4.2 and 4.5, (i+(Gw ), i_(Gw )) = (2,2) if and only if Gw is one of the weighted graphs characterized in the above result. □ Similarly, we can have the following theorem: Theorem 5.4. Let Gw G rn,k_1 with pedants. Then R(Gw ) = 4 if and only if G = G1,..., G7, what's more, the weighted condition of Gw (resp. Gw, Gw, Gw ) is arbitrary; Gw satisfies the weighted condition that ck_1di = cidk_1 holds for i = 1, 2,..., k — 1; while Gw (resp. Gw) satisfies the weighted condition that ckdj = cjdk holds for i = 1, 2,..., k. References [1] M. Arav, F.J. Hall, Z.S. Li, H. van der Holst, The inertia set of a signed graph, Linear Algebra Appl. 439 (5) (2013) 1506-1529. [2] L. Collatz, U. Sinogowitz, Spektren endlicher grapfen, Abh. Math. Sem. Univ. Hamburg 21 (1957) 63-77. S. Deng et al.: On the inertia of weighted (k — l)-cyclic graphs 299 [3] S. Daugherty, The inertia of unicyclic graphs and the implications for closed-shells, Linear Algebra Appl. 429 (2008) 849-858. [4] Y.Z. Fan, W. Du, C. Dong, The nullity of bicyclic signed graphs, arXiv:1207.6765 [math.CO] [5] Y.Z. Fan, Y. Wang, A note on the nullity of unicyclic signed graphs, Linear Algebra Appl. 397 (2005) 245-251. [6] Y.Z. Fan, K.S. Qian, On the nullity of bipartite graphs, Linear Algebra Appl. 430 (2009) 29432949. [7] P.W. Fowler, D.E. Manolopoulos, An Atlas of Fullerenes, Clarendon Press, Oxford, 1995. [8] D.A. Gregory, V.L. Watts, B.L. Shader, Biclique decompositions and Hermitian rank, Linear Algebra Appl. 292 (1999) 267-280. [9] D.A. Gregory, B. Heyink, K.N. Vander Meulen, Inertia and biclique decompositions of joins of graphs, J. Comb. Theory Ser. B 88 (2003) 135-151. [10] I. Gutman, N. Trinajstic, Graph theory and molecular orbitals, Top. Curr. Chem. 42 (1973) 49-93. [11] S.B. Hu, B.L. Liu, X.Z. Tan, On the nullity of bicyclic graphs, Linear Algebra Appl. 429 (2008) 1387-1391. [12] P. Lancaster, M. Tismenetsky, The Theory of Matrices, second ed., Academic Press Inc., Orlando, FL, 1985. [13] S.C. Li, On the nullity of graphs with pendant vertices, Linear Algebra Appl. 429 (2008) 16191628. [14] S.C. Li, F.F. Song, On the positive and negative inertia of weighted graphs, arXiv:1307.5110 [math.CO] [15] H.C. Longuet-Higgins, Some studies in molecular orbital theory I. Resonance structures and molecular orbitals in unsaturated hydrocarbons, J. Chem. Phys. 18 (1950) 265-274. [16] H.C. Ma, W.H. Yang, S.G. Li, Positive and negative inertia index of a graph, Linear Algebra Appl. 438 (1) (2013) 331-341. [17] M. Nath, B.K. Sarma, On the null-spaces of acyclic and unicyclic singular graphs, Linear Algebra Appl. 427 (2007) 42-54. [18] X.Z. Tan, B.L. Liu, On the nullity of unicyclic graphs, Linear Algebra Appl. 408 (2005) 212220. [19] G.H. Yu, L.H. Feng, Q.W. Wang, Bicyclic graphs with small positive index of inertia, Linear Algebra Appl. 438 (2013) 2036-2045. [20] G.H. Yu, L.H. Feng, X.D. Zhang, The inertia of weighted unicyclic graphs, Linear Algebra Appl. 448 (2014) 130-152. [21] X.Z. Tan, B.L. Liu, The nullity of (k — 1)-cyclic graphs, Linear Algebra Appl. 438 (2013) 3144-3153.