TY - JOUR
T1 - On the spectra of general random mixed graphs
AU - Hu, Dan
AU - Broersma, Hajo
AU - Hou, Jiangyou
AU - Zhang, Shenggui
N1 - Funding Information:
∗Supported by NSFC (No. 12001421), Scientific Research Program Funded by Shaanxi Provincial Education Department (20JK0782). †Corresponding author. ‡Supported by NSFC (No. 11701451). §Supported by NSFC (No. 12071370 and U1803263).
Publisher Copyright:
© The authors.
PY - 2021/1/15
Y1 - 2021/1/15
N2 - A mixed graph is a graph that can be obtained from a simple undirected graph by replacing some of the edges by arcs in precisely one of the two possible directions. The Hermitian adjacency matrix of a mixed graph G of order n is the n × n matrix H(G) = (hij ), where hij = −hji = i (with i =√−1) if there exists an arc from vi to vj (but no arc from vj to vi), hij = hji = 1 if there exists an edge (and no arcs) between vi and vj, and hij = 0 otherwise (if vi and vj are neither joined by an edge nor by an arc). We study the spectra of the Hermitian adjacency matrix and the normalized Hermitian Laplacian matrix of general random mixed graphs, i.e., in which all arcs are chosen independently with different probabilities (and an edge is regarded as two oppositely oriented arcs joining the same pair of vertices). For our first main result, we derive a new probability inequality and apply it to obtain an upper bound on the eigenvalues of the Hermitian adjacency matrix. Our second main result shows that the eigenvalues of the normalized Hermitian Lapla-cian matrix can be approximated by the eigenvalues of a closely related weighted expectation matrix, with error bounds depending on the minimum expected degree of the underlying undirected graph.
AB - A mixed graph is a graph that can be obtained from a simple undirected graph by replacing some of the edges by arcs in precisely one of the two possible directions. The Hermitian adjacency matrix of a mixed graph G of order n is the n × n matrix H(G) = (hij ), where hij = −hji = i (with i =√−1) if there exists an arc from vi to vj (but no arc from vj to vi), hij = hji = 1 if there exists an edge (and no arcs) between vi and vj, and hij = 0 otherwise (if vi and vj are neither joined by an edge nor by an arc). We study the spectra of the Hermitian adjacency matrix and the normalized Hermitian Laplacian matrix of general random mixed graphs, i.e., in which all arcs are chosen independently with different probabilities (and an edge is regarded as two oppositely oriented arcs joining the same pair of vertices). For our first main result, we derive a new probability inequality and apply it to obtain an upper bound on the eigenvalues of the Hermitian adjacency matrix. Our second main result shows that the eigenvalues of the normalized Hermitian Lapla-cian matrix can be approximated by the eigenvalues of a closely related weighted expectation matrix, with error bounds depending on the minimum expected degree of the underlying undirected graph.
KW - General random mixed graphs
KW - Random Hermitian adjacency matrix
KW - Random normalized Hermitian Laplacian matrix
KW - Spectra
KW - UT-Gold-D
UR - http://www.scopus.com/inward/record.url?scp=85100163779&partnerID=8YFLogxK
U2 - 10.37236/9638
DO - 10.37236/9638
M3 - Article
AN - SCOPUS:85100163779
SN - 1077-8926
VL - 28
JO - The Electronic journal of combinatorics
JF - The Electronic journal of combinatorics
IS - 1
M1 - P1.3
ER -