Improved bounds on the H-rank of a mixed graph in terms of the matching number and fractional matching number

2025/07/07 by Wu, Qi, Lu, Yong
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2507.04728

Abstract

A mixed graph \widetildeG is obtained by orienting some edges of a graph G, where G is the underlying graph of \widetildeG. Let r(\widetildeG) be the H-rank of \widetildeG. Denote by r(G), κ(G), m(G) and m^∗(G) the rank, the number of even cycles, the matching number and the fractional matching number of G, respectively. Zhou et al. [Discrete Appl. Math. 313 (2022)] proved that 2m(G)-2κ(G)≤ r(G)≤ 2m(G)+ρ(G), where ρ(G) is the largest number of disjoint odd cycles in G. We extend their results to the setting of mixed graphs and prove that 2m(G)-2κ(G)≤ r(\widetildeG) ≤ 2m^∗(G) for a mixed graph \widetildeG. Furthermore, we characterize some classes of mixed graphs with rank r(\widetildeG)=2m(G)-2κ(G), r(\widetildeG)=2m(G)-2κ(G)+1 and r(\widetildeG)=2m^∗(G), respectively. Our results also improve those of Chen et al. [Linear Multiliear Algebra. 66 (2018)]. In addition, our results can be applied to signed graphs and oriented graphs in some situations.

Citations

• Relation between the H-rank of a mixed graph and the rank of its underlying graph
• Complex unit gain bicyclic graphs with rank 2, 3 or 4
• Hermitian adjacency spectrum and switching equivalence of mixed graphs

Related

• Relation between the H-rank of a mixed graph and the rank of its underlying graph
• Tight lower bounds on the matching number in a graph with given maximum degree
• No mixed graph with the nullity η(\widetildeG)=|V(G)|-2m(G)+2c(G)-1
• On total regularity of mixed graphs with order close to the Moore bound
• Nordhaus-Gaddum type inequality for the fractional matching number of a graph