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

Abstract

An oriented graph $G^σ$ is a digraph without loops or multiple arcs whose underlying graph is $G$. Let $S\left(G^σ\right)$ be the skew-adjacency matrix of $G^σ$ and $α(G)$ be the independence number of $G$. The rank of $S(G^σ)$ is called the skew-rank of $G^σ$, denoted by $sr(G^σ)$. 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^σ)+2α(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^σ)+α(G),\, sr(G^σ)-α(G)$, $sr(G^σ)/α(G)$ and characterize all corresponding extremal graphs.

16 Page; 1 figure