The relation between the H-rank of a mixed graph and the independence number of its underlying graph. Issue 11 (2nd November 2019)

• Record Type: Journal Article
• Authors: Li, Shuchao; Zhang, Siqi; Xu, Baogen
• Is Part Of: Linear & multilinear algebra. Volume 67:Issue 11(2019)
• Page Start: 2230
• Page End: 2245
• Publication Date: 2019-11-02
• Subjects: H-rank -- mixed graph -- independence number; 05C50 -- 05C69; Algebras, Linear -- Periodicals; Multilinear algebra -- Periodicals; 512.505
• DOI: 10.1080/03081087.2018.1488936
• Languages: English
• ISSNs: 0308-1087

Abstract

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.