¿^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) 285-299
On the inertia of weighted (k — 1)-cyclic graphs*
Shibing Deng , Shuchao Li, Feifei Song
Faculty of Mathematics and Statistics Central China Normal University, Wuhan 430079, P. R. China
Received 21 May 2014, accepted 24 October 2014, published online 16 December 2015
Abstract
Let Gw be a weighted graph. The inertia of Gw is the triple In(Gw) = (i+ (Gw), i-(Gw),i0(Gw)), where i+(Gw),i-(Gw),i0(Gw) are, respectively, the number of the positive, negative and zero eigenvalues of the adjacency matrix A(Gw) of Gw including their multiplicities. A simple n-vertex connected graph is called a (k - 1)-cyclic graph if its number of edges equals n + k - 2. Let 0(r1,r2,... ,rk)w be an n-vertex simple weighted graph obtained from k weighted paths (Pri )w, (Pr2 )w,..., (Prk )w by identifying their initial vertices and terminal vertices, respectively. Set Qk := {0(r1,r2,..., rk)w : ri + r2 + ■ ■ ■ + rk = n + 2k - 2}. The inertia of the weighted graph d(r1,r2,... ,rk)w is studied. Also, the weighted (k — 1)-cyclic graphs that contain 6(r1, r2,..., rk)w as an induced subgraph are studied. We characterize those graphs among Qk that have extreme inertia. The results generalize the corresponding results obtained by Tan and Liu in 2013 andYuetal., 2014.
Keywords: Weighted k-cyclic graph, adjacency matrix, inertia. Math. Subj. Class.: 05C50, 15A18
1 The first section
In this paper, we only consider simple weighted graphs on positive weight set. Let Gw be a weighted graph with vertex set [v\,v2,... ,vn}, edge set E(Gw) = 0 and weight set W(Gw) = {w(e) > 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_1ii_1Wjij +
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 \ /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,i^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) 403-413
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\ + n-3 and q := t + n2. It is easy to see that Gw e ©fc, we arrange the structure of Gw as follows: First come the paths Pri,..., Pr with r s' r-> s' ... s' r„ and r, = :!
(mod 4), i = 1, 2,... ,ni; next Pr„i+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 Pr9+1 ,...,PTk with rg+1 < rq+2 < ... < rfc and ri = 0 (mod 4), i = q + 1, q + 2,..., fc. Let Mj be the neighbor of vq in the odd path Pri, i = 1,2,... ,t. Let P* = u\u\ ... u2s. (1 < i < fc) 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 a,j = 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 = Hu2ju2j+1) (* =	= 1,..., ^¡ViP^l - 1). Then the adja-
cency 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	Pi I3t	0
T at+i T ak	0	At+1 Ak	0	0l+i Pi
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 0f (i = 1,..., k). After that, column operations are applied so that each «j and p are reduced to 0s. By Lemma 2.5, —af A-1aj = — pf A-1 p = 0 and c = —af Ar1^ = — pfA-1aj, where

Cj = <
«jb»wi2w23 . . ,-1, wl 1w22 ...
2w23 . . .
wl 1w22 . .	i,Si
if |Aj| = 2sj = 2 (mod 4);
if |Aj| = 2sj = 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 = ^ 4
j=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
Afc /
(3.2)
292
Ars Math. Contemp. 11 (2016) 403-413
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 — ^ .
(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) 403-413
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) 403-413
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 d®cfc-1 = c®dk-1 for some 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, 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 = cjdt 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	cfc-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 G1, 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, = Cidk_i holds for i = 1.2..... /;• — I. Iff/ is isomorphic to G6 or G7, the weighted condition is ckdi = 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 , tl, = r/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\ = -^l2 + ^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 Ck~2<ii = 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, G4) 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.
299
Ars Math. Contemp. 11 (2016) 403-413
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
136
[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.