Relation between the rank of a signed graph and the rank of its underlying graph

ABSTRACT

A signed graph $\mathrm{\Gamma }\left(G\right)$ is a graph with a sign attached to each of its edges, where G is the underlying graph of $\mathrm{\Gamma }\left(G\right)$. Let $A\left(\mathrm{\Gamma }\right(G\left)\right)$ denote the adjacency matrix of $\mathrm{\Gamma }\left(G\right)$, and $A\left(G\right)$ be the adjacency matrix of G. The rank of G (resp. $\mathrm{\Gamma }\left(G\right)$), written as $r\left(G\right)$ (resp. $r\left(\mathrm{\Gamma }\right(G\left)\right)$), refers to the rank of $A\left(G\right)$ (resp. $A\left(\mathrm{\Gamma }\right(G)$)). A natural and interesting problem is: What is the relation between the rank of a signed graph and the rank of its underlying graph? In this paper, we focus our attention on this problem. Sharp lower bounds and upper bounds on $r\left(\mathrm{\Gamma }\right(G\left)\right)-r\left(G\right)$ are determined. All the corresponding extremal signed graphs $\mathrm{\Gamma }\left(G\right)$ are characterized, respectively.

KEYWORDS:

• Signed graph
• rank
• upper-optimal
• lower-optimal

AMS SUBJECT CLASSIFICATION:

• 05C50

Acknowledgements

The author is very grateful to Professor Shuchao Li for some of his ideas, discussions, and many useful suggestions. I am indebted to the referees for carefully reading the manuscript and providing numerous comments.

Disclosure statement

No potential conflict of interest was reported by the author.