Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 6 (2013) 171–185
Sharp spectral inequalities for connected
bipartite graphs with maximal Q-index
Milica And̄elić ∗
Department of Mathematics, University of Aveiro, 3810-193 Aveiro, Portugal
Faculty of Mathematics, University of Belgrade, 11 000 Belgrade, Serbia
C. M. da Fonseca †
Department of Mathematics, University of Coimbra, 3001-501 Coimbra, Portugal
Tamara Koledin
Faculty of Electrical Engineering, University of Belgrade, 11 000 Belgrade, Serbia
Zoran Stanić ‡
Faculty of Mathematics, University of Belgrade, 11 000 Belgrade, Serbia
Received 31 October 2011, accepted 26 December 2011, published online 11 July 2012
Abstract
The Q-index of a simple graph is the largest eigenvalue of its signless Laplacian. As
for the adjacency spectrum, we will show that in the set of connected bipartite graphs
with fixed order and size, the bipartite graphs with maximal Q-index are the double nested
graphs. We provide a sequence of (in)equalities regarding the principal eigenvector of the
signless Laplacian of double nested graphs and apply these results to obtain some lower
and upper bounds for their Q-index. In the end, we give some computational results in
order to compare these bounds.
Keywords: Double nested graph, signless Laplacian, largest eigenvalue, spectral inequalities.
Math. Subj. Class.: 05C50
∗Research supported by CIDMA - Center for Research and Development in Mathematics and Applications,
FCT - Fundação para a Ciência e a Tecnologia, through European program COMPETE/FEDER and Serbian
Ministry of Education and Science, Project 174033.
†Research supported by CMUC - Centro de Matemática da Universidade de Coimbra and FCT - Fundação
para a Ciência e a Tecnologia, through European program COMPETE/FEDER
‡Research supported by Serbian Ministry of Education and Science, Projects 174012 and 174033.
E-mail addresses: milica.andelic@ua.pt (Milica And̄elić), cmf@mat.uc.pt (C. M. da Fonseca),
tamara@etf.rs (Tamara Koledin), zstanic@math.rs (Zoran Stanić)
Copyright c© 2013 DMFA Slovenije
172 Ars Math. Contemp. 6 (2013) 171–185
1 Introduction
Let G = (V,E) be a (simple) graph, of order ν = |V | and size  = |E|. The signless
Laplacian of G is defined to be the matrix Q = A+D, where A(= A(G)) is the adjacency
matrix of G, while D(= D(G)) is the diagonal matrix of its vertex degrees. The largest
eigenvalue (or spectral radius) of Q is usually called the Q-index of G, and is denoted by
κ(= κ(G)). Much interest has been paid recently to this very important spectral invariant.
Let us recall that
∆ + 1 6 κ 6 2(ν − 1) , (1.1)
where ∆ denotes the maximal vertex degree of the graph, with equality for stars, on the
lower bound, and complete graphs, on upper bound [7].
In 2007, Cvetković, Rowlinson, and Simić [6] conjectured that
κ 6 ν − 1 + d̄ , (1.2)
where d̄ is the average (vertex) degree of a graph. Later Feng and Yu [9] proved that (1.2)
is true (cf. also [1]). Many other bounds on Q-index for arbitrary (connected) graphs can
be found in [8].
We will now describe in brief the structure of a connected double nested graph (or DNG
for short). It was first considered in [3, 4] and, independently, under the name of chain
graph, in [5], in studying graphs whose least eigenvalue is minimal among the connected
(bipartite) graphs of fixed order and size. The vertex set of any such graph G consists of
two colour classes (or co-cliques). To specify the nesting, both of them are partitioned
into h non-empty cells
h⋃
i=1
Ui and
h⋃
i=1
Vi, respectively; all vertices in Us are joined (by
cross edges) to all vertices in
h+1−s⋃
k=1
Vk, for s = 1, 2, . . . , h. Denote by NG(w) the set of
neighbors of a vertex w. Hence, if u′ ∈ Us+1, u′′ ∈ Us, v′ ∈ Vt+1, and v′′ ∈ Vt, then
NG(u
′) ⊂ NG(u′′) and NG(v′) ⊂ NG(v′′). This claim makes precise the double nesting
property. Observe that 1 6 s, t 6 h.
If ms = |Us| and ns = |Vs|, with s = 1, 2, . . . , h, then G is denoted by
DNG(m1,m2, . . . ,mh;n1, n2, . . . , nh) .
Note that G is connected whenever m1, n1 > 0. Additionally, if some of the remain-
ing parameters are equal to zero, we again get a DNG with a smaller value of h. Thus,
throughout we assume that all these parameters are greater than zero.
We now introduce some notation to be used later on. Let
Ms =
s∑
i=1
mi and Nt =
t∑
j=1
nj , for 1 6 s, t 6 h.
Thus G is of order ν = Mh+Nh and size  =
∑h
s=1msNh+1−s. Observe that Nh+1−s is
the degree of a vertex u ∈ Us; the degree of a vertex v ∈ Vt is equal to Mh+1−t. We also
set Ms,t = Mt −Ms−1 and, additionally, M1,t = Mt.
M. And̄elić et al.: Sharp spectral inequalities for connected bipartite graphs. . . 173
j z
ppp ppp
j z
j z




Q
Q
Q
Q
Q
L
L
L
L
L
L
L
L
L
L
L
L












Uh Vh
U2 V2
U1 V1
Figure 1: The structure of a double nested graph.
2 Extremal bipartite graphs
Let G be a bipartite graph with colour classes U and V . First, we state the main result of
this section.
Theorem 2.1. If G is a graph for which κ(G) is maximal among all connected bipartite
graphs of order ν and size , thenG is a DNG with all pendant edges attached to a common
vertex.
Theorem 2.1 means that double nested graphs play the same role among bipartite graphs
(with respect to the signless Laplacian index) as nested split graphs among non-bipartite
graphs. The same classes of graphs appear as extremal with respect to the adjacency spectra
as well, i.e., in the class of all connected (resp. all connected bipartite) graphs of fixed order
and size, those with maximal radius with respect to the adjacency matrix are NSGs (resp.
DNGs). The proof of Theorem 2.1 is based on the following lemmas, the first of which is
taken from [6]. Recall that there exists a unique unit eigenvector corresponding to κ(G)
having only positive entries; this eigenvector is called the principal eigenvector of G.
Lemma 2.2. Let G′ be the graph obtained from a connected graph G by rotating the
edge rs around r to the non-edge position rt. Let x = (x1, x2, . . . , xν)T be the principal
eigenvector of G. If xt > xs then κ(G′) > κ(G).
The next lemma will be very helpful when we find a bridge in a graph whose index is
assumed to be maximal. Given two rooted graphs P (= Pu) and Q(= Qv) with u and v
as roots, let G be the graph obtained from the disjoint union P ∪̇Q by adding the edge uv.
Let G′ be the graph obtained from the coalescence of Pu and Qv by attaching a pendant
edge at the vertex identified with u and v.
Lemma 2.3. With the above notation, if P and Q are two non-trivial connected graphs
then κ(G) < κ(G′).
Proof. Let (x1, x2, . . . , xν)T be the principal eigenvector of G. Without loss of generality,
we may suppose that xu 6 xv . Let NP (u) be the neigbourhood of u in P ; since P is
174 Ars Math. Contemp. 6 (2013) 171–185
non-trivial, NP (u) 6= ∅. Now G′ is obtained from G by replacing the edges uw, with w ∈
NP (u) by the edges vw and, therefore, κ(G) < κ(G′), by Lemma 2.2, as required.
In what follows we assume that G has maximal index among the connected bipartite
graphs of fixed order and size.
Lemma 2.4. LetG be a graph satisfying the above assumptions, and let x = (x1, . . . , xν)T
be the principal eigenvector of G. If v and w are vertices in the same colour class such
that xv > xw, then deg(v) > deg(w).
Proof. Let U, V be the colour classes of G. Assuming that v and w are vertices in V such
that xv > xw and deg(v) < deg(w), then deg(w) > 1 and there exists u ∈ U such
that v 6∼ u ∼ w. By Lemma 2.3, we may rotate uw to uv to obtain a graph G′ such
that κ(G′) > κ(G). If uw is a bridge, then deg(u) = 1 and, again by Lemma 2.3, G′
is necessarily connected; but now the maximality of κ(G) is contradicted and the proof is
complete.
From now on we take the colour classes to be U = {u1, u2, . . . , um} and V =
{v1, v2, . . . , vn}, with xu1 > xu2 > · · · > xum and xv1 > xv2 > · · · > xvn . By
Lemma 2.4, this ordering coincides with the ordering by degrees in each colour class. In
the next lemma we note some consequences of those facts.
Lemma 2.5. Let G be a graph satisfying the above assumptions including those on vertex
ordering. Then
(i) the vertices u1 and v1 are adjacent;
(ii) u1 is adjacent to every vertex in V , and v1 is adjacent to every vertex in U ;
(iii) if the vertex u is adjacent to vk, then u is adjacent to vj , for all j < k, and if the
vertex v is adjacent to uk, then v is adjacent to uj , for all j < k.
Proof. First we consider bridges in G. By Lemma 2.3, all bridges are pendant edges. By
Lemma 2.2, all pendant edges are attached at the same vertex, and this vertex w is such
that xw is maximal. Without loss of generality, xu1 > xv1 and w = u1. It follows that the
result holds if G is a tree and, consequently, G is a star. Accordingly, we suppose that G is
not a tree.
To prove (i), suppose by way of contradiction that u1 6∼ v1. Then v1 is adjacent to some
vertex u ∈ U , and uv1 is not a bridge. By Lemma 2.2, we may rotate v1u to v1u1 to obtain
a connected bipartite graph G′ such that κ(G′) > κ(G), contradicting the maximality of
κ(G).
To prove (ii), suppose that u is a vertex of U not adjacent to v1. Then u 6= u1 by (i), uv
is not a bridge, and u is adjacent to some vertex v in V other than v1. Now we can rotate
uv to uv1 to obtain a contradiction as before. Secondly, suppose that v is a vertex of V not
adjacent to u1. Then v 6= v1 by (i), again vu1 is not a bridge, and a rotation about v yields
a contradiction.
To prove (iii), suppose that u ∈ U , u ∼ vk and u 6∼ vj for some j < k. Now u 6= u1
by (ii), and so uvk is not a bridge. Then we can rotate uvk to uvj to obtain a contradiction.
Finally, suppose that v ∈ V, v ∼ vk and v 6∼ uj for some j < k. In this case, vuk is not a
bridge because k > 1, and the rotation of vuk to vuj yields a contradiction.
The proof is now finished.
M. And̄elić et al.: Sharp spectral inequalities for connected bipartite graphs. . . 175
Taking into account Lemma 2.5 and the definition of a DNG the first part of Theorem
2.1 follows. It remains only to prove that all cut-edges in the observed DNG are pendant
edges attached to a common vertex. This easily comes from Lemma 2.3.
3 Q-eigenvectors of DNGs
Here we consider the principal eigenvector of the signless Laplacian of DNGs. In this
section (and in the next one, if not told otherwise) we will assume that
x = (x1, . . . , xν)
T
is a Q-eigenvector of G with all positive entries, which is usually normalized, i.e.,
ν∑
i=1
xi = 1 .
The entries of x are also called the weights of the corresponding vertices. We first observe
that all vertices within the sets Us or Vt, for 1 6 s, t 6 h, have the same weights, since
they belong to the same orbit of G. Let xu = as, if u ∈ Us, while xv = bt, if v ∈ Vt.
From the eigenvalue equations for κ, applied to any vertex from Us or Vt, we get
κas = Nh+1−sas +
h+1−s∑
j=1
njbj , for s = 1, . . . , h, (3.1)
and
κbt = Mh+1−tbt +
h+1−t∑
i=1
miai , for t = 1, . . . , h. (3.2)
By normalization we have
h∑
i=1
miai +
h∑
j=1
njbj = 1 , (3.3)
and, from (3.1), we easily get
as =
1
κ−Nh+1−s
h+1−s∑
j=1
njbj , for s = 1, . . . , h. (3.4)
From (3.2) we have
bt =
1
κ−Mh+1−t
h+1−t∑
i=1
miai, for t = 1, . . . , h, (3.5)
and therefore, using (3.3), we have
as =
1
κ−Nh+1−s
1− h∑
i=1
miai −
h∑
j=h+2−s
njbj
 , for s = 1, . . . , h, (3.6)
176 Ars Math. Contemp. 6 (2013) 171–185
or, using (3.2) for t = 1,
as =
1
κ−Nh+1−s
1− (κ−Mh)b1 − h∑
j=h+2−s
njbj
 , for s = 1, . . . , h.
Similarly,
bt =
1
κ−Mh+1−t
(
1− (κ−Nh)a1 −
h∑
i=h+2−t
miai
)
, for t = 1, . . . , h.
Setting ah+1 = bh+1 = 0 and N0 = 0, from (3.4) and (3.6), together with (3.3), we get
successively
(κ−Nh−s)as+1 − (κ−Nh+1−s)as = −nh+1−sbh+1−s, for s = 1, . . . , h− 1,
and
(κ− n1)ah = n1b1, for s = h.
Since all components of x are positive and κ > ∆ + 1 (1.1), it comes
as+1 6 as, for s = 1, . . . , h− 1, (3.7)
and
bt+1 6 bt, for t = 1, . . . , h− 1. (3.8)
Furthermore, by setting s = h in (3.2), we obtain
(κ−m1)bh = m1a1. (3.9)
Moreover, substituting s = 1 in (3.1) and t = 1 in (3.2) and applying in (3.3) we get
(κ−Nh)a1 + (κ−Mh)b1 = 1,
and finally
as =
1
κ−Nh+1−s
(κ−Nh)a1 − h∑
j=h+2−s
njbj
 . (3.10)
Next we focus our attention on bounding ai’s and bj’s.
Lemma 3.1. For any s = 1, . . . , h, we have
Nh+1−sbh+1−s
κ−Nh+1−s
6 as 6
Nh+1−sb1
κ−Nh+1−s
. (3.11)
Proof. From (3.4), we have
as =
1
κ−Nh+1−s
h+1−s∑
j=1
njbj .
Therefore, (3.11) immediately follows since bj’s are strictly decreasing, from (3.8).
M. And̄elić et al.: Sharp spectral inequalities for connected bipartite graphs. . . 177
Lemma 3.2. For any s = 1, . . . , h,
as 6 a1
(
1− Nh+2−s,h
κ−Nh+1−s
(
1 +
m1
κ−m1
))
, (3.12)
Proof. The inequality (3.12) follows from (3.10), since bi’s are strictly decreasing, bearing
in mind (3.9) as well.
Lemma 3.3. For any s = 1, . . . , h,
as >
a1
κ−Nh+1−s
(
1−
s−1∑
i=1
nh+1−iMi
κ−Mi
)
.
Proof. By induction on s. For s = 1, the inequality holds trivially. Assume next that
as >
a1
κ−Nh+1−s
(
1−
s−1∑
i=1
nh+1−iMi
κ−Mi
)
,
for s > 1. Then
as+1 =
1
κ−Nh−s
h−s∑
j=1
njbj
=
1
κ−Nh−s
((κ−Nh+1−s)as −Nh+1−sbh+1−s)
>
a1
κ−Nh−s
(
1−
s−1∑
i=1
nh+1−iMi
κ−Mi
)
− Nh+1−sMsa1
(κ−Nh−s)(κ−Ms)
=
a1
κ−Nh−s
(
1−
s∑
i=1
nh+1−iMi
κ−Mi
)
.
This ends the proof.
Lemma 3.4. For any s = 1, . . . , h, we have
as 6
b1
κ−Nh+1−s
(
Nh+1−s −
κfh+1−s
(κ− n1)(κ−Ms)
)
, (3.13)
where
fh+1−s =
h+1−s∑
j=1
njMh+2−j,h .
Proof. From (3.4) and (3.12) applied to bj , we get
as =
1
κ−Nh+1−s
h+1−s∑
j=1
njbj
6
1
κ−Nh+1−s
h+1−s∑
j=1
njb1
(
1− Mh+2−j,h
κ−Mh+1−j
(
1 +
n1
κ− n1
))
6
b1
κ−Nh+1−s
(
Nh+1−s −
κfh+1−s
(κ− n1)(κ−Ms)
)
.
The proof is now complete.
178 Ars Math. Contemp. 6 (2013) 171–185
4 Some bounds on the Q-index of a DNG
In this section we obtain some upper and lower bounds on the Q-index of DNGs using the
eigenvalue and the matrix technique. We also emphasize that our main goal is to consider
the estimation of theQ-index of large graphs. Before we proceed, we provide the following
observations.
First, if h = 1 we get a complete bipartite graph Km1,n1 , whose Q-index is equal
to m1 + n1 = ν [2]. Furthermore, since the Q-index of an arbitrary graph increases by
inserting edges (cf. [6]), we have
κ 6 ν, (4.1)
for any (not necessarily connected) DNG.
Otherwise, if h > 1 is fixed but the graph size is not, using the same previous ar-
guments, the maximal Q-index would appear in DNG(m1, 1, . . . , 1;n1, 1, . . . , 1). The
computational results suggest this will happen when |m1−n1| 6 1. So, these cases are not
interesting for our research and, therefore, we will assume that h > 1 and the size is fixed.
4.1 Eigenvalue technique
Now we establish some bounds for the Q-index of DNGs using the eigenvalue technique.
We start with lower bounds.
Proposition 4.1. If G is a connected DNG, then
κ > max
16k6h
{Mh+1−k +Nk}.
Proof. On the one hand, from (3.2), we get
bk =
1
κ−Mh+1−k
h+1−k∑
i=1
miai >
Mh+1−kah+1−k
κ−Mh+1−k
,
since, from (3.7), ai’s are decreasing. On the other hand, from (3.1), we get
ah+1−k =
1
κ−Nk
k∑
j=1
njbj >
Nkbk
κ−Nk
,
since bj’s are decreasing, from (3.8). From the last two inequalities we get
κ(κ− (Mh+1−k +Nk)) > 0,
which is equivalent to
κ >Mh+1−k +Nk.
In particular, for k = h and k = 1, we obtain the following corollary.
Corollary 4.2. If G is a connected DNG, then
κ > m1 +Nh and κ > n1 +Mh .
M. And̄elić et al.: Sharp spectral inequalities for connected bipartite graphs. . . 179
Proposition 4.3. If G is a connected DNG, then
κ >
1
2
t+ 
Nh
+
√(
t− 
Nh
)2
+ 4ê∗h
 ,
where
t =
∑h
i=1miN
3
h+1−i∑h
i=1miN
2
h+1−i
and ê∗h =
h∑
i=1
mi
N2h+1−i
Nh
.
Proof. Let y = (y1, . . . , yν)T be a vector whose components are indexed by the vertices of
G, and let yu = Nh+1−i if u ∈ Ui, for some i ∈ {1, . . . , h}, or, otherwise, yv = q = κ− t,
for some t, if v ∈ Vj for some j ∈ {1, . . . , h}. Substituting y into the Rayleigh quotient
(see, e.g., [8, p. 49]) we obtain
κ >
2
∑h
i=1miN
2
h−1+iq +
∑h
i=1miN
3
h+1−i +
∑h
i=1 niMh−1+iq
2∑h
i=1miN
2
h+1−i +Nhq
2
due to Rayleigh’s principle which reads
yTQy
yT y
6 κ. Since q = κ− t, we get
Nhq
3 + (Nht− )q2 −
h∑
i=1
miN
2
h+1−iq >
h∑
i=1
miN
3
h+1−i − t
h∑
i=1
miN
2
h+1−i .
Choosing
t =
∑h
i=1miN
3
h+1−i∑h
i=1miN
2
h+1−i
,
and having in mind that N1 6 t 6 Nh, we immediately get a quadratic inequality in q and
the proof is concluded.
Proposition 4.4. If G is a connected DNG, then
κ 6
1
2
(
ν +
√
ν2 − 4(MhNh − )
)
. (4.2)
Proof. From (3.1), with s = h, and from (3.3), recalling (3.11), we get
(κ−Mh)b1 =
h∑
i=1
miai 6
h∑
i=1
mi
Nh+1−i
κ−Nh+1−s
b1 .
Then, we obtain
(κ−Mh)(κ−Nh) 6 ,
and, therefore, from the quadratic inequality
κ2 − (Mh +Nh)κ+MhNh −  6 0,
we obtain κ1 6 κ 6 κ2 where κ1 and κ2 are the solutions of the associated quadratic
equality, and this completes the proof.
180 Ars Math. Contemp. 6 (2013) 171–185
The next two bounds improve the bound (4.2). We recall that fh+1−i is defined in
Lemma 3.4.
Proposition 4.5. If G is a connected DNG, then
κ 6
1
2
(
ν +
√
ν2 − 4(MhNh − ′)
)
,
where
′ = − ν(ν −Nh)
(ν − n1)2(ν −m1)
h∑
i=1
mifh+1−i .
Proof. As in the proof of Proposition 4.4, we have
(κ−Mh)b1 =
h∑
i=1
miai .
Using (3.12), we get
κ−Mh 6
h∑
i=1
mi
κ−Nh+1−i
(
Nh+1−i −
κfh+1−i
(κ− n1)(κ−Mi)
)
,
and therefore
(κ−Mh)(κ−Nh) 6 −
κ(κ−Nh)
(κ− n1)2(κ−m1)
h∑
i=1
mifh+1−i .
Taking into account that κ 6 ν, from Proposition 4.4 it follows
(κ−Mh)(κ−Nh) 6 ′,
and the proof ends.
The next result may be proved in a similar way.
Proposition 4.6. If G is a connected DNG, then
κ 6
1
2
(
ν +
√
ν2 − 4(MhNh − ′′)
)
,
where
′′ = − κ
′(κ′ −Nh)
(κ′ − n1)2(κ′ −m1)
h∑
i=1
mifh+1−i,
for
κ′ =
1
2
(
ν +
√
ν2 − 4(MhNh − ′)
)
.
M. And̄elić et al.: Sharp spectral inequalities for connected bipartite graphs. . . 181
4.2 Matrix technique
The partition
V =
h⋃
k=1
Uk ∪
h⋃
k=1
Vk (4.3)
is equitable since every vertex in Ui and every vertex in Vi have the same number of neigh-
bors in Uj and Vj , for all i, j ∈ {1, 2, . . . , h}. Let AD be the signless Laplacian divisor
matrix of a DNG(m1, . . . ,mh;n1, . . . , nh) with respect to the equitable partition (4.3).
The matrix AD has the following form:
AD =

Nh n1 n2 · · · nh−1 nh
Nh−1 n1 n2 · · · nh−1
. . .
...
... ...
N2 n1 n2
N1 n1
m1 m2 · · · mh−1 mh Mh
m1 m2 · · · mh−1 Mh−1
...
... ...
. . .
m1 m2 M2
m1 M1

,
where the non-mentioned entries are to be read as zero. Setting
N =

n1 n2 · · · nh−1 nh
n1 n2 · · · nh−1
...
... ...
n1 n2
n1
 , M =

m1 m2 · · · mh−1 mh
m1 m2 · · · mh−1
...
... ...
m1 m2
m1
 ,
D1 = diag(Nh, . . . , N1), and D2 = diag(Mh, . . . ,M1), AD can be rewritten in the com-
pact block form
AD =
(
D1 N
M D2
)
.
In order to obtain more bounds we set
P =
(
0 xI
I 0
)
,
for some x 6= 0. Since the matrices
PADP
−1 =
(
D2 xM
x−1N D1
)
and AD are similar, they have the same index. We choose x such that the sum in the first
row and the (h + 1)-th row are equal. It leads to Mhx2 − (Nh −Mh)x − Nh = 0, i.e.,
x = NhMh . By Frobenius Theorem [11, Theorem 3.1.1], we have
min
16i6n
Ri 6 κ 6 max
16i6n
Ri,
182 Ars Math. Contemp. 6 (2013) 171–185
where Ri stands for the sum of elements in the i-th row of PADP−1. Using this, we get
the following result.
Proposition 4.7. If G is a connected DNG, then
min
{
n1
(
Nh
Mh
+ 1
)
, n1
(
Mh
Nh
+ 1
)}
6 κ 6 Nh +Mh = ν. (4.4)
Clearly, the upper bound does not provide a decisive progress in our quest (recall (4.1)).
We will establish some more interesting improvements next.
Let Ri be the sum of the entries in row i of the matrix AD. It is easy to confirm that
Ri = 2Nh−i+1, for i ∈ {1, . . . , h}
= 2Mh−i+1, for i ∈ {h+ 1, . . . , 2h},
and, therefore,
maxRi = max{2Nh, 2Mh}.
By Frobenius Theorem
min{2n1, 2m1} 6 κ 6 max{2Nh, 2Mh}. (4.5)
Here the upper bound does not make any (general) improvement since max{2Nh, 2Mh} >
ν (compare (4.1)), so next we use the result of Minc (see [10]), which for the matrix AD
reads:
min
i
∑h
j=1(AD)ijRj
Ri
6 κ 6 max
i
∑h
j=1(AD)ijRj
Ri
.
Proposition 4.8. If G is a connected DNG, then
min{n1 +Mh,m1 +Nh} 6 κ 6 max
{

Nh
+Nh,

Mh
+Mh
}
. (4.6)
The bounds (4.6) obviously improve both (4.4) and (4.5), but the lower bound is still
rough comparing with Corollary 4.2.
5 Computational results
In this final section, we provide several examples which can help to gain a better insight
into the quality of the bounds obtained in the previous section.
We compute the lower bounds of Propositions 4.1 and 4.3, and the upper bounds from
Propositions 4.4, 4.5, 4.6, and 4.8. One observes that the bound from Proposition 4.1 is
always integral. The number of vertices in the corresponding DNG is also given in every
example since it makes another upper bound (cf. (4.1)). It can be easy checked that the
lower bounds from Corollary 4.2 and Propositions 4.7 and 4.8, all of them having simple
expressions, are rough in some cases, and therefore they are not considered in our examples.
We also compute the relative errors in each case.
Example 5.1. First we consider a randomly chosen DNG with small number of vertices
and some larger DNGs derived from the previous one:
G1 = DNG(2, 2, 5, 3; 2, 3, 1, 1);
G2 = DNG(10, 10, 25, 15; 10, 15, 5, 5);
G3 = DNG(200, 200, 500, 300; 200, 300, 100, 100);
M. And̄elić et al.: Sharp spectral inequalities for connected bipartite graphs. . . 183
Prop. 4.3 Prop. 4.1 κ Prop. 4.8 Prop 4.6 Prop 4.5 Prop 4.4 ν
G1 13.6785 14 15.6451 16.7500 17.0210 17.0550 17.4530 19
-12.57% -10.52% 7.06% 8.79% 9.01% 11.56% 21.44%
G2 68.3923 70 78.2257 83.7500 85.1052 85.2749 87.2649 95
-12.57% -10.52% 7.06% 8.79% 9.01% 11.56% 21.44%
G3 1367.8452 1400 1564.5133 1675.0000 1702.1030 1705.4985 1745.2987 1900
-12.57% -10.52% 7.06% 8.79% 9.01% 11.56% 21.44%
Notice that κ(G2) (resp. κ(G3)) is very close to 5κ(G1) (resp. 100κ(G3)); we get
5κ(G1) − κ(G2) ≈ 10−7. Since the similar fact holds for all bounds obtained (compare
the corresponding propositions), we get the same results for the relative errors.
Example 5.2. Here we consider the DNGs obtained from G1 by multiplying some of its
parameters:
H1 = DNG(2000, 2, 5, 3; 2, 3, 1, 1000);
H2 = DNG(2000, 2, 5, 3; 2, 3, 1000, 1);
H3 = DNG(2000, 2, 5, 3; 2, 3000, 1, 1);
H4 = DNG(2000, 2, 5, 3; 2000, 3, 1, 1);
Prop. 4.3 Prop. 4.1 κ Prop. 4.8 Prop 4.6 Prop 4.5 Prop 4.4 ν
H1 3006.0284 3006 3006.0287 3011.0164 3008.2682 3008.2960 3012.6750 3016
-8 · 10−6% -1 · 10−3% 0.17% 0.07% 0.08% 0.22% 0.33%
H2 3008.0175 3007 3008.0177 3012.0104 3009.8145 3009.8323 3013.3388 3016
-5 · 10−6% -0.03% 0.13% 0.06% 0.06% 0.18% 0.27%
H3 5010.9908 5009 5010.9909 5010.9980 5011.7199 5011.7199 5012.2008 5014
-5 · 10−7% -0.04% 1 · 10−4% 0.15% 0.15% 0.02% 0.06%
H4 4014.9731 4010 4014.9732 4014.9866 4014.9800 4014.9800 4014.9933 4015
-3 · 10−6% -0.12% 3 · 10−4% 2 · 10−4% 2 · 10−4% 5 · 10−4% 7 · 10−4%
In this example all bounds are (more or less) close to the exact value of Q-index. We
already pointed that the bounds obtained in Propositions 4.5 and 4.6 are the improvements
of the one obtained in Proposition 4.4. This example shows that the bound from Proposition
4.8 is incomparable to them. In opposition to the previous example, here Proposition 4.1
gives a better estimation than Proposition 4.3.
Example 5.3. The parameters of the following DNGs are obtained by multiplying the
parameters of G1 by 1, 10, 100 or 1000 ad hoc.
I1 = DNG(2, 2, 5, 3; 2000, 300, 10, 1);
I2 = DNG(2, 2, 5, 3; 2, 30, 100, 1000);
I3 = DNG(2000, 200, 50, 30; 2000, 300, 10, 1);
Prop. 4.3 Prop. 4.1 κ Prop. 4.8 Prop 4.6 Prop 4.5 Prop 4.4 ν
I1 2255.0867 2314 2316.3632 2322.5716 2322.5716 2322.5733 2322.5737 2323
-2.65% -0.10% 0.26% 0.27% 0.27% 0.27% 0.29%
I2 1118.5026 1134 1134.0007 1134.3799 1134.4002 1134.4000 1134.4002 1144
-1.37% -6 · 10−5% 0.03% 0.04% 0.04% 0.04% 0.88%
I3 4562.6064 4550 4562.6584 4563.2717 4563.1367 4563.1369 4563.6312 4591
-0.28% -1 · 10−3% 0.01% 0.01% 0.01% 0.02% 0.62%
184 Ars Math. Contemp. 6 (2013) 171–185
Taking into account the lower bound of Proposition 4.3, one can conclude that its devia-
tion from the exact value is expected for I1 (and other similar graphs). Note that Proposition
4.6 will often give better bound than Proposition 4.5, but not always – see graphs I2 or J2
in the next example.
Example 5.4. Finally, we consider the extensions of the original graphs:
J1 = DNG(2, 2, 5, 3, 2, 3, 1, 1; 2, 3, 1, 1, 2, 2, 5, 3);
J2 = DNG(20000, 2, 5, 3, 10, 10, 10, 10; 2, 3, 1, 10000, 10, 10, 10, 10);
J3 = DNG(2, 2, 5, 3, 1, 1, 1, 1; 2000, 300, 10, 1, 1, 1, 1, 1);
Prop. 4.3 Prop. 4.1 κ Prop. 4.8 Prop 4.6 Prop 4.5 Prop 4.4 ν
J1 23.1888 23 27.4601 29.0526 32.3032 32.3022 32.8203 38
-15.56% -16.24% 5.80% 17.64% 17.64% 19.52% 38.38%
J2 30065.9176 30046 30065.9178 30080.9446 30072.6747 30072.7003 30085.9668 30096
-6 · 10−7% -0.07% 0.05% 0.02% 0.02% 0.07% 0.10%
J3 2313.0140 2324 2327.5409 2330.8445 2330.8452 2330.8452 2330.8456 2331
-0.62% -0.15% 0.14% 0.14% 0.14% 0.14% 0.15%
The bounds obtained will be used in a forthcoming research regarding the graphs with
maximal Q-index and fixed (but high) orders and also a fixed particular size. We also
remark that the results could be also compared to the corresponding bounds obtained for
the adjacency spectra.
Acknowledgment
The authors thank two anonymous referees for providing constructive comments in im-
proving the contents of this paper.
References
[1] M. And̄elić, C. M. da Fonseca, S. K. Simić and D. V. Tošić, Connected graphs of fixed order and
size with maximal Q-index: Some spectral bounds, Discrete Appl. Math. 160 (2012), 448–459.
[2] M. And̄elić, T. Koledin and Z. Stanić, Nested graphs with bounded second largest (signless
Laplacian) eigenvalue, Electron. J. Linear Algebra 24 (2012), to appear.
[3] F. K. Bell, D. Cvetković, P. Rowlinson and S. K. Simić, Graphs for which the least eigenvalue
is minimal, I, Linear Algebra Appl. 429 (2008), 234–241.
[4] F. K. Bell, D. Cvetković, P. Rowlinson and S. K. Simić, Graphs for which the least eigenvalue
is minimal, II, Linear Algebra Appl. 429 (2008), 2168–2179.
[5] A. Bhattacharya, S. Friedland and U. N. Peled, On the first eigenvalue of bipartite graphs,
Electron. J. Combin. 15 (2008), R#144.
[6] D. Cvetković, P. Rowlinson and S. K. Simić, Eigenvalue bounds for the signless Laplacian,
Publ. Inst. Math. (Beograd), 81 (95) (2007), 11–27.
[7] D. Cvetković, P. Rowlinson and S. K. Simić, Signless Laplacians of finite graphs, Linear Alge-
bra Appl. 423 (2007), 155–171.
[8] D. Cvetković, P. Rowlinson and S. K. Simić, An Introduction to the Theory of Graph Spectra,
Cambridge University Press, 2009.
M. And̄elić et al.: Sharp spectral inequalities for connected bipartite graphs. . . 185
[9] L.-H. Feng, G.-H. Yu, On three conjectures involving the signless Laplacian spectral radius of
graphs, Publ. Inst. Math. (Beograd) 85 (99) (2009), 35–38.
[10] S.-L. Liu, Bounds for the greatest characteristic root of a nonnegative matrix, Linear Algebra
Appl. 239 (1996), 151–160.
[11] M. Marcus and H. Minc, A Survey of Matrix Theory and Matrix Inequalities, Dover Publica-
tions Inc., New York, 1992; unabridged reprint of the corrected 1969 printing, Prindle, Weber,
& Schmidt, Boston.