A matrix representation of graphs and its spectrum as a graph invariant
From MaRDI portal
Publication:2500953
Abstract: We use the line digraph construction to associate an orthogonal matrix with each graph. From this orthogonal matrix, we derive two further matrices. The spectrum of each of these three matrices is considered as a graph invariant. For the first two cases, we compute the spectrum explicitly and show that it is determined by the spectrum of the adjacency matrix of the original graph. We then show by computation that the isomorphism classes of many known families of strongly regular graphs (up to 64 vertices) are characterized by the spectrum of this matrix. We conjecture that this is always the case for strongly regular graphs and we show that the conjecture is not valid for general graphs. We verify that the smallest regular graphs which are not distinguished with our method are on 14 vertices.
Summary: We use the line digraph construction to associate an orthogonal matrix with each graph. From this orthogonal matrix, we derive two further matrices. The spectrum of each of these three matrices is considered as a graph invariant. For the first two cases, we compute the spectrum explicitly and show that it is determined by the spectrum of the adjacency matrix of the original graph. We then show by computation that the isomorphism classes of many known families of strongly regular graphs (up to 64 vertices) are characterized by the spectrum of this matrix. We conjecture that this is always the case for strongly regular graphs and we show that the conjecture is not valid for general graphs. We verify that the smallest regular graphs which are not distinguished with our method are on 14 vertices.
Recommendations
- Graph properties and invariants, by their associated matrices
- On the spectral invariants of symmetric matrices with applications in the spectral graph theory
- Laplacian spectra and invariants of graphs
- scientific article; zbMATH DE number 4139784
- Spectral graph theory and the inverse eigenvalue problem of a graph
- Spectral graph theory and the inverse eigenvalue problem of a graph
- The Laplacian eigenvalues and invariants of graphs
- scientific article; zbMATH DE number 1264877
- Invariant adjacency matrices of configuration graphs
- On a construction of integrally invertible graphs and their spectral properties
Cited in
(42)- On the locating matrix of a graph and its spectral analysis
- Quaternionic Grover walks and zeta functions of graphs with loops
- The spectral analysis of the unitary matrix of a 2-tessellable staggered quantum walk on a graph
- A zeta function related to the transition matrix of the discrete-time quantum walk on a graph
- The Ihara expression for the generalized weighted zeta function of a finite simple graph
- Ruelle zeta functions for finite digraphs
- The spectra of the unitary matrix of an n-tessellable staggered quantum walk on a graph
- Graph characteristics from the heat kernel trace
- A quantum walk induced by Hoffman graphs and its periodicity
- Periodicities of Grover walks on distance-regular graphs
- Discrete-time quantum walks and graph structures
- Quantum walks on generalized quadrangles
- Phase measurement of quantum walks: application to structure theorem of the positive support of the Grover walk
- The discrete-time quaternionic quantum walk on a graph
- A characteristic polynomial for the transition probability matrix of correlated random walks on a graph
- Quantum walks defined by digraphs and generalized Hermitian adjacency matrices
- On the limitations of graph invariants inspired by quantum walks
- Characteristic Polynomial Analysis on Matrix Representations of Graphs
- scientific article; zbMATH DE number 193703 (Why is no real title available?)
- On the relation between quantum walks and zeta functions
- Quantum walks induced by Dirichlet random walks on infinite trees
- Spatial search on Johnson graphs by discrete-time quantum walk
- The trace formula with respect to the Grover matrix of a graph
- Quantum walks
- The discrete-time quaternionic quantum walk and the second weighted zeta function on a graph
- On two matrices that can be used to check graph isomorphism
- scientific article; zbMATH DE number 6282149 (Why is no real title available?)
- Quantum walks, Ihara zeta functions and cospectrality in regular graphs
- Computation of polarized metrized graph invariants by using discrete Laplacian matrix
- Odd-periodic Grover walks
- Spectral mapping theorem of an abstract non-unitary quantum walk
- Entanglement entropy in the ground state of supersymmetric fermion lattice models
- Quantum walks driven by quantum coins with two multiple eigenvalues
- The absolute zeta function with respect to a bipartite walk on a bipartite graph
- Clique complexes of strongly regular graphs, their eigenvalues, and cohomology groups
- Konno-Sato theorem for a covering of a graph
- Iwasawa theory for weighted graphs
- Periodicity of Grover walks on generalized Bethe trees
- Zeta functions with respect to general coined quantum walk of periodic graphs
- A remark on zeta functions of finite graphs via quantum walks
- A study of graph spectra for comparing graphs and trees
- On the power of combinatorial and spectral invariants
This page was built for publication: A matrix representation of graphs and its spectrum as a graph invariant
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2500953)
