American Journal of Combinatorics Research Note

Volume 2 (2023), Pages 72–78

Rank of signed cacti

Zoran Stanić
(Communicated by Bahattin Yildiz)

Abstract
A signed cactus Ġ is a connected signed graph such that every edge belongs to at
most one cycle. The rank of Ġ is the rank of its adjacency matrix. In this paper we
prove that
Xk Xk
ni − 2k ≤ rank(Ġ) ≤ ni − 2t + 2s,
i=1 i=1

where k is the number of cycles in Ġ, n1 , n2 , . . . , nk are their lengths, t is the number
of cycles whose rank is their order minus two, and s is the number of edges outside
cycles. Signed cacti attaining the lower bound are determined.

1 Introduction
A signed graph Ġ is a finite, undirected graph without loops or parallel edges, in which every
edge has been declared positive or negative. The adjacency matrix AĠ is an n × n matrix
whose (i, j)-entry is 1 if the vertices i and j are joined by a positive edge, −1 if they are
joined by a negative edge, and 0 if they are non-adjacent. The order n of Ġ is the number
of vertices of Ġ. The rank rank(Ġ) of Ġ is the rank of AĠ .
A signed cactus (also known as a tree-like signed graph) Ġ is a connected signed graph
such that every pair of induced cycles (if any) has at most one common vertex; equivalently,
every edge of Ġ belongs to at most one cycle.
Inspired by the result of Chen and Tian [2] that offers a lower bound for the rank of the
skew adjacency matrix of an oriented cactus, in this contribution we prove a similar lower
bound for the rank of a signed cactus, along with an upper bound. Signed cacti attaining
the lower bound are determined, as well. Our results can be seen in the light of recently
established links between the spectrum of an oriented graph and the skew spectrum of a
related signed graph (with a precise meaning of ‘related’) [5]. According to these links, there
MSC 2020: 05C50, 05C22; Keywords: Adjacency matrix, Tree-like signed graph, Rank, Cycle

©
Received Sep 14, 2023; Revised Oct 10, 2023; Accepted Oct 13, 2023; Published Oct 14, 2023
The author(s). Released under the CC BY 4.0 International License

72
 Stanić/ American Journal of Combinatorics 2 (2023) 72–78

is a strong relationship between the theory of skew spectra of oriented graphs and the theory
of spectra of signed graphs, and therefore the similarity between the lower bound of [2] and
the lower bound obtained in this paper is unsurprising.
In the next section we go straight to the results.

2 Results
All the necessary terminology and notation are given in this paragraph. We write I, O and 0
to denote the identity matrix, the all-zero matrix and the all-zero vector, respectively. For a
vertex v of a signed graph Ġ, Ġ − v denotes the induced subgraph obtained by removing v.
Similarly, if Ḣ is an induced subgraph of Ġ, then Ġ − Ḣ denotes the induced subgraph
obtained by removing the vertices of Ḣ. In this spirit, Ḣ + v is an induced subgraph whose
vertex set is the union of the vertex set of Ḣ and a single vertex v. A cut-vertex of a
connected signed graph is a vertex whose removal results in a disconnected signed graph. A
pendant vertex is a vertex of degree one. A cycle in Ġ is even (resp. odd ) if its order is even
(odd). A cycle is positive if the product of its edge signs is 1. Otherwise, it is negative.
Some known results are needed.
Lemma 2.1 (cf. [1, Theorem 3]). For a vertex v of a signed graph Ġ, rank(Ġ − v) ≤
rank(Ġ) ≤ rank(Ġ − v) + 2.
The next results reveals a situation in which the previous upper bound is attained.
Lemma 2.2 ([3]). Let v be a cut-vertex of a connected signed graph Ġ and Ḣ a disjoint union
of some connected components of Ġ − v. If rank(Ḣ + v) = rank(Ḣ) + 2, then rank(Ġ) =
rank(Ġ − v) + 2.
We include a sketched proof, while for details we refer the reader to [3]. If Ḣ includes all
the components of Ġ − v, there is nothing to prove. Otherwise, we write
 
AḢ x O
AĠ =  x| 0 y|  , (2.1)
O y AĠ−v−Ḣ
and observe that, under the assumption of the lemma, x is not in the range 
(i.e.,the
 column

ci x
space) of AḢ and a basis of the 2 × 2 top-left block of AĠ is spanned by , and
  0 0
0
, where {ci } is the basis of the column space of AḢ . Then
1
 
0 O
rank(Ġ) = rank(Ḣ) + 1 + rank  1 y|  = rank(Ḣ) + 2 + rank(Ġ − v − Ḣ),
0 AĠ−v−Ḣ

which gives the desired assertion, as Ġ − v is a disjoint union of Ḣ and Ġ − v − Ḣ, with
rank(Ġ − v) = rank(Ḣ) + rank(Ġ − v − Ḣ).
We proceed with the following lemma.

73
 Stanić/ American Journal of Combinatorics 2 (2023) 72–78

Lemma 2.3. Let v be a cut-vertex of a connected signed graph Ġ and Ḣ a disjoint union
of some connected components of Ġ − v. If rank(Ḣ + v) = rank(Ḣ), then rank(Ġ) =
rank(Ḣ) + rank(Ġ − Ḣ).

Proof. The result follows directly if Ḣ includes all the components of Ġ − v, i.e., Ḣ ∼
= Ġ − v.
Otherwise, if rank(Ḣ + v) = rank(Ḣ), then the vector x of (2.1) belongs to the range of AḢ ,
giving AḢ z = x, for z 6= 0. In addition, x| z = 0, as otherwise yields rank(Ḣ) < rank(Ḣ +v).
With consistent submatrix sizes, this gives the following rank preserving transformation
of AĠ :
 |  
I −z O I −z O
0| 1 0|  · AĠ · 0| 1 0|  =
O 0 I O 0 I
     
I 0 O AḢ x O I −z O AḢ 0 O
−z| 1 0|   x| 0 y|  0| 1 0|  =  0| 0 y|  ,
O 0 I O y AĠ−v−Ḣ O 0 I O y AĠ−v−Ḣ

which leads to the desired assertion.

A similar proof technique can be found in [2]. We continue with the following theorem,
a crucial ingredient for the proof of the forthcoming Theorem 2.6.

Theorem 2.4. Let v be a cut-vertex of a connected signed graph Ġ and Ḣ a disjoint union
of some connected components of Ġ − v. The following statements hold true.

(i) If rank(Ḣ + v) = rank(Ḣ) + 2, then rank(Ḣ) + rank(Ġ − Ḣ) ≤ rank(Ġ) ≤ rank(Ḣ) +

rank(Ġ − Ḣ) + 2.

(ii) If rank(Ḣ +v) = rank(Ḣ)+1, then rank(Ḣ)+rank(Ġ− Ḣ)−1 ≤ rank(Ġ) ≤ rank(Ḣ)+

rank(Ġ − Ḣ) + 1.

Proof. As in the previous proof, the case Ḣ ∼ = Ġ − v is resolved directly. We assume that
Ḣ ∼
6= Ġ − v, and write Ḟ for the signed graph obtained by removing the vertex v from Ġ − Ḣ.
Since Ġ − v is a disjoint union of Ḣ and Ḟ , we have

rank(Ġ − v) = rank(Ḣ) + rank(Ḟ ). (2.2)

Due to Lemma 2.1, we have

rank(Ḟ ) ≤ rank(Ġ − Ḣ) ≤ rank(Ḟ ) + 2. (2.3)

(i): For rank(Ḣ +v) = rank(Ḣ)+2, Lemma 2.2 in conjunction with (2.2) yields rank(Ġ) =
rank(Ḣ) + rank(Ḟ ) + 2. Employing (2.3), we obtain rank(Ḣ) + rank(Ġ − Ḣ) ≤ rank(Ġ) ≤
rank(Ḣ) + rank(Ġ − Ḣ) + 2, as desired.
(ii): We assume that rank(Ḣ + v) = rank(Ḣ) + 1 and consider the three possibilities for
rank(Ġ − Ḣ).

74
 Stanić/ American Journal of Combinatorics 2 (2023) 72–78

First, if rank(Ġ − Ḣ) = rank(Ḟ ) + 2, by substituting Ḟ for Ḣ in Lemma 2.2, we obtain

rank(Ġ) = rank(Ġ − v) + 2 = rank(Ḟ ) + rank(Ḣ) + 2, where the latter equality follows
from (2.2). This gives
rank(Ġ) = rank(Ḣ) + rank(Ġ − Ḣ). (2.4)
Let rank(Ġ − Ḣ) = rank(Ḟ ) + 1. From Lemma 2.1 and (2.2), we obtain rank(Ḣ) +
rank(Ḟ ) ≤ rank(Ġ) ≤ rank(Ḣ) + rank(Ḟ ) + 2, which together with the previous equality
leads to

rank(Ḣ) + rank(Ġ − Ḣ) − 1 ≤ rank(Ġ) ≤ rank(Ḣ) + rank(Ġ − Ḣ) + 1. (2.5)

Finally, assume that rank(Ġ − Ḣ) = rank(Ḟ ). By substituting Ḟ for Ḣ in Lemma 2.3, we
arrive at rank(Ġ) = rank(Ḣ + v) + rank(Ḟ ) = rank(Ḣ) + rank(Ḟ ) + 1, where the second
equality follows from the assumption of item (ii) of this statement. It follows

rank(Ġ) = rank(Ḣ) + rank(Ġ − Ḣ) + 1. (2.6)

The desired inequalities follow by taking into account (2.4)–(2.6).

The next result is needed, as well. It can be proved directly, but we also provide some
references.

Lemma 2.5 ([3, 4]). The following statements hold true.

(i) For a signed path Ṗn of order n,


n if n is even,
rank(Ṗn ) =
n − 1 if n is odd.

(ii) For a signed cycle Ċn of order n,

if either n ∼

 n−2 = 0 (mod 4) and Ċn is positive or
rank(Ċn ) = ∼
n = 2 (mod 4) and Ċn is negative,
n otherwise.


Here is the main result of this paper.

Theorem 2.6. Let Ġ be a signed cactus with k cycles of lengths n1 , n2 , . . . , nk , such that
exactly t of them are even and positive (resp. negative) if their order is (is not) divisible by 4.
Assume that exactly s edges do not belong to any cycle. Then
k
X k
X
ni − 2k ≤ rank(Ġ) ≤ ni − 2t + 2s.
i=1 i=1

75
 Stanić/ American Journal of Combinatorics 2 (2023) 72–78

Proof. For k = 0, the lower bound reduces to 0, and the upper bound reduces to 2(n − 1),
where n is the order of Ġ, and so both inequalities hold. Let k ≥ 1.
We first consider the lower bound. Observe that the existence of pendant vertices leaves
the bound unchanged and may increase the rank, and thus we assume that Ġ has no pendant
vertices. For k = 1, the result follows from Lemma 2.5(ii). We proceed by the induction
argument, i.e., we assume that the statement holds for every signed cactus with k − 1 cycles,
and consider Ġ having k (k ≥ 2) cycles. Let Ċnk be a cycle with exactly one vertex, say
v, of degree ≥ 3. Clearly, such a cycle exists under the assumption that Ġ has no pendant
vertices.
If rank(Ċnk ) = nk − 2, then by Lemma 2.5(i) we have rank(Ċnk − v) = nk − 2, as Ċnk − v
is a path of an odd order. From Lemma 2.3 with Ċnk − v in the role of Ḣ, we obtain
rank(Ġ) = rank(Ċnk − v) + rank(Ġ − Ċnk + v), which under the induction hypothesis leads
to rank(Ġ) ≥ nk − 2 + k−1
P Pk
i=1 n i − 2(k − 1) = i=1 ni − 2k.
In the light of Lemma 2.5(i), rank(Ċnk ) = nk implies

nk − 2 if nk is even,
rank(Ċnk − v) =
nk − 1 if nk is odd.
For nk even, Theorem 2.4(i) leads to rank(Ġ) ≥ rank(Ċnk − v) + rank(Ġ − Ċnk + v) =
nk − 2 + rank(Ġ − Ċnk + v). After employing the induction hypothesis, we arrive at the
desired inequality.
For nk odd, Theorem 2.4(ii) leads to rank(Ġ) ≥ rank(Ċnk − v) + rank(Ġ − Ċnk + v) − 1 =
nk − 2 + rank(Ġ − Ċnk + v), and the result follows.
Consider now the upper bound. For k = 1, the result follows from Lemma 2.5(ii) and
Lemma 2.1. Indeed, the rank of the unique cycle is given in the former lemma, and the latter
one tells us that adding a pendant vertex increases the rank by at most 2. We proceed as in
the previous case and assume that Ġ has k (k ≥ 2) cycles, along with the hypothesis that
the statement holds for every signed cactus with k − 1 cycles. Suppose first that Ġ has a
cycle, say Ċnk , with exactly one vertex, say again v, of degree ≥ 3.
If rank(Ċnk ) = nk − 2 (which occurs exactly if Ċnk is one of the t cycles given in the
statement formulation), then by virtue of Lemma 2.3, we obtain rank(Ġ) = rank(Ċnk − v) +
Pk−1
rank(Ġ− Ċnk +v), and then Lemma 2.5(i) yields rank(Ġ) ≤ nk −2+ i=1 ni −2(t−1)+2s =
Pk
i=1 ni − 2t + 2s.
If rank(Ċnk ) = nk , the desired inequality is obtained by a slight modification of the proof
for the lower bound; the only difference is that now we use the upper bounds of Theorem 2.4.
If Ċnk has trees attached at its vertices, which contain r edges in total, then rank(Ġ) ≤
Pk
i=1 ni − 2t + 2(s − r) + 2r, as follows by multiple application of Lemma 2.5 to the vertices
of trees. The latter inequality concludes the entire proof.
We reformulate the previous result to the following corollary suggested by the referee.
Corollary 2.7. Let Ġ be a signed cactus of Theorem 2.6. Then

m − s − 2k ≤ rank(Ġ) ≤ m − 2t + s,

where m is the number of edges of Ġ.

76
 Stanić/ American Journal of Combinatorics 2 (2023) 72–78

Figure 1: Examples of signed cacti attaining the upper bound of Theorem 2.6. In these
examples, all edges are positive.

Pk
This result, of course, follows from m = i=1 ni + s. Consider now the equality in the
lower bound of Theorem 2.6.

Theorem 2.8. The lower bound of Theorem 2.6 is attained if and only if either Ġ is an
isolated vertex or each of its edges belongs to a cycle, and every cycle is even and positive
(resp. negative) if its order is (is not) divisible by 4.

Proof. Assume first that Ġ is as in the statement formulation. If it consists of a single

vertex, then the bound is obviously attained. In the remaining case, we again proceed with
the induction. For k = 1, Ġ is an even cycle and the result follows from Lemma 2.5(ii). If
Ċnk is a cycle with exactly one vertex, say v, of degree ≥ 3, then rank(Ċnk ) = rank(Ċnk − v)
(by Lemma 2.5), and the result follows by employing Lemma 2.3 (with Ċnk − v in the role
of Ḣ) and the induction hypothesis.
Assume now that the equality is attained. We first eliminate te possibility that Ġ contains
an odd cycle. If Ċn1 is such a cycle, then we have rank(Ċn1 ) = n1 . We proceed to build Ġ by a
successive addition of pendant vertices or cycles. Adding a vertex does not decrease the rank,
and adding the entire cycle of length q increases it by at leastPq−2, as follows by Theorem 2.4.
Therefore, the rank of Ġ is at least n1 + ki=2 ni −2(k−1) = ki=1 ni −2(k−1) > ki=1 ni −2k.
P P
The remainder of the proof follows from Theorem 2.6(i) of [5] which states that the rank
of a bipartite signed graph equals the rank of an associated oriented graph (with a precise
meaning of ‘associated’) and Theorem 1.2 of [2] stating that the corresponding lower bound
for oriented graphs is attained if and only if they are associated with signed graphs given in
the formulation of this statement.
Observe that the upper bound of Theorem 2.6 may be trivial in the sense that is larger
than the order of Ġ. For t = 0, since every vertex belonging to a cycle in Ġ is counted at
least once in the sum of the upper bound, and every vertex not belonging to any cycle is
incident with at least one edge not belonging to cycles, we obtain that the upper bound is
not less than the order of Ġ, and Ġ attains the bound if and only if it is an isolated vertex

77
 Stanić/ American Journal of Combinatorics 2 (2023) 72–78

or a signed cycle; since t = 0, this cycle has restrictions according to the theorem. For t ≥ 1,
we got a rather complicated situation, and the question of equality remains a challenging
problem. Our experiments show that, for example, two infinite families of signed graphs
illustrated in Fig. 1 attain the bound. The same holds if we remove pendant vertices form
the first one. Further examples are constructed by changing lengths of cycles with a caveat
that their rank must remain unchanged. This in particular means that the triangle of the
first example can be replaced by a negative cycle of length 4k + 2 (k ≥ 1).

Acknowledgments
I am very grateful to the anonymous referee for her/his helpful comments that improved the
quality of the manuscript.
The research is 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.

References
[1] Jean H. Bevis, Kevin K. Blount, George J. Davis, Gayla S. Domke, and Valerie A. Miller,
The rank of a graph after vertex addition, Linear Algebra Appl. 265 (1997) 55–69.

[2] Li Chen and Fenglei Tian, Skew-rank of an oriented graph with edge-disjoint cycles,
Linear Multilinear Algebra 64 (2016) 1197–1206.

[3] Yu Liu and Lihua You, Further results on the nullity of signed graphs, J. Appl. Math.
2014, article ID 483735.

[4] Slobodan K. Simić and Zoran Stanić, Polynomial reconstruction of signed graphs, Linear
Algebr Appl. 501 (2016) 390–408.

[5] Zoran Stanić, Relations between the skew spectrum of an oriented graph and the spectrum
of an associated signed graph, Linear Algebra Appl. 676 (2023) 241–250.

Contact Information
Zoran Stanić Faculty of Mathematics, University of Belgrade
[email protected] Studentski trg 16, 11 000 Belgrade, Serbia

78