On Mixed Graphs Whose Hermitian Spectral Radii are at Most 2
- PDF / 287,659 Bytes
- 12 Pages / 439.37 x 666.142 pts Page_size
- 7 Downloads / 184 Views
(0123456789().,-volV) (0123456789().,-volV)
ORIGINAL PAPER
On Mixed Graphs Whose Hermitian Spectral Radii are at Most 2 Bo-Jun Yuan1 • Yi Wang1 • Shi-Cai Gong2 • Yun Qiao1 Received: 26 July 2019 / Revised: 4 May 2020 Ó Springer Japan KK, part of Springer Nature 2020
Abstract A mixed graph is a graph with undirected and directed edges. Guo and Mohar in 2017 determined all mixed graphs whose Hermitian spectral radii are less than 2. In this paper, we give a sufficient condition which can make Hermitian spectral radius of a connected mixed graph strictly decreasing when an edge or a vertex is deleted, and characterize all mixed graphs with Hermitian spectral radii at most 2 and with no cycle of length 4 in their underlying graphs. Keywords C4 -free graph Mixed graph Hermitian spectral radius
Mathematics Subject Classification 05C50
1 Introduction Characterizing the structure of a graph by the spectrum of an associated matrix with the graph is a basic problem in spectral graph theory. Since restrictions on the spectral radii of graphs with respect to their adjacency matrices often force those to have very special structures, it is always a hot topic to characterize the graphs whose spectral radii are bounded above. Smith [13] determined all graphs whose spectral radii are at most 2. This work stimulated the interest of researchers. There are a lot of results in the literature concerning the topic. Brouwer and Neumaier [1] characterized the graphs whose spectral radii are contained in the interval pffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi pffiffiffi ð2; 2 þ 5 and later, Woo and Neumaier [15] described the structure of graphs pffiffiffi whose spectral radii are bounded above by 32 2. Studying the same problem on digraphs has received less attention. Greaves [6] characterized all gain graphs whose gains are from the Gauss or Eisenstein integers This work was supported by National Natural Science Foundation of China (11771016, 11871073). Extended author information available on the last page of the article
123
Graphs and Combinatorics
and adjacency spectral radii are at most 2. Xu and Gong [17] investigated digraphs whose spectral radii with respect to their skew adjacency matrices do not exceed 2. Guo and Mohar [9] determined all mixed graphs whose spectral radii with respect to their Hermitian adjacency matrices are less than 2. Their work shows that 2 is the smallest limit point of the Hermitian spectral radii of connected mixed graphs. In the present paper, we characterize all C4 -free mixed graphs whose Hermitian spectral radii do not exceed 2. A graph containing undirected edges and directed edges is called a mixed graph. Clearly, mixed graphs are natural generalizations of both simple graphs and digraphs. Indeed, a mixed graph D can be obtained from a simple graph G by orienting a subset of its edge set. We call G as the underlying graph of D and denote it by G(D). Formally, a mixed graph D is comprised of the vertex set V(D), which is the same as the vertex set V(G), and the edge set E(D), which consists of two parts: undirected edge set
Data Loading...
