Relation between the skew-rank of an oriented graph and the independence number of its underlying graph |
| |
Authors: | Jing Huang Shuchao Li Hua Wang |
| |
Affiliation: | 1.Faculty of Mathematics and Statistics,Central China Normal University,Wuhan,People’s Republic of China;2.Department of Mathematical Sciences,Georgia Southern University,Statesboro,USA |
| |
Abstract: | An oriented graph (G^sigma ) is a digraph without loops or multiple arcs whose underlying graph is G. Let (Sleft( 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. (Eur J Comb 54:76–86, 2016) 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 )+2alpha (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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|