Publication:2447959

DOI10.1016/J.LAA.2014.02.016zbMath1286.05087arXiv1505.01321OpenAlexW1994037159MaRDI QIDQ2447959

Bojan Mohar, Krystal Guo

Publication date: 29 April 2014

Published in: Linear Algebra and its Applications, Journal of Graph Theory (Search for Journal in Brave)

Abstract: The paper gives a thorough introduction to spectra of digraphs via its Hermitian adjacency matrix. This matrix is indexed by the vertices of the digraph, and the entry corresponding to an arc from $x$ to $y$ is equal to the complex unity $i$ (and its symmetric entry is $-i$) if the reverse arc $yx$ is not present. We also allow arcs in both directions and unoriented edges, in which case we use $1$ as the entry. This allows to use the definition also for mixed graphs. This matrix has many nice properties; it has real eigenvalues and the interlacing theorem holds for a digraph and its induced subdigraphs. Besides covering the basic properties, we discuss many differences from the properties of eigenvalues of undirected graphs and develop basic theory. The main novel results include the following. Several surprising facts are discovered about the spectral radius; some consequences of the interlacing property are obtained; operations that preserve the spectrum are discussed -- they give rise to an incredible number of cospectral digraphs; for every $0lealphalesqrt{3}$, all digraphs whose spectrum is contained in the interval $(-alpha,alpha)$ are determined.

Full work available at URL: https://arxiv.org/abs/1505.01321

zbMATH Keywords

eigenvaluespectral radiusdirected graphinfinite graphcospectralalgebraic graph theorymixed graph

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Directed graphs (digraphs), tournaments (05C20) Infinite graphs (05C63)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Skew-adjacency matrices of graphs
• Hermitian-adjacency matrices and Hermitian energies of mixed graphs
• Spectra of graphs
• Spektren endlicher Grafen
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Hermitian adjacency spectrum and switching equivalence of mixed graphs
• Eigenvalues and colorings of digraphs
• The spectrum of an infinite graph
• Counterexamples to the Baum-Connes conjecture
• Pick's inequality and tournaments
• Spectral decomposition of real circulant matrices
• Interlacing eigenvalues and graphs
• Median eigenvalues and the HOMO-LUMO index of graphs
• Expander graphs and their applications
• A Survey on Spectra of infinite Graphs
• On the Shannon capacity of a graph
• Random Walks on Infinite Graphs and Groups
• Median Eigenvalues of Bipartite Subcubic Graphs
• The Eigenvalues of a Graph and Its Chromatic Number
• The creation of spectral gaps by graph decoration

Related Items (only showing first 100 items - show all)

Construction of cospectral graphs, signed graphs and \(\mathbb{T}\)-gain graphs via partial transpose ⋮ On the spectrum of complex unit gain graphs ⋮ Inverse of Hermitian adjacency matrix of mixed bipartite graphs ⋮ \( \gamma \)-inverse graph of some mixed graphs ⋮ On the characteristic polynomial and energy of Hermitian quasi-Laplacian matrix of mixed graphs ⋮ Integral mixed Cayley graphs over abelian groups ⋮ Principal Minors of Hermitian (Quasi-)Laplacian Matrix of Second Kind for Mixed Graphs ⋮ Unit gain graphs with two distinct eigenvalues and systems of lines in complex space ⋮ On cospectral oriented graphs and cospectral signed graphs ⋮ Pretty good state transfer in discrete-time quantum walks ⋮ HS-integral and Eisenstein integral mixed Cayley graphs over abelian groups ⋮ Mixed graphs with smallest eigenvalue greater than \(- \frac{ \sqrt{ 5} + 1}{ 2} \) ⋮ Bounds for the rank of a complex unit gain graph in terms of the independence number ⋮ Inertia indices and eigenvalue inequalities for Hermitian matrices ⋮ On extremal spectral results of digraphs based on sum distance ⋮ Digraphs with Hermitian spectral radius below 2 and their cospectrality with paths ⋮ Universality in perfect state transfer ⋮ The rank of a complex unit gain graph in terms of the matching number ⋮ On the relation between theH-rank of a mixed graph and the matching number of its underlying graph ⋮ Some families of integral mixed graphs ⋮ Characterizing the mixed graphs with exactly one positive eigenvalue and its application to mixed graphs determined by their \(H\)-spectra ⋮ Spectral determinations and eccentricity matrix of graphs ⋮ Unnamed Item ⋮ The spectra of random mixed graphs ⋮ Bounds for the matching number and cyclomatic number of a signed graph in terms of rank ⋮ Hermitian adjacency spectrum and switching equivalence of mixed graphs ⋮ \(H\)-integral and Gaussian integral normal mixed Cayley graphs ⋮ On -gain graphs with few positive eigenvalues ⋮ The non-negative spectrum of a digraph ⋮ Gap sets for the spectra of cubic graphs ⋮ State transfer on integral mixed circulant graphs ⋮ Mixed graphs whose Hermitian adjacency matrices of the second kind have the smallest eigenvalue greater than \(- \frac{3}{2}\) ⋮ Splitting fields of mixed Cayley graphs over abelian groups ⋮ Quantum state transfer on integral oriented circulant graphs ⋮ On bounds of \(A_\alpha\)-eigenvalue multiplicity and the rank of a complex unit gain graph ⋮ Zero-divisor graphs of rings and their Hermitian matrices ⋮ Semi-restricted rock, paper, scissors ⋮ On the \({A_{\!\mathbb{C}}}\)-rank of multidigraphs ⋮ More on minors of Hermitian (quasi-)Laplacian matrix of the second kind for mixed graphs ⋮ Hermitian matrices of roots of unity and their characteristic polynomials ⋮ Why and how to add direction to a quantum walk ⋮ Spectral analysis of non-Hermitian matrices and directed graphs ⋮ On the multiplicities of digraph eigenvalues ⋮ Combinatorial necessary conditions for regular graphs to induce periodic quantum walks ⋮ Quantum walks defined by digraphs and generalized Hermitian adjacency matrices ⋮ On integral mixed Cayley graphs over non-abelian finite groups admitting an abelian subgroup of index 2 ⋮ Incidence matrices and line graphs of mixed graphs ⋮ On the inertia index of a mixed graph in terms of the matching number ⋮ Characterizing signed mixed graphs with small eigenvalues ⋮ Relations between the skew spectrum of an oriented graph and the spectrum of an associated signed graph ⋮ On graphs whose orientations are determined by their Hermitian spectra ⋮ Geometric and spectral analysis on weighted digraphs ⋮ NEPS of complex unit gain graphs ⋮ On symmetric spectra of Hermitian adjacency matrices for non-bipartite mixed graphs ⋮ Splitting fields of some matrices of normal (mixed) Cayley graphs ⋮ Transport properties in directed quantum walks on the line ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Interlacing families and the Hermitian spectral norm of digraphs ⋮ Hermitian normalized Laplacian matrix for directed networks ⋮ Minors of Hermitian (quasi-) Laplacian matrix of a mixed graph ⋮ Generalized spectral characterization of mixed graphs ⋮ On the spectra of general random mixed graphs ⋮ Complex unit gain graphs with exactly one positive eigenvalue ⋮ On mixed graphs whose Hermitian spectral radii are at most 2 ⋮ Bounds for the energy of a complex unit gain graph ⋮ Projecting signed two-mode networks ⋮ Relation between the \(H\)-rank of a mixed graph and the rank of its underlying graph ⋮ Hermitian Laplacian matrix and positive of mixed graphs ⋮ On ABC Estrada index of graphs ⋮ Gain distance matrices for complex unit gain graphs ⋮ Hermitian-Randić matrix and Hermitian-Randić energy of mixed graphs ⋮ Mixed graphs with \(H\)-rank 3 ⋮ On the eigenvalues distribution in threshold graphs ⋮ On graphs whose least eigenvalue is greater than –2 ⋮ On the characteristic polynomials and \(H\)-ranks of the weighted mixed graphs ⋮ Some mixed graphs with \(H\)-rank 4, 6 or 8 ⋮ Mixed paths and cycles determined by their spectrum ⋮ Unnamed Item ⋮ On spectral properties of digraphs about maximum distance ⋮ The index weighted Hermitian adjacency matrices for mixed graphs ⋮ Eigenvalues of complex unit gain graphs and gain regularity ⋮ Inverse of \(\alpha\)-Hermitian adjacency matrix of a unicyclic bipartite graph ⋮ Bounds on the nullity, the H-rank and the Hermitian energy of a mixed graph ⋮ On the largest eigenvalue of a mixed graph with partial orientation ⋮ Balancedness and the least Laplacian eigenvalue of some complex unit gain graphs ⋮ Relation between the Hermitian energy of a mixed graph and the matching number of its underlying graph ⋮ On the N-spectrum of oriented graphs ⋮ Maximizing the Order of a Regular Graph of Given Valency and Second Eigenvalue ⋮ The negative tetrahedron and the first infinite family of connected digraphs that are strongly determined by the Hermitian spectrum ⋮ Mixed graphs with smallest eigenvalue greater than \(- \sqrt{3}\) ⋮ Spectral fundamentals and characterizations of signed directed graphs ⋮ Hermitian energy and Hermitian Estrada index of digraphs ⋮ The relation between the H-rank of a mixed graph and the independence number of its underlying graph ⋮ The spectra of digraphs with Morita equivalent \(C^\ast\)-algebras ⋮ A new kind of Hermitian matrices for digraphs ⋮ Integral mixed circulant graphs ⋮ The \(k\)-generalized Hermitian adjacency matrices for mixed graphs ⋮ Maximal digraphs whose Hermitian spectral radius is at most 2 ⋮ Harmonic analysis on directed graphs and applications: from Fourier analysis to wavelets

Uses Software

• Unnamed Item

This page was built for publication: Large regular bipartite graphs with median eigenvalue 1