Skew-rank of an oriented graph in terms of the rank and dimension of cycle space of its underlying graph


Yong Lu, Ligong Wang, Qiannan Zhou




Let G σ be an oriented graph and S(G σ) be its skew-adjacency matrix, where G is called the underlying graph of G σ. The skew-rank of G σ , denoted by sr(G σ), is the rank of S(G σ). Denote by d(G) = |E(G)| − |V(G)| + θ(G) the dimension of cycle spaces of G, where |E(G)|, |V(G)| and θ(G) are the edge number, vertex number and the number of connected components of G, respectively. Recently, Wong, Ma and Tian [European J. Combin. 54 (2016) 76–86] proved that sr(G σ) ≤ r(G) + 2d(G) for an oriented graph G σ , where r(G) is the rank of the adjacency matrix of G, and characterized the graphs whose skew-rank attain the upper bound. However, the problem of the lower bound of sr(G σ) of an oriented graph G σ in terms of r(G) and d(G) of its underlying graph G is left open till now. In this paper, we prove that sr(G σ) ≥ r(G) − 2d(G) for an oriented graph G σ and characterize the graphs whose skew-rank attain the lower bound