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.
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
(38)- The trace formula with respect to the Grover matrix of a graph
- The discrete-time quaternionic quantum walk on a graph
- On the power of combinatorial and spectral invariants
- Quantum walks
- On the relation between quantum walks and zeta functions
- Quantum walks induced by Dirichlet random walks on infinite trees
- Quantum walks, Ihara zeta functions and cospectrality in regular graphs
- A study of graph spectra for comparing graphs and trees
- Zeta functions with respect to general coined quantum walk of periodic graphs
- A remark on zeta functions of finite graphs via quantum walks
- Quantum walks driven by quantum coins with two multiple eigenvalues
- Characteristic Polynomial Analysis on Matrix Representations of Graphs
- A characteristic polynomial for the transition probability matrix of correlated random walks on a graph
- Periodicity of Grover walks on generalized Bethe trees
- Periodicities of Grover walks on distance-regular graphs
- The spectra of the unitary matrix of an n-tessellable staggered quantum walk on a graph
- The spectral analysis of the unitary matrix of a 2-tessellable staggered quantum walk on a graph
- Quaternionic Grover walks and zeta functions of graphs with loops
- Graph characteristics from the heat kernel trace
- scientific article; zbMATH DE number 6282149 (Why is no real title available?)
- Computation of polarized metrized graph invariants by using discrete Laplacian matrix
- Quantum walks defined by digraphs and generalized Hermitian adjacency matrices
- The discrete-time quaternionic quantum walk and the second weighted zeta function on a graph
- A zeta function related to the transition matrix of the discrete-time quantum walk on a graph
- On the locating matrix of a graph and its spectral analysis
- Phase measurement of quantum walks: application to structure theorem of the positive support of the Grover walk
- The Ihara expression for the generalized weighted zeta function of a finite simple graph
- Discrete-time quantum walks and graph structures
- A quantum walk induced by Hoffman graphs and its periodicity
- Quantum walks on generalized quadrangles
- Ruelle zeta functions for finite digraphs
- On two matrices that can be used to check graph isomorphism
- Entanglement entropy in the ground state of supersymmetric fermion lattice models
- Odd-periodic Grover walks
- Spatial search on Johnson graphs by discrete-time quantum walk
- On the limitations of graph invariants inspired by quantum walks
- Spectral mapping theorem of an abstract non-unitary quantum walk
- scientific article; zbMATH DE number 193703 (Why is no real title available?)
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)
