The relation between the H-rank of a mixed graph and the independence number of its underlying graph. Issue 11 (2nd November 2019) - Li, Shuchao; Zhang, Siqi; Xu, Baogen
ABSTRACT: Let G = ( V G, E G ) be a simple graph with vertex set V G and edge set E G . By orienting a subset of E G, we get a mixed graph G . Let H ( G ) be the Hermitian-adjacency matrix of G , the rank of H ( G ), written as r k ( G ), is called the H -rank of G . Denote by d ( G ) the dimension of cycle spaces of G, that is d ( G ) = | E G | − | V G | + c ( G ), where c ( G ) denotes the number of connected components of G . Let α ( G ) be the independence number of G . In this paper, the relationship between the H -rank of G and the independence number of G is characterized. Firstly, it is proved that 2 | V G | − 2 d ( G ) ⩽ r k ( G ) + 2 α ( G ) ⩽ 2 | V G | for every mixed graph G . Secondly, all the mixed graphs which satisfy r k ( G ) + 2 α ( G ) = 2 | V G | − 2 d ( G ) are characterized.