On the spectra of general random mixed graphs

Dan Hu, Hajo Broersma, Jiangyou Hou, Shenggui Zhang

科研成果: 会议稿件论文同行评审

摘要

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 = v-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 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.

源语言英语
132-135
页数4
出版状态已出版 - 2019
活动16th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2018 - Paris, 法国
期限: 18 6月 201820 6月 2018

会议

会议16th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2018
国家/地区法国
Paris
时期18/06/1820/06/18

指纹

探究 'On the spectra of general random mixed graphs' 的科研主题。它们共同构成独一无二的指纹。

引用此