Relation between the skew-rank of an oriented graph and the independence number of its underlying graph

J. Huang, S. C. Li, H. Wang

Published 2017-04-23Version 1

An oriented graph $G^\sigma$ is a digraph without loops or multiple arcs whose underlying graph is $G$. Let $S\left(G^\sigma\right)$ be the skew-adjacency matrix of $G^\sigma$ and $\alpha(G)$ be the independence number of $G$. The rank of $S(G^\sigma)$ is called the skew-rank of $G^\sigma$, denoted by $sr(G^\sigma)$. Wong et al. [European J. Combin. 54 (2016) 76-86] studied the relationship between the skew-rank of an oriented graph and the rank of its underlying graph. In this paper, the correlation involving the skew-rank, the independence number, and some other parameters are considered. First we show that $sr(G^\sigma)+2\alpha(G)\geqslant 2|V_G|-2d(G)$, where $|V_G|$ is the order of $G$ and $d(G)$ is the dimension of cycle space of $G$. We also obtain sharp lower bounds for $sr(G^\sigma)+\alpha(G),\, sr(G^\sigma)-\alpha(G)$, $sr(G^\sigma)/\alpha(G)$ and characterize all corresponding extremal graphs.