On the spectra of general random mixed graphs

Dan Hu¹ ; Hajo Broersma² ; Jiangyou Hou³ ; Shenggui Zhang⁴

¹School of Sciences, Xi'an University of Technology, Xi'an, Shaanxi 710048, P.R. China
²University of Twente
³School of Mathematics, Northwest University, Xi'an, Shaanxi 710127, P.R. China
⁴School of Mathematics and Statistics, Northwestern Polytechnical University, Xi'an, Shaanxi 710129, P.R. China

The electronic journal of combinatorics, Tome 28 (2021) no. 1

Résumé

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 \times n$ matrix $H(G)=(h_{ij})$, where $h_{ij}=-h_{ji}= \boldsymbol{\mathrm{i}}$ (with $\boldsymbol{\mathrm{i}} =\sqrt{-1})$ if there exists an arc from $v_i$ to $v_j$ (but no arc from $v_j$ to $v_i$), $h_{ij}=h_{ji}=1$ if there exists an edge (and no arcs) between $v_i$ and $v_j$, and $h_{ij}= 0$ otherwise (if $v_i$ and $v_j$ 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 Laplacian 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.

Détail

DOI : 10.37236/9638

Classification : 05C50, 15A18, 05C80
Mots-clés : general random mixed graphs, random Hermitian adjacency matrix, random normalized Hermitian Laplacian matrix, spectra