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

DOI10.1016/J.DISC.2019.01.009MaRDI QIDQ1732760zbMATH OpenOpenAlexFDO

Authors Chen Chen, Shuchao Li, Min-jie Zhang

Publication date 25 March 2019

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1812.05309

zbMATH Keywords

\(\delta\)-transformation\(H\)-ranklower-optimalmixed graphupper-optimal

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Abstract: Given a simple graph $G=(V_G,E_G)$ with vertex set $V_G$ and edge set $E_G$, the mixed graph $widetildeG$ is obtained from $G$ by orienting some of its edges. Let $H(widetildeG)$ denote the Hermitian adjacency matrix of $widetildeG$ and $A(G)$ be the adjacency matrix of $G$. The $H$-rank (resp. rank) of $widetildeG$ (resp. $G$), written as $rk(widetildeG)$ (resp. $r(G)$), is the rank of $H(widetildeG)$ (resp. $A(G)$). Denote by $d(G)$ the dimension of cycle spaces of $G$, that is $d(G)=|E_G|-|V_G|+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 $widetildeG$ and the rank of $G$. We first show that $-2d(G)leqslantrk(widetildeG)-r(G)leqslant2d(G)$ for every mixed graph $widetildeG$. 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 cite{004,1} may be deduced consequently.

Recommendations

• The relation between the \(H\)-rank of a mixed graph and the independence number of its underlying graph
• On the relation between theH-rank of a mixed graph and the matching number of its underlying graph
• Mixed graphs with \(H\)-rank 3
• Relation between the rank of a signed graph and the rank of its underlying graph
• Some relations between rank of a graph and its complement
• Relations between the inertia indices of a mixed graph and those of its underlying graph
• On the characteristic polynomials and \(H\)-ranks of the weighted mixed graphs
• Rank of the Hermitian-adjacency matrix of a mixed graph in terms of matching number.
• Relation between the Hermitian energy of a mixed graph and the matching number of its underlying graph
• Relationship between the rank and the matching number of a graph

Cites work

• A characterization of graphs \(G\) with nullity \(|V(G)|-2m(G)+2c(G)\)
• A characterization of long graphs of arbitrary rank
• A characterization of signed planar graphs with rank at most 4
• An upper bound of the nullity of a graph in terms of order and maximum degree
• Bounds for the matching number, the edge chromatic number and the independence number of a graph in terms of rank
• First eigenvalue of nonsingular mixed unicyclic graphs with fixed number of branch vertices
• Graphs and matrices
• Hermitian adjacency spectrum and switching equivalence of mixed graphs
• Hermitian-adjacency matrices and Hermitian energies of mixed graphs
• scientific article; zbMATH DE number 3414355 (Why is no real title available?)
• Mixed graphs with \(H\)-rank 3
• Nullity of a graph in terms of the dimension of cycle space and the number of pendant vertices
• On the mixed adjacency matrix of a mixed graph
• On the nullity of graphs
• On the relation between theH-rank of a mixed graph and the matching number of its underlying graph
• On the relationship between the skew-rank of an oriented graph and the rank of its underlying graph
• Relation between the skew-rank of an oriented graph and the independence number of its underlying graph
• Relation between the skew-rank of an oriented graph and the rank of its underlying graph
• Skew-rank of an oriented graph in terms of matching number
• The extremal graphs with respect to their nullity
• The nullity of \(k\)-cyclic graphs of \(\infty\)-type
• The rank of a graph after vertex addition
• The skew-rank of oriented graphs
• The spectral distribution of random mixed graphs

Cited in

(22)

• Some mixed graphs with \(H\)-rank 4, 6 or 8
• The \(k\)-generalized Hermitian adjacency matrices for mixed graphs
• Relations between the inertia indices of a mixed graph and those of its underlying graph
• The multiplicity of an \(A_\alpha \)-eigenvalue: a unified approach for mixed graphs and complex unit gain graphs
• On graphs whose orientations are determined by their Hermitian spectra
• On mixed graphs whose Hermitian spectral radii are at most 2
• On the characteristic polynomials and \(H\)-ranks of the weighted mixed graphs
• The negative tetrahedron and the first infinite family of connected digraphs that are strongly determined by the Hermitian spectrum
• Some families of integral mixed graphs
• Rank of the Hermitian-adjacency matrix of a mixed graph in terms of matching number.
• On the relation between theH-rank of a mixed graph and the matching number of its underlying graph
• Bounds on the nullity, the H-rank and the Hermitian energy of a mixed graph
• Relation between the inertia indices of a complex unit gain graph and those of its underlying graph
• On the relation between the adjacency rank of a complex unit gain graph and the matching number of its underlying graph
• The relation between the \(H\)-rank of a mixed graph and the independence number of its underlying graph
• Mixed graphs with \(H\)-rank 3
• scientific article; zbMATH DE number 7692350 (Why is no real title available?)
• Incidence matrices and line graphs of mixed graphs
• On the characteristic polynomial and energy of Hermitian quasi-Laplacian matrix of mixed graphs
• Developments on the Hoffman program of graphs
• Relation between the H-rank of a mixed graph and the girth of its underlying graph
• Improved bounds on the H-rank of a mixed graph in terms of the matching number and fractional matching number

This page was built for publication: Relation between the \(H\)-rank of a mixed graph and the rank of its underlying graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1732760)