Narrow Results

A natural upper bound for the maximum number of vertices in a mixed graph with maximum undirected degree r, maximum directed out-degree z and diameter k is given by the mixed Moore bound. Graphs with order attaining the Moore bound are known as Moore graphs, and they are very rare. Besides, graphs with prescribed parameters and order one less than the corresponding Moore bound are known as almost Moore graphs. In this paper we prove that there is a unique mixed almost Moore graph of diameter k = 2 and parameters r = 2 and z = 1.

A mixed graph is a graph whose edge set consists of both oriented and unoriented edges. The Hermitian-adjacency matrix of an $n$-vertex mixed graph is a square matrix $H(M)=[h_{jk}]$ of order $n$, where $h_{jk}=\dot{\iota }=-h_{kj}$ if there is an arc from $v_j$ to $v_k$ and $h_{jk}=1$ if there is an edge between $v_j$ and $v_k$, and $h_{jk}=0$ otherwise. Let $D(M)=[d_{jj}]$ be a diagonal matrix, where $d_{jj}$ is the degree of $v_j$ in the underlying graph of $M$. The matrices $L(M)=D(M)-H(M)$ and $Q(M)=D(M)+H(M)$ are, respectively, the Hermitian Laplacian and Hermitian quasi-Laplacian matrix of the mixed graph $M$. In this paper, we first found coefficients of the characteristic polynomial of Hermitian Laplacian and Hermitian quasi-Laplacian matrices of the mixed graph $M$. Second, we discussed relationship between the spectra of Hermitian Laplacian and Hermitian quasi-Laplacian matrices of the mixed graph $M$.