A matrix representation of graphs and its spectrum as a graph invariant

zbMATH Open1099.05082arXivquant-ph/0505026MaRDI QIDQ2500953FDOQ2500953

Simone Severini, Richard C. Wilson, Edwin R. Hancock, David Emms

Publication date: 30 August 2006

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/quant-ph/0505026

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

strongly regular graphsorthogonal matrix

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Association schemes, strongly regular graphs (05E30)

Cited In (33)

• 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
• The discrete-time quaternionic quantum walk on a graph
• Quantum walks induced by Dirichlet random walks on infinite trees
• On the relation between quantum walks and zeta functions
• Quantum walks, Ihara zeta functions and cospectrality in regular graphs
• 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
• 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
• Title not available (Why is that?)
• Computation of polarized metrized graph invariants by using discrete Laplacian matrix
• Quantum walks defined by digraphs and generalized Hermitian adjacency matrices
• A zeta function related to the transition matrix of the discrete-time quantum walk on a graph
• 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
• 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
• Title not available (Why is that?)

   Recommendations

• Title not available (Why is that?) 👍 👎
• On the spectral invariants of symmetric matrices with applications in the spectral graph theory 👍 👎
• Laplacian spectra and invariants of graphs 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Spectral graph theory and the inverse eigenvalue problem of a graph 👍 👎
• The Laplacian eigenvalues and invariants of graphs 👍 👎
• Title not available (Why is that?) 👍 👎
• Invariant adjacency matrices of configuration graphs 👍 👎
• On a construction of integrally invertible graphs and their spectral properties 👍 👎

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)