ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 22 (2022) #P4.05 / 595–608
https://doi.org/10.26493/1855-3974.2714.9b3
(Also available at http://amc-journal.eu)
Ordering signed graphs with large index
Maurizio Brunetti
Dip. di Matematica e Applicazioni, Universitá di Napoli ‘Federico II’,
P. le Tecchio 80, I-80125 Naples, Italy
Zoran Stanić *
Faculty of Mathematics, University of Belgrade,
Studentski trg 16, Belgrade, Serbia
Received 28 October 2021, accepted 5 January 2022, published online 3 August 2022
Abstract
The index of a signed graph is the largest eigenvalue of its adjacency matrix. We estab-
lish the first few signed graphs ordered decreasingly by the index in classes of connected
signed graphs, connected unbalanced signed graphs and complete signed graphs with a
fixed number of vertices.
Keywords: Adjacency matrix, largest eigenvalue, edge relocation, unbalanced signed graph, com-
plete signed graph.
Math. Subj. Class. (2020): 05C50, 05C22
1 Introduction
A signed graph Ġ is a pair (G, σ), where G = (V,E) is an unsigned graph, called the
underlying graph, and σ : E −→ {1,−1} is the sign function or the signature. The number
of vertices of Ġ is called the order and denoted by n. The edge set of Ġ is composed of the
subset E+ of positive edges and the subset E− of negative edges. We interpret an unsigned
graph as a signed graph with the all positive signature, that is the signature which assigns
1 to every edge.
The adjacency matrix AĠ of Ġ is obtained from the standard adjacency matrix of its
underlying graph by switching the sign of all 1’s which correspond to negative edges. The
eigenvalues of Ġ are identified to be the eigenvalues of its adjacency matrix; they form
*Corresponding author. Research of the second author is partially supported by the Serbian Ministry of Edu-
cation, Science and Technological Development via the University of Belgrade.
E-mail addresses: maurizio.brunetti@unina.it (Maurizio Brunetti), zstanic@matf.bg.ac.rs (Zoran Stanić)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
596 Ars Math. Contemp. 22 (2022) #P4.05 / 595–608
the spectrum of Ġ. The largest eigenvalue of Ġ is called the index and denoted by λ1 (or
λ1(Ġ)).
If S is a set of vertices of Ġ, the switched signed graph ĠS is obtained from Ġ by
reversing the signs of the edges in the cut [S, V (Ġ) \ S]. The signed graphs Ġ and ĠS are
said to be switching equivalent. The switching equivalence is an equivalence relation that
preserves the eigenvalues, and the switching class of Ġ is denoted by [Ġ].
A signed graph is said to be balanced if it switches to the signed graph with all positive
signature. Otherwise, it is said to be unbalanced. Equivalently, Ġ is balanced if every cycle
contained in Ġ is balanced [15].
Ordering of unsigned graphs by the largest eigenvalue of some associated matrix has
received a great deal of attention in literature. Many results can be found in [12]. More re-
cently, there has been a growing interest for extremal problems in the framework of signed
graphs. For instance, in [9] Koledin and the second author studied connected signed graphs
of fixed order, size and number of negative edges that maximize the index. In the wake
of that paper, signed graph maximizing the index in suitable subsets of complete signed
graphs have been studied in [2]. Let Un (resp. Bn) denote the class of unbalanced uni-
cyclic (resp. bicyclic) signed graphs of order n. Akbari et al. [1] determined the signed
graphs attaining the extremal indices in Un. Some of the same authors studied in [10]
signed graphs achieving the maximum index among signed graphs in Un of fixed girth.
The first five largest indices among signed graphs in Bn with n ⩾ 36 are detected by He
et al. [8]. Signed graphs in Un and Bn with extremal spectral radius were identified in [4].
Finally, extremal graphs in Un and Bn with respect to the least Laplacian eigenvalue were
studied in [5] and [3], respectively.
In [6] we determined the unbalanced signed graph with largest index, for every order
n. In this paper we continue this research by presenting a general method for ordering the
signed graphs with a fixed number of vertices by their index. We demonstrate the method
by determining the first few signed graphs ordered by the index in the class of connected
signed graphs, or connected unbalanced signed graphs, or complete signed graphs with n
vertices.
The paper is organized as follows. Section 2 contains a preliminary setting related to
the graphical representations of signed graphs in this paper along with terminology, nota-
tion, a few known results and the proofs of two preliminary lemmas. The main result that
provides the subsequent orderings is formulated in Theorem 3.2 of Section 3. Orderings
in the mentioned classes are considered in Sections 3–5. Further computations, including
orderings of signed graphs with a comparatively small number of vertices, are given in
Section 6.
2 Preparatory
We introduce a way of depicting signed graphs that will be used in the subsequent sections.
For a signed graph of order n, we draw only the negative edges and the non-edges, along
with the assumption that all non-depicted edges are positive. By convention, a negative
edge is represented by a full line and a non-edge is represented by a dotted line. Accord-
ingly, the complete signed graph with the all positive signature (i.e. the complete unsigned
graph) is represented by an empty figure, the complete signed graph with a single negative
edge is represented by a negative edge, and so on.
The following lemmas are taken from [13, 14].
M. Brunetti and Z. Stanić: Ordering signed graphs with large index 597
Lemma 2.1 ([14]). For a connected signed graph Ġ = (G, σ), we have λ1(Ġ) ≤ λ1(G)
with equality if and only if Ġ switches to G.
Lemma 2.2 ([13]). For an eigenvalue λ of a signed graph Ġ, there is a switching equiv-
alent signed graph for which the λ-eigenspace contains an eigenvector whose non-zero
coordinates are of the same sign.
For the sake of completeness we say that a signed graph of the previous lemma can
be constructed by taking Ġ with AĠx = λx and considering D
−1AĠD where D is the
diagonal matrix of ±1s whose negative entries correspond to negative coordinates of x.
We proceed with some notation. For a signed graph Ġ we denote by R(Ġ) the set of
signed graphs obtained by taking a positive edge e of some signed graph of the switching
class [Ġ], and then either removing e or reversing its sign.
Let S = (Ġ1, Ġ2, . . . , Ġg) be a sequence which consists of the representatives of all
switching equivalence classes of connected signed graphs with n vertices such that the
representatives are ordered non-increasingly by the index and chosen in such a way that,
for 1 ≤ i ≤ g, the λ1-eigenspace of Ġi contains an eigenvector whose non-zero coordinates
are positive. (The existence of Ġi is provided by Lemma 2.2.)
We now prove the following lemmas. They generalize known results for unsigned
graphs that can be found in [12, Lemma 1.28].
Lemma 2.3 (Changing an edge). Let x = (x1, x2, . . . , xn)⊺ be an eigenvector associated
with the index of a signed graph Ġ and let r, s be fixed vertices of Ġ.
(i) If xrxs ≥ 0 and rs is a non-edge (resp. rs is a negative edge), then for a signed
graph Ġ′ obtained by inserting a positive edge between r and s (resp. deleting rs or
reversing its sign) we have λ1(Ġ′) ≥ λ1(Ġ). If at least one of xr, xs is non-zero, the
previous inequality is strict.
(ii) If xrxs < 0 and rs is a non-edge (resp. rs is a positive edge), then for a signed
graph Ġ′ obtained by inserting a negative edge between r and s (resp. deleting rs or
reversing its sign) we have λ1(Ġ′) > λ1(Ġ).
Proof. We only demonstrate the proof of (i), as (ii) is proved analogously. If y is an
eigenvector associated with λ1(Ġ′), using the Rayleigh principle we get
λ1(Ġ
′)− λ1(Ġ)
= y⊺AĠ′y − x
⊺AĠx ≥ x
⊺AĠ′x− x
⊺AĠx = x
⊺(AĠ′ −AĠ)x
=
{
2xrxs if
(
rs /∈ E(Ġ) ∧ rs ∈ E+(Ġ′)
)
∨
(
rs ∈ E−(Ġ) ∧ rs /∈ E(Ġ′)
)
,
4xrxs if rs ∈ E−(Ġ) ∧ rs ∈ E+(Ġ′).
Hence, λ1(Ġ′) ≥ λ1(Ġ).
Assume that xr ̸= 0 and, by way of contradiction, that λ1(Ġ′) = λ1(Ġ). In this
case, the inequality in the previous chain reduces to equality, which means that x is an
eigenvector afforded by λ1(Ġ′). Using the eigenvalue equations at vertex s in Ġ and Ġ′,
we get
0 =
(
λ1(Ġ
′)− λ1(Ġ)
)
xs =
∑
i : is∈E(Ġ′)
σĠ′(is)xi −
∑
i : is∈E(Ġ)
σĠ(is)xi = αxr, (2.1)
598 Ars Math. Contemp. 22 (2022) #P4.05 / 595–608
where α depends on (r, s)-entries in AĠ and AĠ′ , but it is always non-zero; for example,
if rs /∈ E(Ġ) ∧ rs ∈ E+(Ġ′) then α = σĠ′(rs) = 1, and similarly for the remaining
possibilities listed in the statement formulation. Together with (2.1), this leads to xr = 0,
which in turn contradicts the initial assumption and we are done.
Let r, s, t, u be fixed vertices of a signed graph. A relocation Rot(r, s, t) (called a
rotation) is realised in the adjacency matrix by replacing the entries ars, asr with the entries
art, atr, and vice versa. In simple words, this relocation is realised by taking the object
(which can be a positive edge, or a negative edge, or a non-edge) located between r and s
and the object located between r and t and then inserting the first object between r and t
and the second object between r and s.
A relocation Shift(r, s, t, u) (called a shifting) is realised in the adjacency matrix by
replacing the entries ars, asr with atu, aut, and vice versa.
Lemma 2.4 (Rotation and shifting). Let x = (x1, x2, . . . , xn)⊺ be an eigenvector asso-
ciated with the index of a signed graph Ġ and let r, s, t, u be fixed vertices of Ġ.
(i) Let Ġ′ be obtained from Ġ by the relocation Rot(r, s, t). If
(
xr
(
xs−xt) > 0∨ (xs =
xt ∧ xr ̸= 0)
)
∧
(
(rs is a non-edge ∧ rt is a positive edge) ∨ (rs is a negative edge
and rt is a positive edge) ∨ (rs is a negative edge and rt is a non-edge)
)
then
λ1(Ġ
′) > λ1(Ġ).
(ii) Let Ġ′ be obtained from Ġ by the relocation Shift(r, s, t, u). If
(
xtxu > xrxs ∨
(xtxu = xrxs ∧ at least one of xr, xs, xt, xu is non-zero)
)
∧
(
(rs is a positive edge
∧ tu is a non-edge) ∨ (rs is a positive edge and tu is a negative edge) ∨ (rs is a
non-edge and tu is a negative edge)
)
then λ1(Ġ′) > λ1(Ġ).
Proof. This proof is similar to the proof of the previous lemma. If rs and rt are as in (i),
then we compute
λ1(Ġ
′)− λ1(Ġ) ≥ x⊺(AĠ′ −AĠ)x = 2αxr(xs − xt),
where α = 1 for the first and the third assumption on rs and rt, and α = 2 for the second
assumption. Now, for xr(xs − xt) > 0 we get λ1(Ġ′) > λ1(Ġ). For xs = xt we have
λ1(Ġ
′) ≥ λ1(Ġ). In case of equality, we have that x is afforded by λ1(Ġ′). Considering
the eigenvalue equation at the vertex s in Ġ and Ġ′ , we get xr = 0, which completes (i).
If rs and rt are as in (ii), then we compute
λ1(Ġ
′)− λ1(Ġ) ≥ x⊺(AĠ′ −AĠ)x = 2α(xtxu − xrxs),
with α ∈ {1, 2}, as before. We are done for xtxu > xrxs, while for xtxu = xrxs, using
the previous reasoning we get that the equality between the indices necessarily leads to the
conclusion that x takes zero at the corresponding four vertices.
3 Ordering signed graphs by the index
We start our considerations with an example.
Example 3.1. Clearly, there are just 3 connected signed graphs of order 3, up to switching:
the positive triangle (with index 2), the 3-vertex path (with index
√
2) and the negative
M. Brunetti and Z. Stanić: Ordering signed graphs with large index 599
triangle (with index 1). We know from [11] that there are exactly 12 connected signed
graphs of order 4 (again, up to switching). Their indices are computed directly, and the
corresponding ordering is given in Figure 1.
2. 2.56161. 3.0000 3. 2.2361 4. 2.1701 7. 1.7321 8. 1.6181 9. 1.5616 10. 1.4812 11. 1.4142 12. 1.00005-6. 2.0000
Figure 1: Connected signed graphs with 4 vertices ordered by the index. Here and in the
subsequent graphical representations, signed graphs are depicted according to the conven-
tion explained in Section 2.
In what follows, we determine the first 5 connected signed graphs with n vertices or-
dered by the index, for every n ≥ 5. In other words, we determine the signed graphs
Ġ1 − Ġ5 of the sequence S defined in the previous section. First, Ġ1 is the complete
signed graph with the all positive signature, which follows from the well-known Perron-
Frobenius Theorem and Lemma 2.1. We now prove the following theorem, crucial for our
considerations.
Theorem 3.2. Let S ′ = (Ġk+1, Ġk+2, . . . , Ġk+ℓ) be a subsequence of S such that
λ1(Ġk) > λ1(Ġk+1) = λ1(Ġk+2) = · · · = λ1(Ġk+ℓ) > λ1(Ġk+ℓ+1). (3.1)
Then, for every Ġ ∈ S ′, we have Ġ ∈ R(Ḣ) where Ḣ ∈ {Ġ1, Ġ2, . . . , Ġk+ℓ} \ Ġ.
In addition:
(a) For at least one Ġ ∈ S ′ we have Ḣ ∈ {Ġ1, Ġ2, . . . , Ġk};
(b) If Ḣ /∈ {Ġ1, Ġ2, . . . , Ġk} then a non-negative λ1-eigenvector for Ġ has at least two
zero coordinates and the same eigenvector is afforded by λ1(Ḣ).
Proof. Assume by way of contradiction that for some Ġ ∈ S ′, Ġ /∈ R(Ḣ), for every Ḣ
that belongs to the set given in the statement formulation. Let x = (x1, x2, . . . , xn)⊺ be an
eigenvector with non-negative coordinates afforded by the index of Ġ.
Assume that at least one of xr, xs is non-zero for some vertices r, s of Ġ. If rs is not
a positive edge, then Lemma 2.3(i) produces a signed graph Ġ′ that differs from Ġ only
in the positive edge rs, along with λ1(Ġ′) > λ1(Ġ). Since Ġ /∈
⋃k
i=1 R(Ġi), we have
Ġ′ /∈
⋃k
i=1[Ġi], i.e. there are at least k+1 signed graphs whose index is larger than λ1(Ġ),
which contradicts (3.1). Hence, rs is a positive edge.
Further, if xr = xs = 0, then reversing the sign of rs, or removing rs, or adding rs do
not affect the existence of the corresponding eigenvalue; indeed, it is afforded by the same
eigenvector. Thus if for any such r, s there is no positive edge between them, as before we
get Ġ′ with λ1(Ġ′) ≥ λ1(Ġ). Since Ġ /∈
⋃k
i=1 R(Ġi), we have λ1(Ġ′) = λ1(Ġ), but then
Ġ ∈
⋃ℓ
i=1 R(Ġk+i) which together with the initial assumption leads to Ġ ∈ R(Ġ), i.e. Ġ
is isomorphic to the signed graph obtained by inserting a positive edge rs. Replacing Ġ
with this signed graph we get that rs is positive.
Amalgamating the previous conclusions we get that Ġ is the complete signed graph
with the all positive signature, which together with Lemma 2.1 contradicts (3.1) (since we
assumed in (3.1) that Ġ is not Ġ1).
600 Ars Math. Contemp. 22 (2022) #P4.05 / 595–608
Consider now (a). Take an arbitrary Ġ ∈ S ′. If Ġ ∈
⋃k
i=1 R(Ġi), we are done.
Assume that Ġ /∈
⋃k
i=1 R(Ġi). If x is the previously defined eigenvector, then there
is a positive edge rs for every pair r, s such that at least one of xr, xs is non-zero, as
otherwise by inserting a positive edge between such vertices we get Ġ ∈
⋃k
i=1 R(Ġi). If
at most one coordinate of x is zero, then Ġ switches to a complete unsigned graph, which
contradicts (3.1). Therefore there exist at least 2 vertices at which x takes zero. In addition,
there is a negative edge between at least one such a pair, since otherwise Ġ has the all
positive signature and then x has no zero coordinates by the Perron-Frobenius Theorem.
If Ġ′ is obtained by switching the sign of such a negative edge, then λ1(Ġ′) = λ1(Ġ), as
otherwise we get Ġ ∈
⋃k
i=1 R(Ġi). Moreover, λ1(Ġ′) is afforded by the same eigenvector,
so we may repeat the previous consideration with Ġ′ in the role of Ġ. In this way we
necessarily arrive at some Ġ ∈ S ′ ∩
(⋃k
i=1 R(Ġi)
)
since the number of negative edges
strictly decreases in passing from Ġ to Ġ′.
It remains to consider (b). Let Ġ ∈ R(Ḣ). If at most one coordinate of x is zero,
then λ1(Ḣ) > λ1(Ġ) (by Lemma 2.3(i)), which implies Ḣ ∈ {Ġ1, Ġ2, . . . , Ġk}. Further,
the assumption that Ġ ∈ R(Ḣ) together with λ1(Ḣ) = λ1(Ġ) leads to the conclusion
that xr = xs = 0 for a non-positive (resp. positive) edge rs in Ġ (resp. Ḣ), and thus
AḢx = AĠx = λ1(Ḣ)x.
Remark 3.3. Theorem 3.2 gives a method for the ordering of signed graphs by the index.
Let Ġ1, Ġ2, . . . , Ġk be the first k signed graphs ordered by the index such that all signed
graphs (if any) sharing the index with Ġk are listed before it (so, as in the theorem). Then
the sequence is extended by the signed graph(s) belonging to
⋃k
i=1 R(Ġi). The candidates
must be connected and the λ1-eigenspace for each of them must contain an eigenvector with
non-negative coordinates. They are compared on the basis of an algebraic computation
that relies on Lemmas 2.3 and 2.4. As long as we deal with signed graphs whose λ1-
eigenspaces do not contain an eigenvector with at least two zero coordinates, there are no
other candidates. In case of such eigenvectors, signed graphs with equal indices sharing
the same eigenvector may appear.
Remark 3.4. To determine the set R(Ġ) we need to consider the entire switching class of
Ġ. For example, if Ġ is the complete signed graph with exactly one negative edge, say e,
then the signed graphs obtained from Ġ by removing a positive edge or reversing its sign
are the following 4:
By making a switch at a vertex incident with e and either removing e or reversing its sign,
we get 2 additional members of R(Ġ) that are not switching equivalent to the previous
ones. But in both cases the λ1-eigenspace does not contain a non-negative eigenvector
(the condition required in Remark 3.3). A method for computing the λ1-eigenvectors is
demonstrated in the proof of the forthcoming Lemma 3.5.
Now we proceed with the ordering.
Lemma 3.5. Ġ2 is .
M. Brunetti and Z. Stanić: Ordering signed graphs with large index 601
Proof. There are exactly two candidates for Ġ2: Ḟ obtained by removing an edge of Ġ1
and Ḣ obtained by reversing the sign of an edge of Ġ1. If the vertices joined by the unique
negative edge of Ḣ are labelled by 1 and 2, using the eigenvalue equation for λ1(Ḣ) we
get
λ1a = − a+ (n− 2)b
λ1b = 2a+ (n− 3)b
which leads to the λ1(Ḣ)-eigenvector b(λ1+1λ1+3 ,
λ1+1
λ1+3
, 1, 1, . . . , 1)⊺, b ̸= 0. By virtue of
Lemma 2.3(i) (applied to Ḣ), we have λ1(Ḟ ) > λ1(Ḣ). Hence Ġ2 ∼= Ḟ .
Lemma 3.6. Ġ3 is .
Proof. The candidates for Ġ3 are illustrated in Figure 2. They are obtained by considering
R(Ġ1)∪R(Ġ2); we also include the transposes of the corresponding positive eigenvectors
afforded by the index.
b
(
(λ1+1)(λ1−2)
λ1(λ1+2)−4
,
λ21
λ1(λ1+2)−4
,
λ21+λ1−2
λ1(λ1+2)−4
, 1, 1, . . . , 1
)
b
( (λ21−1)
λ1(λ1+2)−1
,
λ1(λ1+1)
λ1(λ1+2)−1
,
λ1(λ1+1)
λ1(λ1+2)−1
, 1, 1, . . . , 1
)
b
(
λ1+1
λ1+2
, λ1+1
λ1+2
, λ1+1
λ1+2
, λ1+1
λ1+2
, 1, 1, . . . , 1
)1
2
3
4
Ḣ2
Ḣ4 Ḣ5
b
(
λ1+1
λ1+3
, λ1+1
λ1+3
, 1, 1, . . . , 1
)
1
2
Ḣ1
b
(
λ1+1
λ1+3
, λ1+1
λ1+3
, λ1+1
λ1+2
, λ1+1
λ1+2
, 1, 1, . . . , 1
)1
2
3
4
Ḣ3
Figure 2: The candidates for Ġ3.
From Lemma 2.3(i), we have λ1(Ḣ1) > max{λ1(Ḣ2), λ1(Ḣ3)}. We further apply
Lemma 2.4(i) to Ḣ5 with (r, s, t) = (1, 2, 3) to conclude that λ1(Ḣ4) > λ1(Ḣ5). To show
that Ġ3 ∼= Ḣ1 it remains prove that λ1(Ḣ1) > λ1(Ḣ4). The adjacency matrix of Ḣ1 is
AḢ1 =
 0 −1−1 0 J⊺
J AKn−2
 ,
(where J is the all-1 matrix) which leads to the quotient matrix (i.e. the matrix of row sums
in the corresponding blocks of AḢ1 ):
QḢ1 =
(
−1 n− 2
2 n− 3
)
.
We know from [7] that every eigenvalue whose eigenspace does not contain an eigenvector
orthogonal to the all-1 vector j belongs to the spectrum of the quotient matrix. In our case,
this means that λ1(Ḣ1) is an eigenvalue of QḢ1 , i.e. λ1(Ḣ1) is the largest root of
x2 + (4− n)x− 3n+ 7. (3.2)
602 Ars Math. Contemp. 22 (2022) #P4.05 / 595–608
In the same way, we get that λ1(Ḣ4) is the largest root of
f(x) = x3 − (n− 3)x2 − (2n− 5)x+ n− 3. (3.3)
Now, computing the largest root of (3.2) we get λ1(Ḣ1) =
n+
√
(n−2)(n+6)
2 −2. Insert-
ing it in (3.3), we get f
(n+√(n−2)(n+6)
2 −2
)
=
√
(n− 2)(n+ 6)−n > 0, which leads to
the conclusion that either λ1(Ḣ1) > λ1(Ḣ4) or the two roots of f are larger than λ1(Ḣ1).
The latter is not true because f(0) > 0, f(1) < 0 which means that f has a negative root
and a root in (0, 1).
To avoid repetitive proofs, in the remainder of this section and the next two sections we
omit the parts in which we compute the λ1-eigenvectors of potential candidates since these
are technical algebraic computations performed in exactly the same way as in the previous
proof.
Lemma 3.7. Ġ4 is .
Proof. The 6 candidates for Ġ4 are (those of Figure 2 that have not passed for Ġ3 are
included, of course):
We note that there are two additional members of R(Ġ3) mentioned in Remark 3.3, but the
non-existence of a required λ1-eigenvector eliminates them.
The 3rd and the 5th candidate are eliminated since their indices are dominated by the
index of the 1st one, while the 4th and the 6th are eliminated by the 2nd one in the same
way – all this by virtue of Lemma 2.3(i). Finally, the fact that the index of the 1st signed
graph is larger than that of the 2nd one is established in the proof of Lemma 3.6, and we
are done.
Lemma 3.8. Ġ5 is .
Proof. The candidates for Ġ5 are the 5 signed graphs that are eliminated in the proof of the
previous lemma (when we considered Ġ4) and the following 8 signed graphs:
Lemma 2.3(i) eliminates all except the 2nd and the 3rd of the previous proof; in Figure 2
they are denoted by Ḣ5 and Ḣ2) and the 1st and the 3rd of the additional candidates (we
denote them by Ḟ1 and Ḟ2). By Lemma 2.4, λ1(Ḟ2) dominates λ1(Ḟ1); we already had
this in the proof of Lemma 3.6.
Thus, it remains to prove that λ1(Ḣ5) > max{λ1(Ḣ2), λ1(Ḟ2)}. As in the proof of
Lemma 3.6 we deduce that these indices are the largest roots of characteristic polynomials
of the corresponding quotient matrices. These polynomials are:
h5(x) = x
2 − (n− 3)x− 2(n+ 3)
h2(x) = x
4 − (n− 4)x3 − (3n− 7)x2 + 2(n− 4)x+ 4(n− 3)
f2(x) = x
3 − (n− 3)x2 − 2(n− 3)x+ 2(n− 4)
M. Brunetti and Z. Stanić: Ordering signed graphs with large index 603
The largest root of h5 is 12 (n − 3 +
√
(n− 3)(n+ 5)). Concerning h2 we get h2(−4) =
12(n + 11) > 0, h2(−2) = −4(n − 4) < 0, h2(0) = 4(n − 3) > 0 and h2(n − 2) =
−(n − 1)(n − 4)2 < 0, which together with n − 2 < λ1(Ḣ5) leads to the conclusion
that at least 3 roots of h2 are less than λ1(Ḣ5). Since h2(λ1(Ḣ5)) = (n − 4)(n − 3 +√
(n− 3)(n+ 5)) > 0, we conclude that the fourth root of h2 is also less than λ1(Ḣ5).
Similarly, we have f2(−3) = −n − 26 < 0, f2(0) = 2(n − 4) > 0 and f2(1) =
2−n < 0, which means that that two roots of f2 are less than λ1(Ḣ5), while f2(λ1(Ḣ5)) =
2(n− 4) > 0 confirms the same for the third root, and we are done.
Amalgamating the previous results we arrive at the following theorem.
Theorem 3.9. The first 5 connected signed graphs with n ≥ 5 vertices ordered by their
indices are:
Ġ1 Ġ2 Ġ3 Ġ4 Ġ5
4 Unbalanced signed graphs
Let now (U̇1, U̇2, . . . , U̇u) be the subsequence of S (defined in Section 2) containing only
unbalanced signed graphs. In other words, the previous sequence ignores the balanced
ones. In what follows, we determine U̇1 − U̇4 for n ≥ 6.
We know from [6] that U̇1 is obtained by reversing the sign of a single edge in the
complete graph of order n.
Lemma 4.1. U̇2 is .
Proof. The candidates for U̇2 are the last 4 signed graphs considered as the candidates in
the proof of Lemma 3.7. (As before, it is not complicated to show that these are the only
candidates with positive λ1-eigenvectors).
The latter two candidates are eliminated by Lemma 2.3(i) – they are dominated by the
1st candidate. Observe that the λ1-eigenvector for the 2nd candidate is given in Figure 2.
Using the same vertex labelling and applying the relocation Rot(3, 4, 1) we arrive at the
result formulated in this statement.
Lemma 4.2. U̇3 is .
Proof. The candidates for U̇3 are the following 14 signed graphs:
2
1 3
4
1
2
3
J̇1 J̇2 J̇3 J̇4
604 Ars Math. Contemp. 22 (2022) #P4.05 / 595–608
All in the second row are easily eliminated on the basis of Lemma 2.3(i). The two in the
third row are eliminated by Lemma 2.4(i). Namely, if we denote the vertices in the rep-
resenting path by 1, 2, 3, 4 (in the natural order) and if x2 ≥ x3, then Rot(1, 2, 3) implies
that the index of the signed graph under consideration is less than that of J̇3. Otherwise,
we can apply Rot(4, 3, 2) with the same result.
It remains to consider the indices of J̇1−J̇4. We first show that λ1(J̇2) > max{λ1(J̇3),
λ1(J̇4)}. As in the proof of Lemma 3.5 we can show that J̇3 and J̇4 have a positive λ1-
eigenvector. (Namely, we compute b
( (λ1+1)(λ1−3)
λ1(λ1+2)−5 ,
(λ21+λ1−2)
λ1(λ1+2)−5 ,
(λ21+λ1−2)
λ1(λ1+2)−5 ,
λ21+1
λ1(λ1+2)−5 ,
1, 1, . . . , 1
)⊺
for J̇3 which is positive for every b > 0, as λ1 > 3 when n ≥ 6. Similarly,
we get b
( (λ1+1)2
λ1(λ1+4)+1
, λ1(λ1+1)λ1(λ1+4)+1 ,
λ1(λ1+1)
λ1(λ1+4)+1
, 1, 1, . . . , 1
)⊺
for J̇4, which is positive for
b > 0, as well.) Set J̇∗ ∈ {J̇3, J̇4}, and let x be a positive eigenvector afforded by λ1(J̇∗).
Observe that J̇2 is obtained by inserting a positive edge 12 and a negative edge 13 in J̇∗.
Therefore, we have
λ1(J̇2)− λ1(J̇∗) ≥ x⊺(AJ̇2 −AJ̇∗)x = 2(x1x2 − x1x3) = 0,
where the last equality follows since x2 = x3 (by the symmetry in J̇∗). Hence, λ1(J̇2) ≥
λ1(J̇∗). If λ1(J̇2) = λ1(J̇∗), then x is afforded by λ1(J̇2), but this is impossible since the
eigenvalue equation at the vertex 2 cannot hold in J̇2 and J̇∗.
Characteristic polynomials of quotient matrices of J̇1 and J̇2 are:
j1(x) = x
3 − (n− 6)x2 − (5n− 17)x− 6n+ 20
j2(x) = x
3 − (n− 3)x2 − (2n− 3)x+ 7n− 23
We compute j(x) = j1(x)− j2(x) = 3x2 − (3n− 14)x− 13n+43, with roots: x1, x2 =
1
6 (3n − 14 ±
√
9n(8 + n)− 320). It follows that j1(x) < j2(x) for x ∈ (x1, x2). For
the larger root x2 we have j1(x2) = j2(x2) = 127
(
(3n− 16)
√
9n(8 + n)− 320 + 9n2 −
96n+248
)
> 0 where the inequality follows since 9n2 − 96n+248 > 0 for n ≥ 7, while
for n = 6 it is confirmed directly. Taking into account that x1 is negative (the easiest way
to see this is to compute j(0)), we conclude that λ1(J̇1), λ1(J̇2) ∈ (x1, x2). Together with
j1(x) < j2(x) on the same interval, this leads to λ1(J̇1) > λ1(J̇2).
Lemma 4.3. U̇4 is .
Proof. Besides the 13 signed graphs listed in the previous lemma, we have other 4 candi-
dates for U̇4 (that arise from U̇3 but not from U̇1 or U̇2):
The former two are eliminated by Lemma 2.3(i), the latter two by Lemma 2.4(i). Therefore,
it remains to consider J̇2 − J̇4, but they have been already considered in the proof of the
previous lemma, when we proved that λ1(J̇2) > max{λ1(J̇3), λ1(J̇4)}, as desired.
The previous results lead to the following theorem.
Theorem 4.4. The first 4 connected unbalanced signed graphs with n ≥ 6 vertices ordered
by their indices are:
M. Brunetti and Z. Stanić: Ordering signed graphs with large index 605
U̇1 U̇2 U̇3 U̇4
5 Complete signed graphs
As before, let (Ċ1, Ċ1, . . . , Ċc) be the subsequence of S containing complete signed graphs.
Clearly, the complete signed graph with the largest index switches to the one with the all
positive signature. The next one contains exactly one negative edge. There are 2 candidates
for Ċ3, both with 2 negative edges. By Lemma 2.4(i), Ċ3 is the one in which negative edges
are adjacent.
In what follows we set n ≥ 10.
Lemma 5.1. Ċ4 is .
Proof. The candidates are:
L̇1 L̇2 L̇3
2
1
3
4
The latter two are eliminated by Lemma 2.4(i). By inserting the largest eigenvalue of the
quotient matrix QL̇3 into the characteristic polynomial ℓ2, we get
ℓ2
(
1
2 (n− 6 +
√
n(n+ 8)− 32)
)
= 2(−n− 4 +
√
n(n+ 8)− 32) < 0
as n(n + 8) − 32 < (n − 4)2. The latter inequality implies that the largest root of ℓ2 is
larger than the largest eigenvalue of QL̇3 , i.e. λ1(L̇2) > λ1(L̇3).
If the vertices of L̇2 are labelled as above then the λ1-eigenvector has the form
b = b
( (λ1 + 1)(λ1 − 5)
λ1(λ1 + 2)− 11
,
λ21 + 1
λ1(λ1 + 2)− 11
,
λ21 + 1
λ1(λ1 + 2)− 11
, 1, 1, . . . , 1
)⊺
,
for b > 0. Now, L̇1 is obtained by reversing the sign of edges 12, 13 and 23, and thus we
have
λ1(L̇1)− λ1(L̇2) ≥ b⊺(AL̇1 −AL̇2)b
=
4(λ21 + 1)b
2
λ1(λ1 + 2)− 11
(2(λ1 + 1)(λ1 − 5)
λ1(λ1 + 2)− 11
− λ
2
1 + 1
λ1(λ1 + 2)− 11
)
=
4(λ21 + 1)b
2
λ1(λ1 + 2)− 11
· λ
2
1 − 8λ1 − 9
λ1(λ1 + 2)− 11
> 0 for λ1 > 9.
We compute λ1(L̇2) > 9 for n = 11, and then by eigenvalue interlacing we have the same
inequality for n ≥ 12. For n = 10, the inequality λ1(L̇1) > λ1(L̇2) is confirmed directly,
and we are done.
Lemma 5.2. Ċ5 is .
606 Ars Math. Contemp. 22 (2022) #P4.05 / 595–608
Proof. Apart from the signed graphs faced in the proof of the previous lemma, there is
exactly one additional candidate: it contains exactly 3 non-adjacent negative edges. This
candidate is eliminated on the basis of Lemma 2.4(i), while the remaining ones are already
considered in the previous proof. In particular, we know that λ1(L̇2) > λ1(L̇3), and the
proof is completed.
Lemma 5.3. Ċ6 is .
Proof. The only critical case is the comparison of the indices of L̇3 and the signed graph,
say L̇, containing 4 negative edges that share the same vertex. Computing the λ1-eigenvector
for L̇ and following the proof of Lemma 5.1, we get λ1(L̇3) > λ1(L̇) for λ21−12λ1−13 >
0, i.e. for λ1 = λ1(L̇) > 13. This proves this lemma for n ≥ 15 (as there λ1(L̇) > 13).
The case 10 ≤ n ≤ 14 is considered directly, and we are done.
We arrive at the following result.
Theorem 5.4. The first 6 complete signed graphs with n ≥ 10 vertices ordered by their
indices are:
Ċ1 Ċ2 Ċ3 Ċ4 Ċ5 Ċ6
Remark 5.5. With a slight modification in which a full line represents a positive edge and
an unpictured line represents a non-edge, the result of Theorem 5.4 remains valid for the
ordering of unsigned graphs by the index of the Seidel matrix. Indeed, the Seidel matrix of
an unsigned graph G coincides with the adjacency matrix of the complete signed graph in
which negative edges are induced by the edges of G.
6 Further computations
We complete the results of Sections 4 and 5 by determining the 6 signed graphs with largest
indices for every order that is not covered by Theorem 4.4 and the 7 signed graphs with
largest indices for every order that is not covered by Theorem 5.4.
There is exactly one connected unbalanced signed graph with 3 vertices (the unbalanced
triangle), while the ordering for n ∈ {4, 5} is given in the first part of Figure 3. We note
that there are exactly 6 connected unbalanced signed graphs for n = 4, so in this case the
given list is complete.
There are exactly 3 complete signed graphs with 4 vertices and their ordering does not
deviate from the general case considered in Theorem 5.4. For 5 ≤ n ≤ 9 the one with the
largest index switches to the signed graph with all positive signature, while the remaining
6 are given in the second part of Figure 3. Again, for n = 5 the list is complete.
In this paper our idea was to give a general method for the ordering by the index and to
demonstrate its use by determining the lists of the first few signed graphs as reported in the
previous sections. Of course, these results can be extended, but the theoretical approach
is becoming more complicated as the number of candidates increases and comparison of
their indices requires more sophisticated methods. However, it occurs that the list of Theo-
rem 3.9 continues with:
M. Brunetti and Z. Stanić: Ordering signed graphs with large index 607
Ġ6 Ġ7 Ġ8
n = 4
unbalanced
n = 5
unbalanced
n = 5
complete
n = 6
complete
n = 7
complete
n = 8
complete
n = 9
complete
2. 2.00001. 2.2361 3. 1.5616 4. 1.4812 5. 1.4142 6. 1.0000
2. 3.10281. 3.3723 5. 2.9173 6. 2.77843-4. 3.0000
3. 3.00002. 3.3723 4. 2.5616 5. 2.3723 6. 2.2361 7. 1.0000
3. 4.06422. 4.4641 4. 3.8284 5. 3.6056 6. 3.4940 7. 3.3871
3. 5.15542. 5.5311 6. 4.7720 7. 4.68424-5. 5.0000
3. 6.23612. 6.5826 4. 6.1231 5. 6.0283 6. 5.8990 7. 5.8284
3. 7.30392. 7.6235 4. 7.2170 5. 7.0813 6-7. 7.0000
Figure 3: Orderings of small signed graphs that are uncovered by Theorem 4.4 or Theo-
rem 5.4.
608 Ars Math. Contemp. 22 (2022) #P4.05 / 595–608
We skip the details and note that the proof relies on an intensive algebraic computation that
basically does not deviate from those of the previous sections.
ORCID iDs
Maurizio Brunetti https://orcid.org/0000-0002-2742-1919
Zoran Stanić https://orcid.org/0000-0002-4949-4203
References
[1] S. Akbari, F. Belardo, F. Heydari, M. Maghasedi and M. Souri, On the largest eigenvalue of
signed unicyclic graphs, Linear Algebra Appl. 581 (2019), 145–162, doi:10.1016/j.laa.2019.
06.016.
[2] S. Akbari, S. Dalvandi, F. Heydari and M. Maghasedi, Signed complete graphs with maximum
index, Discuss. Math. Graph Theory 40 (2020), 393–403, doi:10.7151/dmgt.2276.
[3] F. Belardo, M. Brunetti and A. Ciampella, Signed bicyclic graphs minimizing the least Lapla-
cian eigenvalue, Linear Algebra Appl. 557 (2018), 201–233, doi:10.1016/j.laa.2018.07.026.
[4] F. Belardo, M. Brunetti and A. Ciampella, Unbalanced unicyclic and bicyclic graphs with
extremal spectral radius, Czechoslovak Math. J. 71(146) (2021), 417–433, doi:10.21136/cmj.
2020.0403-19.
[5] F. Belardo and Y. Zhou, Signed graphs with extremal least Laplacian eigenvalue, Linear Alge-
bra Appl. 497 (2016), 167–180, doi:10.1016/j.laa.2016.02.028.
[6] M. Brunetti and Z. Stanić, Unbalanced signed graphs with extremal spectral radius or index,
Comput. Appl. Math. 41 (2022), Paper No. 118, 13, doi:10.1007/s40314-022-01814-5.
[7] D. M. Cvetković, The main part of the spectrum, divisors and switching of graphs, Publ. Inst.
Math. (Beograd) (N.S.) 23(37) (1978), 31–38, http://eudml.org/doc/257490.
[8] C. He, Y. Li, H. Shan and W. Wang, On the index of unbalanced signed bicyclic graphs, Com-
put. Appl. Math. 40 (2021), Paper No. 124, 14, doi:10.1007/s40314-021-01498-3.
[9] T. Koledin and Z. Stanić, Connected signed graphs of fixed order, size, and number of negative
edges with maximal index, Linear Multilinear Algebra 65 (2017), 2187–2198, doi:10.1080/
03081087.2016.1265480.
[10] M. Souri, F. Heydari and M. Maghasedi, Maximizing the largest eigenvalues of signed
unicyclic graphs, Discrete Math. Algorithms Appl. 12 (2020), 2050016, 8, doi:10.1142/
s1793830920500160.
[11] Z. Stanić, Signed graphs of small order, {www.matf.bg.ac.rs/˜zstanic/siggr.
htm}.
[12] Z. Stanić, Inequalities for Graph Eigenvalues, volume 423 of London Mathematical So-
ciety Lecture Note Series, Cambridge University Press, Cambridge, 2015, doi:10.1017/
cbo9781316341308.
[13] Z. Stanić, Perturbations in a signed graph and its index, Discuss. Math. Graph Theory 38
(2018), 841–852, doi:10.7151/dmgt.2035.
[14] Z. Stanić, Integral regular net-balanced signed graphs with vertex degree at most four, Ars
Math. Contemp. 17 (2019), 103–114, doi:10.26493/1855-3974.1740.803.
[15] T. Zaslavsky, Matrices in the theory of signed simple graphs, in: Advances in Discrete
Mathematics and Applications: Mysore, 2008, Ramanujan Math. Soc., Mysore, volume 13
of Ramanujan Math. Soc. Lect. Notes Ser., pp. 207–229, 2010, http://people.math.
binghamton.edu/zaslav/Tpapers/index.html.