Interlacing families and the Hermitian spectral norm of digraphs
| Autor: | Gary R. W. Greaves, Bojan Mohar, Suil O |
|---|---|
| Přispěvatelé: | School of Physical and Mathematical Sciences |
| Rok vydání: | 2019 |
| Předmět: |
Mathematics [Science]
Spectral radius Matrix norm 010103 numerical & computational mathematics Orientation (graph theory) 01 natural sciences Ramanujan's sum Combinatorics symbols.namesake Hermitian Adjacency Matrix FOS: Mathematics Mathematics - Combinatorics Discrete Mathematics and Combinatorics 05C50 05C20 Adjacency matrix 0101 mathematics Connectivity Mathematics Discrete mathematics Numerical Analysis Algebra and Number Theory 010102 general mathematics Digraph 16. Peace & justice Hermitian matrix Tree (graph theory) symbols Combinatorics (math.CO) Geometry and Topology |
| Zdroj: | Linear Algebra and its Applications. 564:201-208 |
| ISSN: | 0024-3795 |
| DOI: | 10.1016/j.laa.2018.12.004 |
| Popis: | It is proved that for any finite connected graph G, there exists an orientation of G such that the spectral radius of the corresponding Hermitian adjacency matrix is smaller or equal to the spectral radius of the universal cover of G (with equality if and only if G is a tree). This provides a suitable answer to a problem proposed by Mohar. The proof uses the method of interlacing families of polynomials that was developed by Marcus, Spielman, and Srivastava in their seminal work on the existence of infinite families of Ramanujan graphs. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect