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

Abstract

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)⩾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.

16 Page; 1 figure