Relation between the H-rank of a mixed graph and the rank of its underlying graph

被引:17
作者
Chen, Chen [1 ]
Li, Shuchao [1 ]
Zhang, Minjie [2 ]
机构
[1] Cent China Normal Univ, Fac Math & Stat, Wuhan 430079, Hubei, Peoples R China
[2] Hubei Univ Arts & Sci, Sch Math & Stat, Xiangyang 441053, Peoples R China
基金
中国国家自然科学基金;
关键词
Mixed graph; H-rank; Lower-optimal; Upper-optimal; delta-transformation; ORIENTED GRAPH; SKEW-RANK; INDEPENDENCE NUMBER; MATCHING NUMBER; NULLITY; TERMS;
D O I
10.1016/j.disc.2019.01.009
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Given a simple graph G = (V-G, E-G) with vertex set V-G and edge set E-G , the mixed graph (C) over tilde is obtained from G by orienting some of its edges. Let H(G)over tilde>) denote the Hermitian adjacency matrix of (G)over tilde> and A(G) be the adjacency matrix of G. The H-rank (resp. rank) of (G ) over tilde (resp. G), written as rk(G) (resp. r(G)), is the rank of H(G) (resp. A(G)). Denote by d(G) the dimension of cycle space of G, that is d(G) = vertical bar E-G vertical bar - vertical bar V-G vertical bar + omega(G), where omega(G) denotes the number of connected components of G. In this paper, we concentrate on the relation between the H-rank of (G) over tilde and the rank of G. We first show that -2d(G) <= rk((G) over tilde) - r(G) <= 2d(G) for every mixed graph (G) over tilde. Then we characterize all the mixed graphs that attain the above lower (resp. upper) bound. By these obtained results in the current paper, all the main results obtained in Luo et al. (2018); Wong et al. (2016) may be deduced consequently. (C) 2019 Elsevier B.V. All rights reserved.
引用
收藏
页码:1300 / 1309
页数:10
相关论文
共 25 条
[1]   On the mixed adjacency matrix of a mixed graph [J].
Adiga, Chandrashekar ;
Rakshith, B. R. ;
So, Wasin .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2016, 495 :223-241
[2]  
Bapat R. B., 2014, GRAPHS AND MATRICS
[3]  
Bevis JH, 1997, LINEAR ALGEBRA APPL, V265, P55
[4]   On the relation between the H-rank of a mixed graph and the matching number of its underlying graph [J].
Chen, Chen ;
Huang, Jing ;
Li, Shuchao .
LINEAR & MULTILINEAR ALGEBRA, 2018, 66 (09) :1853-1869
[5]   On the nullity of graphs [J].
Cheng, Bo ;
Liu, Bolian .
ELECTRONIC JOURNAL OF LINEAR ALGEBRA, 2007, 16 :60-67
[6]  
Cvetkovic D., 1972, Mat. Ves, V9, P141
[7]   Hermitian Adjacency Matrix of Digraphs and Mixed Graphs [J].
Guo, Krystal ;
Mohar, Bojan .
JOURNAL OF GRAPH THEORY, 2017, 85 (01) :217-248
[8]   The spectral distribution of random mixed graphs [J].
Hu, Dan ;
Li, Xueliang ;
Liu, Xiaogang ;
Zhang, Shenggui .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2017, 519 :343-365
[9]   Relation between the skew-rank of an oriented graph and the independence number of its underlying graph [J].
Huang, Jing ;
Li, Shuchao ;
Wang, Hua .
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2018, 36 (01) :65-80
[10]  
[李学良 Li Xueliang], 2015, [中国科学. 数学, Scientia Sinica Mathematica], V45, P93