ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 23 (2023) #P1.02
https://doi.org/10.26493/1855-3974.2842.6b5
(Also available at http://amc-journal.eu)
Total graph of a signed graph
Francesco Belardo
Department of Mathematics and Applications, University of Naples Federico II,
I-80126 Naples, Italy
Zoran Stanić *
Faculty of Mathematics, University of Belgrade, Studentski trg 16,
11 000 Belgrade, Serbia
Thomas Zaslavsky
Department of Mathematical Sciences, Binghamton University, Binghamton, NY
13902-6000, United States
Received 10 March 2022, accepted 24 March 2022, published online 8 September 2022
Abstract
The total graph is built by joining the graph to its line graph by means of the incidences.
We introduce a similar construction for signed graphs. Under two similar definitions of the
line signed graph, we define the corresponding total signed graph and we show that it is
stable under switching. We consider balance, the frustration index and frustration number,
and the largest eigenvalue. In the regular case we compute the spectrum of the adjacency
matrix of the total graph and the spectra of certain compositions, and we determine some
with exactly two main eigenvalues.
Keywords: Bidirected graph, signed line graph, signed total graph, graph eigenvalues, regular signed
graph, Cartesian product graph.
Math. Subj. Class. (2020): 05C22, 05C50, 05C76.
*Corresponding author. The research is partially supported by the Science Fund of the Republic of Serbia;
grant number 7749676: Spectrally Constrained Signed Graphs with Applications in Coding Theory and Control
Theory – SCSG-ctct.
E-mail addresses: fbelardo@unina.it (Francesco Belardo), zstanic@matf.bg.ac.rs (Zoran Stanić),
zaslav@math.binghamton.edu (Thomas Zaslavsky)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
2 Ars Math. Contemp. 23 (2023) #P1.02
1 Introduction
We define the total graph of a signed graph in a way that extends to signed graphs the
spectral theory of ordinary total graphs of graphs. The usual total graph is built by joining
the graph to its line graph by means of its vertex-edge incidences; this construction coordi-
nates well with the adjacency matrix. When we consider signed graphs, there is a similar
definition which extends the notion of line graph of a signed graph and which coordinates
combinatorial and matrix constructions. Working from two similar definitions of the line
signed graph we define the corresponding total graphs, and we show they are stable under
switching. We examine fundamental properties of the signed total graph including bal-
ance, the degree of imbalance as measured by the frustration index and frustration number,
and the largest eigenvalue. In the regular case we compute the spectrum of the adjacency
matrix and the spectra of certain compositions and determine some with exactly two main
eigenvalues.
A signed graph Σ is a pair (G, σ) = Gσ , where G = (V,E) is an ordinary (unsigned)
graph, called the underlying graph, and σ : E −→ {−1,+1} is the sign function (the
signature). The edge set of a signed graph is composed of subsets of positive and negative
edges. We interpret an unsigned graph G as the all-positive signed graph (G,+) = +G,
whose signature gives +1 to all the edges. Similarly, by (G,−) = −G we denote a graph G
with the all-negative signature. In general, we have −Σ = (G,−σ).
Many familiar notions about unsigned graphs extend directly to signed graphs. For
example, the degree d(v) of a vertex v in Gσ is simply its degree in G. On the other hand,
there also are notions exclusive to signed graphs, most importantly the sign of a cycle,
namely the product of its edge signs. A signed graph or its subgraph is called balanced if
every cycle in it, if any, is positive. Oppositely, Σ is antibalanced if −Σ is balanced, i.e.,
every odd (resp., even) cycle of Σ is negative (resp., positive), e.g., if Σ = −G. Balance
is a fundamental concept of signed graphs and measuring how far a signed graph deviates
from it is valuable information. The frustration index l (resp., the frustration number ν) of
a signed graph is the minimum number of edges (resp., vertices) whose removal results in a
balanced signed graph. These numbers generalize the edge biparticity and vertex biparticity
of a graph G, which equal l(−G) and ν(−G), respectively.
Also important is the operation of switching. If U is a set of vertices of Σ, the switched
signed graph ΣU (in which the vertices in U are switched) is obtained from Σ by reversing
the signs of the edges in the cut [U, V \ U ]. The signed graphs Σ and ΣU are said to be
switching equivalent, written Σ ∼ ΣU , and the same is said for their signatures. Notably,
a signed graph is balanced if and only if it is switching equivalent to the all-positive signa-
ture [15] and it is antibalanced if and only if it switches to the all-negative signature. For
basic notions and notation on signed graphs not given here we refer the reader to [15, 18].
The adjacency matrix AΣ of Σ = Gσ is obtained from the standard (0, 1)-adjacency
matrix of G by reversing the sign of all 1’s which correspond to negative edges. The
eigenvalues of Σ are identified to be the eigenvalues of AΣ; they form the spectrum of Σ.
The Laplacian matrix of Σ is defined by LΣ = DG−AΣ, where DG is the diagonal matrix
of vertex degrees of G. Analogously, the Laplacian eigenvalues of Σ are the eigenvalues
of LΣ.
It is well known that the signed graphs Σ = Gσ and Σ′ = Gσ′ are switching equivalent
if and only if there exists a diagonal matrix S of ±1’s, called the switching matrix, such that
AΣ′ = S
−1AΣS, and we say that the corresponding matrices are switching similar. More
generally, the signed graphs Σ and Σ′ are switching isomorphic if there exist a permutation
F. Belardo et al.: Total graph of a signed graph 3
matrix P and a switching matrix S such that AΣ′ = (PS)−1AΣ(PS); in fact, PS can be
seen as a signed permutation matrix (or a {1, 0,−1}-monomial matrix).
The frustration index and the frustration number are among the most investigated in-
variants – for more details one can consult [18]. Similarly, the largest eigenvalue of the
adjacency matrix is the most investigated spectral invariant of graphs. Evidently, switch-
ing preserves the eigenvalues of AΣ and LΣ, and it also preserves the signs of cycles, so
that switching equivalent signed graphs share the same set of positive (and negative) cy-
cles and have the same frustration index and frustration number. For the above reasons,
when we consider a signed graph Σ perspective, we are considering its switching isomor-
phism class [Σ], and we focus our attention to the properties of Σ which are invariant under
switching isomorphism.
Here is the remainder of the paper. In Section 2 we discuss the concept of line graph
of a signed graph. The total graph is presented in Section 3. In Section 4 we consider
regular underlying graphs and, similarly to what is known for unsigned graphs [6], we give
the eigenvalues of a total graph of a signed graph by means of the eigenvalues of its root
signed graph.
We stress that a line (total) graph of a signed graph is always signed, so “line (total)
graph” of Σ means the same as “signed line (total) graph” of Σ. For brevity we also call
these graphs “line (total) signed graphs” and “signed line (total) graphs” (although literally
the latter can mean any signature on an unsigned line or total graph; indeed an entirely
different signed total graph has been defined by Sinha and Garg [10]).
2 Line graph(s)
The line graph is a well-known concept in graph theory: given a graph G = (V (G), E(G)),
the line graph L(G) has E(G) as vertex set, and two vertices of L(G) are adjacent if and
only if the corresponding edges are adjacent in G. If we consider signed graphs Σ = Gσ ,
then a (signed) line graph L(Gσ) should have L(G) as its underlying graph. However, what
signature should we associate to it? The answer to this question is a matter of discussion
because it is possible to have several very different signatures. In this section we shall
consider the two relevant ones defined in the literature.
2.1 Definitions of a line graph
Zaslavsky gave the first definition of incidence matrix of signed graphs [15], which is a
necessary step in a spectrally consistent definition of a line graph. For a signed graph
Σ = Gσ , we introduce the vertex-edge orientation η : V (G) × E(G) −→ {1, 0,−1}
formed by obeying the following rules:
(O1) η(i, jk) = 0 if i /∈ {j, k};
(O2) η(i, ij) = 1 or η(i, ij) = −1;
(O3) η(i, ij)η(j, ij) = −σ(ij).
(The minus sign in (O3) is necessary for several purposes, such as with signed-graph ori-
entations [14, 17] and geometry [17].) The incidence matrix Bη = (ηij) is a vertex-edge
incidence matrix derived from Gσ , such that its (i, e)-entry is equal to η(i, e). However, it
is not uniquely determined by Σ alone. As in the definition of the oriented incidence matrix
for unsigned graphs, one can randomly choose an entry η(i, ij) to be either +1 or −1, but
4 Ars Math. Contemp. 23 (2023) #P1.02
the entry η(j, ij) is then determined by σ(ij), so η is called an orientation of Gσ (and a
biorientation of G, the unsigned underlying graph). Zaslavsky later interpreted Bη as the
incidence matrix of an oriented signed graph [17] and recognized that the same was an
alternate definition of bidirected graphs as in [7]. From a signed graph Σ we get many
bidirected graphs Ση , but each of them leads back to the same signed graph Σ.
Let A⊺ denote the transpose of the matrix A. The incidence matrix has an important
role in spectral theory. The Laplacian matrix can be derived as the row-by-row product of
the matrix Bη with itself:
BηB
⊺
η = LΣ.
Notably, regardless of the orientation η chosen, we get the same LΣ. It is well known that
the column-by-column product of Bη with itself is a matrix sharing the nonzero eigenvalues
with the row-by-row product. This was one motive for Zaslavsky [16, 18] to define the line
graph of a signed graph as the signed graph LC(Σ) = (L(G), σC) whose signature σC is
determined by the adjacency matrix is ALC(Σ) defined here:
ALC(Σ) = 2I −B⊺ηBη. (2.1)
Unlike in the case of the Laplacian matrix of Σ, the matrix ALC(Σ) does depend on the
orientation η. On the other hand, choosing a different orientation η′ of Σ leads to a matrix
A(L(G),σ′) that is switching similar to A(LC(G),σ) (cf. [18]). Hence, A(L(G),σ) defines
a line graph up to switching similarity, so it can be used for spectral purposes. One of
the benefits of this definition is that the line graph of a signed graph with an all-negative
signature is a line graph with an all-negative signature. In other words, if −G is a graph G
whose edges are taken negatively, we get
LC(−G) = −L(G).
The above fact has two evident consequences. The first one is that the iteration of the
(Zaslavsky) line graph operator always gives a signed graph with all-negative signature,
namely L(k)C (−G) = −L(k)(G). The second one is that if we map simple unsigned graphs
to the theory of signed graphs as signed graphs with the all-negative signature (instead
of the all-positive, as stated in the introduction), then Zaslavsky’s line graph is a direct
generalization of the usual line graph defined for unsigned graphs. We shall call this line
graph the combinatorial line graph of Σ.
However, from a spectral viewpoint, the fact that the matrix ALC(Σ) has spectrum in
the real interval (−∞, 2], is in contrast with the usual concept of spectral graph theory for
which a line graph has spectrum in the real interval [−2,+∞]. Hence, the authors of [3]
decided to modify Zaslavsky’s definition to
A(LS(G),σ) = B
⊺
ηBη − 2I. (2.2)
In fact, the two definitions are virtually equivalent, as LC(Σ) = −LS(Σ). Moreover,
they can be used for different purposes. The latter definition is tailored for those spectral
investigations in which an unsigned graph is considered as a signed one with all-positive
signature. Clearly, in this case its adjacency (and Laplacian) matrix remains unchanged and
the spectral theory of unsigned graphs can easily be encapsulated into the spectral theory
of signed graphs. For example, in this case LS(Σ) is coherent with the usual Laplacian and
signless Laplacian spectral theories of unsigned graphs, and it can be used to investigate
F. Belardo et al.: Total graph of a signed graph 5
their spectra (cf. [2]). For these reasons, we shall call LS(Σ) the spectral line graph. We
note that Hoffmann’s theory of generalized line graphs [9] fits well with both signatures.
In Figure 1 we illustrate an example of a signed graph Σ, an orientation Ση , and the
consequent line graph LC(Σ). Here and later, positive edges are represented by solid lines
and negative edges are represented by dotted lines.
t
t
t
t t
t
t
t
t t
t
t
t
t
t
qqqqq
qqqqq
q q q q q q q q q q q q q q q q q q q
q q q q q q qqqqq
qqqqq
✲✲
✻
✻
✲ ✲
✻
❄
✲✛
−→ −→
v1 v2 v5
v4 v3
e1
e2e4
e3
e5 e4 e1
e5
e3 e2
Σ Ση LC(Σ)
Figure 1: A signed graph, an orientation and the combinatorial line graph.
The matrix definitions of line graphs have combinatorial analogs; in fact, Zaslavsky’s
original definition of the line graph of a signed graph (even prior to [16]) was combinatorial.
For Σ = Gσ the underlying graph of L∗(Σ) is the line graph L(G), while the sign of the
edge ef (e, f being the edges of Σ with a common vertex v) is
σ(ef) =
{
−η(ve)η(vf) for ∗ = C,
η(ve)η(vf) for ∗ = S. (2.3)
Indeed, we may orient the line graph by defining ηL(e, ef) = η(v, e) for two edges e, f
with common vertex v in Σ [18]. Then the combinatorial definition of line graph signs
follows the rule (O3).
Remark 2.1. Which is the best definition of a line graph of a signed graph? Zaslavsky
prefers the one defined in (2.1) because it is consistent with the basic relationship between
signs and orientation stated in (O3). Belardo and Stanić instead prefer (2.2) because it
is the one coherent with existing spectral graph theory and it is more prominent in the
literature. This led to a long discussion among the three authors of this manuscript and the
late Slobodan Simić. In the end, we recognize the validity of each definition, since either
variant can be used and, after all, they are easily equivalent.
Remark 2.2. The identities (2.1) and (2.2) remain valid even if Σ contains multiple edges.
A pair of edges located between the same pair of vertices form a digon, i.e., a 2-vertex
cycle, which is positive if and only if the edges share the same sign. Here the matrix defi-
nition diverges from the combinatorial definition. In the combinatorial definition, a digon
in Σ with edges e and f gives rise to a digon in the line graph having the same sign as the
original digon; aside from signs, this is as in the unsigned line graph. In the matrix defini-
tions of L∗(Σ) it gives rise to a pair of non-adjacent vertices if the corresponding digon is
negative and a pair joined by two parallel edges of the same sign if the corresponding digon
is positive; this is consistent with the fact that a negative digon in Σ disappears in the adja-
cency matrix AΣ. Zaslavsky calls this kind of line graph, where parallel edges of opposite
sign cancel each other, reduced. Therefore, an unreduced line graph has no multiple edges
if and only if Σ has no digons, and a reduced line graph has no multiple edges if and only
if Σ has no positive digons.
6 Ars Math. Contemp. 23 (2023) #P1.02
2.2 Properties of line graphs
Here are some observations that follow directly from (2.1) and (2.2). All triangles that arise
from a star of Σ are negative (resp., positive) in LC(Σ) (resp., LS(Σ)). Every cycle of Σ
keeps its signature in LC(Σ). Every even cycle of Σ keeps its signature in LS(Σ) and every
odd cycle of Σ reverses its signature in LS(Σ).
Theorem 2.3. Let G be an unsigned graph. Then −LC(−G) and LS(−G) are balanced
signed graphs, and therefore switching equivalent to +L(G).
First Proof. Recall that a balanced graph has no negative cycles. If we consider the line
graph L(G), we distinguish three types of cycle:
(i) those that arise from the cycles of G,
(ii) those that arise from induced stars in G (forming cliques),
(iii) those obtained by combining the types (i) and (ii).
Let us consider −LC(−G) and LS(−G). We have to prove that LC(−G) is antibalanced,
or equivalently that LS(−G) is balanced. In LS(Σ) the signed cycles of type (i), originat-
ing from cycles Ck of Σ, get the sign (−1)kσ(Ck). Hence, they are all transformed into
positive cycles of LS(Σ) if and only if Σ ∼ −G. Consider next the cycles of type (ii). The
cliques (Kt, σ) of LS(Σ), originating from an induced K1,t of G, are switching equivalent
to +Kt. To see the latter, without loss of generality one can choose the biorientation of
K1,t for which the vertex-edge incidence at the center of the star is positive (the arrows are
inward directed), so the obtained clique is indeed +Kt. These cycles are always positive,
regardless of the signature of Σ. Finally, for the cycles of type (iii), we know from [13]
that the signs of a set of cycles that span the cycle space determine all the signs. Hence,
the cycles of type (iii) are positive if and only if the cycles of type (i) are positive, that is,
Σ = −G.
Second Proof. Choose the orientation for −G in which η(v, e) = +1 for every incident
vertex and edge. Then LC(−G) is easily seen to be all negative by the combinatorial
definition (2.3) of edge signs, thus LC(−G) = −L(G), which is antibalanced. Then,
LS(−G) = −LC(−G) = +L(G), which is balanced. Choosing a different orientation for
−G has the effect of switching both line graphs, so it does not change the state of balance
or antibalance.
We conclude this section by analysing balance and the degree of imbalance of line
graphs. Because LS(Σ) = −LC(Σ), balance of the combinatorial line graph LC(Σ) is
equivalent to antibalance of the spectral line graph LS(Σ), and balance of the latter is
equivalent to antibalance of the former.
Theorem 2.4. Let Σ = Gσ be a signed graph of order n and size m. The following hold
true:
(i) LC(Σ) is balanced (and LS(Σ) is antibalanced) if and only if Σ is a disjoint union
of paths and positive cycles.
(ii) LS(Σ) is balanced (and LC(Σ) is antibalanced) if and only if Σ is antibalanced.
F. Belardo et al.: Total graph of a signed graph 7
(iii) l(LS(Σ)) ≥ ν(LS(Σ)) = l(−Σ).
(iv) l(LC(Σ)) ≥
∑
v∈V (Σ)
⌊ (d(v)−1)2
4
⌋
.
Proof. (i): Balance of LC(Σ) means that Σ does not contain a vertex of degree 3 or greater,
as the corresponding edges produce negative triangles. Evidently, Σ cannot contain nega-
tive cycles, because this leads to negative cycles in LC(Σ). If Σ is a disjoint union of paths
and positive cycles, then LC(Σ) is again a disjoint union of paths and positive cycles.
(ii): A line graph L(G) has three kinds of cycle. A vertex triangle corresponds to three
edges incident with a single vertex of G; all vertex triangles are negative in LC(Σ). A
line cycle is derived from a cycle C in G and has the same sign in LC(Σ). The remaining
cycles are obtained by concatenation of cycles of the first two kinds. It follows that LC(Σ)
is antibalanced if and only if every line cycle is antibalanced, thus if and only if Σ is
antibalanced.
(iii): An edge set A in −Σ is a set A of vertices in LS(Σ); and LS(Σ)\A = LS(Σ\A).
By (ii), LS(Σ) \ A is balanced if and only if −Σ \ A is balanced. Thus, the smallest size
of an edge set A such that −Σ \A is balanced, which is l(−Σ), equals the smallest size of
a vertex set A such that LS(Σ \A) is balanced, which is ν(LS(Σ)).
The inequality follows from the general observation that l ≥ ν for every signed graph.
(iv): A vertex of degree d(v) in Σ generates in LC(Σ) an antibalanced vertex clique
−Kd(v). An edge set B in the line graph such that LC(Σ) \ B is balanced must contain
enough edges to make each such clique balanced; this number is l(−Kd(v)) =
⌊ (d(v)−1)2
4
⌋
,
obtained by dividing the vertices of Kd(v) into two nearly equal sets and deleting the edges
within each set. Each edge of the line graph is in only one vertex clique, so the minimum
number of edges required to balance every vertex clique is the sum of these quantities. That
proves the inequality.
We do not expect equality in part (iv) because deleting the edges as in the proof may
not eliminate all negative cycles in LC(Σ). The problem of finding an exact formula for
l(LC(Σ)) or l(LS(Σ)) in terms of Σ, or even a good lower bound that involves the signs
of Σ, seems difficult.
3 Total graph(s)
Recall (say, from [6, page 64]) that, for a given graph G, the total graph T (G) is the graph
obtained by combining the adjacency matrix of a graph with the adjacency matrix of its
line graph and its vertex-edge incidence matrix. Precisely, the adjacency matrix of T (G)
is given by
AT (G) =
(
AG B
B⊺ AL(G)
)
,
where L(G) denotes the line graph of G and B is the (unoriented) incidence matrix. Is it
possible to have an analogous concept for signed graphs?
We will give a positive answer to the latter question. However, since we have multiple
possibilities for line graphs of signed graphs, we build multiple total graphs.
8 Ars Math. Contemp. 23 (2023) #P1.02
3.1 Definitions of a total graph
Definition 3.1. The total graph of Σ = Gσ is the signed graph determined by
AT∗(Σ) =
(
AΣ Bη
B⊺η AL∗(Ση)
)
, (3.1)
where ∗ ∈ {C, S}.
In other words, in the combinatorial view, T∗(Σ) consists of two induced subgraphs, Σ
and L∗(Ση), along with edges joining a vertex v of Σ to all vertices of L∗(Ση) that arise
from the edges which are incident with v in Σ. The signature on these connecting edges
is given by η, i.e., for a root-graph vertex v and an incident line-graph vertex e, σT (ve) =
η(v, e). Note that this does not specify an orientation of the edge ve. One may adopt the
convention that ηT (v, ve) = +1, or any other convention, according to convenience. We
do not need to do that because we have not defined an incidence matrix for T∗(Σ).
To fix the notation, TC(Σ) and TS(Σ) denote the total graphs defined by the combina-
torial line graph (2.1) and the spectral line graph (2.2). Accordingly, we shall call them
respectively the combinatorial total graph and the spectral total graph. If we want to con-
sider both variants, we shall write T∗(Σ) instead. We need to show that our definition,
regardless of Σ ∈ [Σ] and of its chosen orientation η, gives rise to the same signed graph
up to switching equivalence.
In Figure 2 we illustrate an example of a total graph of a signed graph. The root graph
and the orientation are taken from Figure 1.
s
s s
s
s
s s
s s s
♣♣♣♣♣
♣♣♣♣♣
♣♣♣♣♣
♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣
♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣♣♣♣♣
♣♣♣♣♣
♣ ♣ ♣ ♣ ♣ ♣♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣❆❆❆
❆
✁
✁
✁
✁


❅
❅
❍❍
❍❍
✟✟
✟✟


❍❍❍❍
✁
✁
✁
✁
✟✟✟✟
v1 v2
v3v4
v5
e1
e2e4
e3
e5
TC(Σ)
s
s s
s
s
s s
s s s
♣♣♣♣♣
♣♣♣♣♣
♣♣♣♣♣
♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣
♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣♣♣♣♣
♣♣♣♣♣
♣♣♣♣♣♣
♣♣♣♣♣♣ ♣ ♣ ♣ ♣ ♣
❅
❅✏✏
✏✏
✏✏
❆
❆
❆
❆
✁
✁
✁
✁
❍❍
❍❍
✟✟
✟✟
❍❍❍❍
✁
✁
✁
✁
✟✟✟✟
v1 v2
v3v4
v5
e1
e2e4
e3
e5
TS(Σ)
Figure 2: The combinatorial and the spectral total graphs resulting from Ση depicted in
Figure 1.
We show that our definitions of a total graph are stable under reorientation and switch-
ing. For reorientation we have the first lemma.
Lemma 3.2. Let Σ = Gσ be a signed graph, and Ση and Ση′ two orientations of Σ. Then
T∗(Ση) and T∗(Ση′) are switching equivalent, for each ∗ ∈ {C, S}.
Proof. For the sake of readability, we will restrict the discussion to the combinatorial line
graph defined by Zaslavsky. Hence, hereafter L(Σ) := LC(Σ) and T (Ση) := TC(Ση).
Let G = (V,E), where |V | = n and |E| = m. Suppose that η and η′ differ on
some set F ⊆ E, and let Bη and Bη′ be the corresponding vertex-edge incidence matrices,
respectively. Let S = (sij) be the m × m diagonal matrix such that sii = −1 if ei ∈ F
F. Belardo et al.: Total graph of a signed graph 9
and sii = 1, otherwise. Then Bη′ = BηS. Since S = S⊺ = S−1, in view of (2.1), we have
AL(Ση′ ) = 2I −B
⊺
η′Bη′ = S
⊺(2I −B⊺ηBη)S = S⊺AL(Ση)S.
Therefore,
AT (Ση′ ) =
(
AΣ Bη′
B⊺η′ AL(Ση′ )
)
=
(
AΣ BηS
S⊺B⊺η S
⊺AL(Ση)S
)
=
(
I O
O S⊺
)(
AΣ Bη
B⊺η AL(Ση)
)(
I O
O S
)
=
(
I O
O S
)−1
AT (Ση)
(
I O
O S
)
.
This completes the proof.
Next, we prove that switching equivalent signed graphs produce switching equivalent
total graphs.
Lemma 3.3. If Σ and Σ′ are switching equivalent, then T∗(Σ) and T∗(Σ′) are switching
equivalent as well, for each ∗ ∈ {C, S}.
Proof. The notation is the same as in Lemma 3.2. Since Σ and Σ′ are switching equivalent,
their adjacency matrices are switching similar. Hence, AΣ = S−1AΣ′S for some switching
matrix S. Observe that if B = Bη is a vertex-edge incidence matrix of Σ, then B′ = SBη
is a vertex-edge incidence matrix of Σ′. Additionally, in view of (2.1), we have AL(Σ) =
2I −B⊺B.
Therefore, (for Σ′) we have
AT (Σ′) =
(
AΣ′ B
′
B′⊺ AL(Σ′)
)
=
(
AΣ′ B
′
B′⊺ 2I −B′⊺B′
)
=
(
S−1AΣS SB
(SB)⊺ 2I −B⊺(S⊺S)B
)
=
(
S O
O I
)−1 (
AΣ B
B⊺ AL(Σ)
)(
S O
O I
)
=
(
S O
O I
)−1
AT (Σ)
(
S O
O I
)
.
Hence, T (Σ) is switching equivalent to T (Σ′), and we are done.
In view of Lemmas 3.2 and 3.3 the definition given by (3.1) can be used for spectral
investigations.
Remark 3.4. A careful reader has probably noticed that the switching matrix in Lemma 3.2
is the one realizing switching equivalence between the line graphs, while the switching
matrix in Lemma 3.3 is the one realizing switching equivalence between the root signed
graphs. In general, if we have two switching equivalent total graphs, then the switching
matrix will be obtained by combining the switching matrices of the corresponding root and
line graphs.
10 Ars Math. Contemp. 23 (2023) #P1.02
Remark 3.5. The spectral total graph TS(·) does not generalize the total graph of an un-
signed graph, because with the TS operator the total graph of an all-positive signed graph
does not have an all-positive signature, as the convention of treating unsigned graphs as
all positive and the definition of the unsigned total graph would imply. On the other
hand, if we consider unsigned graphs as signed graphs with the all-negative signature, then
TC(−G) = −T (G), so that TC can be considered as the generalization to signed graphs
of the unsigned total graph operator. This observation lends some support to using the line
graph operator LC in spectral graph theory and treating unsigned graphs as all negative,
though contrary to existing custom.
3.2 Properties of total graphs
Now we study some structural and spectral properties of TC(Σ) and TS(Σ). We begin by
computing the number of triangles of T∗(Σ).
Theorem 3.6. Let an unsigned graph G have order n, size m, degree sequence
(d1, d2, . . . , dn), and t triangles. Then the number of triangles of T∗(G) is 2t + m +∑n
i=1
(
di+1
3
)
.
Proof. Every triangle of T∗(G) is one of the following four types:
(a) belongs to G,
(b) belongs to L∗(G),
(c) has 1 vertex in G and 2 vertices in L∗(G),
(d) has 2 vertices in G and 1 vertex in L∗(G).
Every triangle of L∗(G) arises from a triplet of adjacent edges of G. Such a triplet ei-
ther forms a triangle or has a common vertex. Therefore, L∗(G) contains t +
∑n
i=1
(
di
3
)
triangles.
Every triangle of type (c) arises from a pair of adjacent edges of G, so their number
is
∑n
i=1
(
di
2
)
.
Every triangle of type (d) arises from an edge of G, so their number is m.
Altogether, the number of triangles is
t+ t+
n∑
i=1
(
di
3
)
+
n∑
i=1
(
di
2
)
+m = 2t+m+
n∑
i=1
(
di + 1
3
)
,
as claimed.
Moreover, we can establish which triangles are either positive or negative.
Theorem 3.7. Let Σ = Gσ be a signed graph of order n, size m, degree sequence
(d1, d2, . . . , dn), and t = t+ + t− triangles, where t+ (resp., t−) denotes the number of
positive (resp., negative) triangles. Then TC(Σ) has exactly 2t+ positive triangles, while
TS(Σ) has exactly t+m negative triangles.
Proof. The total number of triangles is computed in Theorem 3.6.
F. Belardo et al.: Total graph of a signed graph 11
We have the following facts that the reader can easily check. The triangles of type (a)
will keep their sign in the total signed graph. Hence, we have t+ positive triangles for
TC(Σ) and t− negative triangles for TS(Σ).
A positive (negative) triangle in Σ becomes a positive (negative) triangle in LC(G),
and a negative (positive) triangle in LS(G). A set of mutually adjacent edges in G will
give rise to a complete graph in L∗(G) whose signature is equivalent to the all-negative
(resp., all-positive) one for LC(Σ) (resp., LS(Σ)). Summing up, the triangles of type (b)
will be t+ positive for TC(Σ) and t+ negative for TS(Σ).
Next, let us consider a triangle of type (c). Such a triangle of T∗(Σ) is obtained from
two edges, say vu and vw, of Σ that are incident to the same vertex v. Regardless of
σ(vu) and σ(vw), we can assign an orientation such that the arrows from the side of v are
both inward (directed towards v). Hence, the edges {v, vw} and {v, uv} of T∗(Σ) will be
positive, while the edge {vu, vw} will be negative (resp., positive) in TC(Σ) (resp., TS(Σ)).
Finally, a triangle of type (d) comes from a pair of adjacent vertices u and v and the
joining edge uv. Again, regardless of σ(uv) and with a similar reasoning as above, the
resulting triangle will always be negative in T∗(Σ).
Now, the statement easily follows by counting the positive (negative) triangles of TC(Σ)
(resp., TS(Σ)).
Remark 3.8. From Theorem 3.7 we easily deduce that TC(Σ) and TS(Σ) have in general
switching inequivalent signatures which are not the opposite of each other. Hence, in con-
trast to the line graphs defined by (2.1) and (2.2), the total graphs derived from them have
unrelated signatures.
We conclude this section by analysing the degree of imbalance of these compound
graphs. A vertex cover of a graph is a set of vertices such that every edge has at least one
end in the cover. The smallest size of a vertex cover is the vertex cover number, τ .
Theorem 3.9. Let Σ = Gσ be a signed graph of order n, size m, and vertex cover num-
ber τ . The following hold true:
(i) T∗(Σ) is balanced if and only if G is totally disconnected.
(ii) T∗(Σ) is antibalanced if and only if either ∗ = S and Σ has no adjacent edges, or
∗ = C and Σ is antibalanced.
(iii) l(T∗(Σ)) ≥ m+ l(L∗(Σ)), with equality when ∗ = S, and also when ∗ = C and Σ
is a disjoint union of paths and cycles.
(iv) l(T∗(Σ)) = m if and only if either ∗ = S and Σ is antibalanced, or ∗ = C and Σ is
a disjoint union of paths and positive cycles.
(v) ν(T∗(Σ)) ≥ τ , with equality if ∗ = S and Σ is antibalanced.
(vi) ν(TS(Σ)) ≤ τ + ν(LS(Σ)).
(vii) The largest (adjacency) eigenvalue λ of T∗(Σ) satisfies
λ ≤ max
{
−di +
√
5d2i + 4(dimi − 4)
2
: 1 ≤ i ≤ n+m
}
,
where di and mi denote, respectively, the degree of a vertex i of T∗(Σ) and the
average degree of its neighbours.
12 Ars Math. Contemp. 23 (2023) #P1.02
Proof. (i): Each edge of Σ leads to a negative triangle of type (d), so T∗(Σ) is balanced if
and only if Σ has no edges.
(ii): Adjacent edges lead to a positive triangle of type (c) in TS(Σ), hence it cannot be
antibalanced. If there are no adjacent edges, TS(Σ) consists only of negative triangles of
type (d) and any isolated vertices of Σ, which is antibalanced.
There are four kinds of cycle to consider in TC(Σ): triangles of types (c) and (d) and
cycles in Σ and LC(Σ). The triangles are negative, hence antibalanced. If Σ is not an-
tibalanced, the total graph cannot be, but if Σ, thus also LC(Σ) by Theorem 2.4(ii), is
antibalanced, then it follows – from the fact that all cycles in the total graph are obtained
by combining cycles of those four kinds – that the total graph is antibalanced.
(iii): The m triangles of type (d) of the proof of Theorem 3.6 are negative and indepen-
dent, in the sense that no two of them share the same edge. Therefore, to eliminate each
of them it is necessary to delete m edges (for example, the edges of Σ in T∗(Σ)). Deleting
these edges does not change the frustration index of the subgraph L∗(Σ), so at least an
additional l(L∗(Σ)) edges must be deleted to attain balance of T∗(Σ). Hence, we have the
inequality.
Equality holds for TS(Σ) because the triangles of type (c) are positive. In TC(Σ) those
triangles are negative. When Σ is a disjoint union of paths and positive cycles, then the
negative cycles are those of type (c) and (d) which share a common edge. Deleting such
independent edges (there are m of them) leads to a balanced signed graph. When Σ has a
negative cycle, one edge in those triangles can be replaced by one edge each in the negative
cycle in Σ and in the corresponding negative cycle in LC(Σ) for a total of one extra edge
for each negative cycle of Σ.
(iv): The equality for TS(Σ) holds under the formulated conditions since there LS(Σ)
is balanced and then the entire TS(Σ) becomes balanced after deleting all m edges of Σ.
For TC(Σ) the result follows from (iii).
Conversely, if l(T∗(Σ)) = m, then L∗(Σ) must be balanced, i.e., it cannot contain a
negative cycle. For ∗ = S, this means that Σ is antibalanced. For ∗ = C, this means that Σ
does not contain a vertex of degree 3 or greater, as the corresponding edges produce nega-
tive triangles. Evidently, Σ cannot contain negative cycles, because this leads to additional
negative cycles in TC(Σ). If Σ is a disjoint union of paths and positive cycles, the equality
follows from (iii).
(v): Consider T∗(Σ). For both variants we need to eliminate (at least) the negative
triangles of type (d). Instead of deleting the edges of Σ, we can just delete a minimum
vertex cover of Σ and obtain the same effect. The equality is obtained for TS(−G).
(vi): If B is a minimum set of vertices of LS(Σ) such that deleting every vertex in B
leaves a balanced line graph LS(Σ), then deleting the same vertices from the line graph in
TS(Σ) while also deleting a minimum vertex cover from Σ in LS(Σ) as in the proof of (v)
eliminates all negative cycles in the total graph.
(vii): Note that, unless G is totally disconnected, every vertex of T∗(Σ) belongs to
at least one negative triangle – this triangle is again of type (d). Accordingly, the result
follows by the inequality of [11]:
λ ≤ max
{−di +√5d2i + 4(dimi − 4t−i )
2
: 1 ≤ i ≤ n+m
}
,
where t−i stands for the number of negative triangles passing through a vertex i.
F. Belardo et al.: Total graph of a signed graph 13
Remark 3.10. It is not the case that ν(TC(Σ)) ≤ τ + ν(LC(Σ)). A counterexample is a
sufficiently long cycle of either sign, for which τ ≈ 12m, ν(LC(Σ)) ≤ 1, and ν(T∗(Σ)) ≈
2
3m ≈ 43τ > τ + 1 due to the negative triangles of types (c) and (d).
4 Total graphs of regular signed graphs
A signed graph Σ = Gσ is said to be r-regular if its underlying graph G is an r-regular
graph.
4.1 Spectrum
We infer that the spectrum of Σ lies in the real interval [−r, r]. We compute the spectrum
of T∗(Σ) by means of the eigenvalues of the root (signed) graph Σ, when it is regular.
Theorem 4.1. Let Σ be an r-regular signed graph (r ≥ 2) with n vertices and eigenvalues
λ1, λ2, . . . , λn. Then:
(i) The eigenvalues of TC(Σ) are 2 with multiplicity ( r2 − 1)n and
1
2
(
2 + 2λi − r ±
√
r2 − 4λi + 4
)
, for 1 ≤ i ≤ n.
(ii) The eigenvalues of TS(Σ) are −2 with multiplicity ( r2 − 1)n and
1
2
(
r − 2±
√
(r − 2λi)2 + 4(λi + 1)
)
, for 1 ≤ i ≤ n.
Proof. The proof is inspired from Cvetković’s proof of the theorem concerning the total
graphs of regular unsigned graphs [6, Theorem 2.19]. Due to the inconsistency between
the concepts of line graphs of unsigned graphs and that of spectral line graphs of signed
graphs, our proof differs at some points, as do the final results.
Since Σ is r-regular, for some incidence matrix B, we have BB⊺ = LΣ = DG−AΣ =
rI −AΣ, A(LC(Σ)) = 2I −B⊺B, and A(LS(Σ)) = B⊺B − 2I .
The characteristic polynomial of TC(Σ) is given by
ΦTC(Σ)(x) =
∣∣∣∣ xI −AΣ −B−B⊺ xI − LC(Σ)
∣∣∣∣
=
∣∣∣∣ xI − rI +BB⊺ −B−B⊺ xI − 2I +BB⊺
∣∣∣∣ .
Multiplying the first row of the block determinant by B⊺ and adding to the second, and
then multiplying the second by 1x−2B and adding to the first one, we get
ΦTC(Σ)(x) =
∣∣∣∣ (x− r)I +BB⊺ + 1x−2((x− r − 1)BB⊺ +BB⊺BB⊺) O(x− r − 1)B⊺ +B⊺BB⊺ (x− 2)I
∣∣∣∣ .
14 Ars Math. Contemp. 23 (2023) #P1.02
Further, we compute
ΦTC(Σ)(x) = (x− 2)
r
2n
∣∣(x− r)I +BB⊺ + 1
x− 2
(
(x− r − 1)BB⊺ +BB⊺BB⊺
)∣∣
=(x− 2) r2n
∣∣xI −AΣ + 1
x− 2
(
(x− r − 1)(rI −AΣ) + (rI −AΣ)2
)∣∣
=(x− 2)( r2−1)n
∣∣A2Σ + (3− 2x− r)AΣ + (x2 + x(r − 2)− r)I∣∣
=(x− 2)( r2−1)n
n∏
i=1
(
λ2i + (3− 2x− r)λi + (x2 + x(r − 2)− r)
)
=(x− 2)( r2−1)n
n∏
i=1
(
x2 + (r − 2− 2λi)x+ λ2i + (3− r)λi − r
)
.
Since the roots of x2 +(r− 2− 2λi)x+λ2i +(3− r)λi − r = 0 are given by 12
(
2+2λi −
r ±
√
r2 − 4λi + 4
)
, (i) follows.
Item (ii) follows similarly, by taking the spectral variant of the line graph.
From the above theorem we can deduce the real interval containing the eigenvalues of
the total graph of a regular signed graph.
Corollary 4.2. Let Σ be an r-regular signed graph with n vertices and eigenvalues λ1 ≥
λ2 ≥ · · · ≥ λn. Then:
(i) The spectrum of TC(Σ), if r ≥ 4, lies in the interval[1
2
(2 + λn − r −
√
r2 − 4λn + 4),
1
2
(2 + λ1 − r +
√
r2 − 4λ1 + 4)
]
.
(ii) The spectrum of TS(Σ), if r ≥ 2, lies in the interval[1
2
(r − 2−
√
(r − 2λn)2 + 4(λn + 1)),
1
2
(r − 2 +
√
(r − 2λn)2 + 4(λn + 1))
]
.
Proof. Consider first TC(Σ). It is routine to check that the function f1(λ) = 12 (2+λ−r+√
r2 − 4λ+ 4) is increasing for λ ∈ [−r, r] when r ≥ 4. Hence, the maximum of f1 is
attained for λ1. The function f2(λ) = 12 (2 + λ− r−
√
r2 − 4λ+ 4) is always increasing,
therefore, its minimum is achieved by λn. Hence, the entire spectrum of TC(Σ) lies in
[f2(λn), f1(λ1)], and we get (i).
Consider next TS(Σ). Analysing the function
f3(λ) =
√
(r − 2λ)2 + 4(λ+ 1) =
√
(2λ− (r − 1))2 + 2r + 3,
we find that it is decreasing for λ ≤ r−12 , increasing for λ ≥ r−12 , and symmetric around
r−1
2 . Since λ1 ≤ r and λn ≤ −1 (this holds for every signed graph by induction on the
number of edges using eigenvalue interlacing), we have r−12 −λn ≥ | r−12 −λ1|. Since our
function is symmetric around r−12 , the last inequality leads to f3(λn) ≥ f3(λ1). Hence,
1
2 (r−2+f3(λn)) is the largest eigenvalue of TS(Σ). There are two candidates for the least
eigenvalue of the same signed graph: 12 (r−2−f3(λn)) and (according to Theorem 4.1(ii))
−2. Taking into account that λn ≤ −1, we get 12 (r− 2− f3(λn)) ≤ −2, and thus the least
eigenvalue is 12 (r − 2− f3(λn)), which completes (ii).
F. Belardo et al.: Total graph of a signed graph 15
4.2 A composition
We next consider a particular composition of spectral total graphs – those whose definition
is based on the spectral line graph. Of course, similar results can be obtained in case of the
combinatorial definition. Some further definitions and notation are needed. The Cartesian
product (see also [8]) of the signed graphs Σ1 = (G1, σ1) and Σ2 = (G2, σ2) is determined
in the following way: (1) Its underlying graph is the Cartesian product G1 ×G2; we state
for the sake of completeness that its vertex set is V (G1)×V (G2), and the vertices (u1, u2)
and (v1, v2) are adjacent if and only if either u1 = v1 and u2 is adjacent to v2 in G2 or
u2 = v2 and u1 is adjacent to v1 in G1. (2) The sign function is defined by
σ((u1, u2), (v1, v2)) =
{
σ1(u1, v1) if u2 = v2,
σ2(u2, v2) if u1 = v1.
For the real multisets S1 and S2, we denote by S1 + S2 the multiset containing all
possible sums of elements of S1 and S2 (taken with their repetition). Especially, if S2
consists of the additive identity repeated i times, then the previous sum is denoted by Si1
and consists of the elements of S1, each with multiplicity increased by the factor i. Let
further Spec(Gσ) denote the spectrum of Gσ .
Inspired by [4, 5], we consider the polynomial p(Gσ) =
∑k
i=0 ciG
i
σ , where c0, c1, . . . ,
ck are non-negative integers (ck ̸= 0), Gσ is a regular signed graph with a fixed orientation,
Giσ is the ith power of Gσ with respect to the spectral total graph operation (that is, G
i
σ =
T i−1S (Gσ), i > 0, and G0σ = K1), ciGiσ denotes the disjoint union of ci copies of Giσ , and
the sum of signed graphs is their Cartesian product.
Theorem 4.3. For an r-regular signed graph Gσ (r ≥ 2) with n vertices,
Spec(p(Gσ)) =
k∑
i=0
Spec(Giσ)
ci , (4.1)
where, for i ≥ 2, Spec(Giσ) is comprised of −2 with multiplicity ( ri−12 − 1)ni−1 and
1
2
(
ri−1 − 2±
√(
ri−1 − 2λ(i−1)j
)2
+ 4
(
λ
(i−1)
j + 1
) )
, for 1 ≤ j ≤ ni−1,
where ri = 2i−1r, n1 = n , ni = n
∏i
j=2(2
j−3r+1), and with λ(i−1)1 , λ
(i−1)
2 , . . . , λ
(i−1)
ni−1
being the eigenvalues of Gi−1σ .
Proof. Since, for a non-negative integer c, Spec(cΣ) = Spec(Σ)c and Spec(Σ1 + Σ2) =
Spec(Σ1) + Spec(Σ2) (for the latter, see [8]), we arrive at (4.1), and thus it remains to
compute Spec(Σi). The case i ≤ 1 is clear; clearly, for i ≥ 2, Spec(Σi) is as in the
theorem, where ri−1 and ni−1 are the vertex degree and the number of vertices of Σi−1.
By the definition of a total graph we have ri = 2ri−1, which along with r1 = r leads
to ri = 2i−1r.
By the same definition, we also have ni = ni−1 +mi−1, where mi−1 = 12ni−1ri−1 is
the number of edges of Σi−1. So, ni = ni−1 + 12ni−1ri−1 = ni−1
(
1
4ri + 1
)
. Solving, we
get
ni = n
i∏
j=2
(1
4
ri + 1
)
= n
i∏
j=2
(
2j−3r + 1
)
,
and we are done.
16 Ars Math. Contemp. 23 (2023) #P1.02
Regarding the last theorem, for r = 0 the resulting spectrum is trivial. For r = 1,
Spec(Σ2) is computed directly, not as in the theorem.
4.3 Eulerian regular digraph
We conclude the paper by offering a result which applies only to a signed graph that is
regular and with all edges positive. Note that, by the definition, an oriented all-positive
signed graph is precisely a directed graph. An eigenvalue of a signed graph Gσ is called
main if there is an associated eigenvector not orthogonal to the all-1 vector j. An orientation
of a (signed) graph is called Eulerian if the in-degree equals the out-degree at every vertex.
Theorem 4.4. Let Σ = Gσ be an r-regular signed graph with the all-positive signature
and an Eulerian orientation η. Then TS(Ση) has exactly two main eigenvalues: r and −2.
Proof. The assumptions of positive edges and Eulerian orientation mean that the row sums
of Bη are zero. Under our assumptions, every block of (3.1) has a constant row sum given
in the following (quotient) matrix
Q =
(
r 0
0 −2
)
.
The spectrum of Q contains the main part of the spectrum of TS(Ση). (The explicit proof
can be found in [12], but the reader can also consult [6, Chapter 4] or [1].) By definition,
every signed graph has at least one main eigenvalue. If TS(Ση) has exactly one main
eigenvalue, then the eigenspace of any other is orthogonal to j, which implies that j is
associated with the unique main eigenvalue, but this is impossible (for TS(Ση), observe Q).
Therefore, both eigenvalues of Q are the main eigenvalues of TS(Ση), and we are done.
ORCID iDs
Francesco Belardo https://orcid.org/0000-0003-4253-2905
Zoran Stanić https://orcid.org/0000-0002-4949-4203
Thomas Zaslavsky https://orcid.org/0000-0003-0851-7963
References
[1] F. Atik, On equitable partition of matrices and its applications, Linear Multilinear Alge-
bra 68 (2020), 2143–2156, doi:10.1080/03081087.2019.1572708, https://doi.org/
10.1080/03081087.2019.1572708.
[2] F. Belardo, T. Pisanski and S. K. Simić, On graphs whose least eigenvalue is greater than
−2, Linear Multilinear Algebra 64 (2016), 1570–1582, doi:10.1080/03081087.2015.1107020,
https://doi.org/10.1080/03081087.2015.1107020.
[3] F. Belardo and S. K. Simić, On the Laplacian coefficients of signed graphs, Linear Algebra
Appl. 475 (2015), 94–113, doi:10.1016/j.laa.2015.02.007, https://doi.org/10.1016/
j.laa.2015.02.007.
[4] D. M. Cardoso, P. Carvalho, P. Rama, S. K. Simić and Z. Stanić, Lexicographic polyno-
mials of graphs and their spectra, Appl. Anal. Discrete Math. 11 (2017), 258–272, doi:
10.2298/aadm1702258c, https://doi.org/10.2298/aadm1702258c.
[5] D. M. Cardoso, M. A. A. De Freitas, E. A. Martins and M. Robbiano, Spectra of graphs ob-
tained by a generalization of the join graph operation, Discrete Math. 313 (2013), 733–741, doi:
10.1016/j.disc.2012.10.016, https://doi.org/10.1016/j.disc.2012.10.016.
F. Belardo et al.: Total graph of a signed graph 17
[6] D. M. Cvetković, M. Doob and H. Sachs, Spectra of graphs. Theory and applications, Leipzig:
J. A. Barth Verlag, 1995.
[7] J. Edmonds and E. L. Johnson, Matching: A well-solved class of integer linear programs, in:
Combinatorial Optimization – Eureka, You Shrink., Springer, Berlin, 2003, pp. 27–30, doi:
10.1007/3-540-36478-1_3, https://doi.org/10.1007/3-540-36478-1_3.
[8] K. A. Germina, S. Hameed K and T. Zaslavsky, On products and line graphs of signed graphs,
their eigenvalues and energy, Linear Algebra Appl. 435 (2011), 2432–2450, doi:10.1016/j.laa.
2010.10.026, https://doi.org/10.1016/j.laa.2010.10.026.
[9] A. J. Hoffman, On graphs whose least eigenvalue exceeds −1 −
√
2, Linear Algebra Appl.
16 (1977), 153–165, doi:10.1016/0024-3795(77)90027-1, https://doi.org/10.1016/
0024-3795(77)90027-1.
[10] D. Sinha and P. Garg, Balance and consistency of total signed graphs, Indian J. Math. 53 (2011),
71–81.
[11] Z. Stanić, Some bounds for the largest eigenvalue of a signed graph, Bull. Math. Soc. Sci. Math.
Roum., Nouv. Sér. 62 (2019), 183–189.
[12] Z. Stanić, Main eigenvalues of real symmetric matrices with application to signed graphs,
Czech. Math. J. 70 (2020), 1091–1102, doi:10.21136/cmj.2020.0147-19, https://doi.
org/10.21136/cmj.2020.0147-19.
[13] T. Zaslavsky, Characterizations of signed graphs, J. Graph Theory 5 (1981), 401–406, doi:
10.1002/jgt.3190050409, https://doi.org/10.1002/jgt.3190050409.
[14] T. Zaslavsky, Signed graph coloring, Discrete Math. 39 (1982), 215–228, doi:10.1016/
0012-365x(82)90144-3, https://doi.org/10.1016/0012-365x(82)90144-3.
[15] T. Zaslavsky, Signed graphs, Discrete Appl. Math. 4 (1982), 47–74, doi:10.1016/
0166-218x(82)90033-6, https://doi.org/10.1016/0166-218x(82)90033-6.
[16] T. Zaslavsky, Line graphs of switching classes, in: Report of the XVIIIth O.S.U. Denison Maths
Conference, Dept. of Math., Ohio State University, Columbus, Ohio, 1984 pp. 2–4.
[17] T. Zaslavsky, Orientation of signed graphs, Eur. J. Comb. 12 (1991), 361–375, doi:10.1016/
s0195-6698(13)80118-7, https://doi.org/10.1016/s0195-6698(13)80118-7.
[18] T. Zaslavsky, Matrices in the theory of signed simple graphs, in: Advances in Discrete Mathe-
matics and Applications: Mysore, 2008, Mysore: Ramanujan Mathematical Society, pp. 207–
229, 2010, https://arxiv.org/abs/1303.3083.