TY - JOUR
T1 - The rank of a signed graph in terms of the rank of its underlying graph
AU - Lu, Yong
AU - Wang, Ligong
AU - Zhou, Qiannan
N1 - Publisher Copyright:
© 2017 Elsevier Inc.
PY - 2018/2/1
Y1 - 2018/2/1
N2 - Let Γ=(G,σ) be a signed graph and A(Γ) be its adjacency matrix, where G is the underlying graph of Γ. The rank r(Γ) of Γ is the rank of A(Γ). We know that for a signed graph Γ=(G,σ), Γ is balanced if and only if Γ=(G,σ)∼(G,+). That is, when Γ is balanced, then r(Γ)=r(G), where r(G) is the rank of the underlying graph G of Γ. A natural problem is that: how about the relations between the rank of an unbalanced signed graph and the rank of its underlying graph? In this paper, we first prove that r(G)−2d(G)≤r(Γ)≤r(G)+2d(G) for an unbalanced signed graph with d(G)≥1, where d(G)=|E(G)|−|V(G)|+ω(G) is the dimension of cycle spaces of G, ω(G) is the number of connected components of G. As an application, we also prove that 1−d(G)<[Formula presented]≤1+d(G) for an unbalanced signed graph with d(G)≥1. All corresponding extremal graphs are characterized.
AB - Let Γ=(G,σ) be a signed graph and A(Γ) be its adjacency matrix, where G is the underlying graph of Γ. The rank r(Γ) of Γ is the rank of A(Γ). We know that for a signed graph Γ=(G,σ), Γ is balanced if and only if Γ=(G,σ)∼(G,+). That is, when Γ is balanced, then r(Γ)=r(G), where r(G) is the rank of the underlying graph G of Γ. A natural problem is that: how about the relations between the rank of an unbalanced signed graph and the rank of its underlying graph? In this paper, we first prove that r(G)−2d(G)≤r(Γ)≤r(G)+2d(G) for an unbalanced signed graph with d(G)≥1, where d(G)=|E(G)|−|V(G)|+ω(G) is the dimension of cycle spaces of G, ω(G) is the number of connected components of G. As an application, we also prove that 1−d(G)<[Formula presented]≤1+d(G) for an unbalanced signed graph with d(G)≥1. All corresponding extremal graphs are characterized.
KW - Dimension of cycle space
KW - Rank of graphs
KW - Signed graphs
UR - http://www.scopus.com/inward/record.url?scp=85032002746&partnerID=8YFLogxK
U2 - 10.1016/j.laa.2017.10.013
DO - 10.1016/j.laa.2017.10.013
M3 - 文章
AN - SCOPUS:85032002746
SN - 0024-3795
VL - 538
SP - 166
EP - 186
JO - Linear Algebra and Its Applications
JF - Linear Algebra and Its Applications
ER -