Relation between the skew-rank of an oriented graph and the independence number of its underlying graph |
| |
Authors: | Jing Huang Shuchao Li Hua Wang |
| |
Institution: | 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 \(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. (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 )+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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|