Equitable decompositions of graphs with symmetries

DOI10.1016/J.LAA.2016.10.017zbMATH Open1350.05091arXiv1510.04366OpenAlexW2534504831MaRDI QIDQ344919FDOQ344919

Authors: Wayne Barrett, Amanda Francis, B. Z. Webb 

Publication date: 25 November 2016

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Abstract: We investigate connections between the symmetries (automorphisms) of a graph and its spectral properties. Whenever a graph has a symmetry, i.e. a nontrivial automorphism $phi$, it is possible to use $phi$ to decompose any matrix $Minmathbb{C}^{nimesn}$ appropriately associated with the graph. The result of this decomposition is a number of strictly smaller matrices whose collective eigenvalues are the same as the eigenvalues of the original matrix $M$. Some of the matrices that can be decomposed are the graph's adjaceny matrix, Laplacian matrix, etc. Because this decomposition has connections to the theory of equitable partitions it is referred to as an equitable decomposition. Since the graph structure of many real-world networks is quite large and has a high degree of symmetry, we discuss how equitable decompositions can be used to effectively bound both the network's spectral radius and spectral gap, which are associated with dynamic processes on the network. Moreover, we show that the techniques used to equitably decompose a graph can be used to bound the number of simple eigenvalues of undirected graphs, where we obtain sharp results of Petersdorf-Sachs type.

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

Recommendations

• Extensions and applications of equitable decompositions for graphs with symmetries
• General equitable decompositions for graphs with symmetries
• Fourier decompositions of graphs with symmetries and equitable partitions
• Exploring symmetries to decompose matrices and graphs preserving the spectrum
• Characterizing and computing weight-equitable partitions of graphs

zbMATH Keywords

automorphismequitable partitioneigenvalue multiplicitygraph symmetry

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Symmetry in complex networks
• Title not available (Why is that?)
• A note on limit points for algebraic connectivity
• Isospectral graph transformations, spectral equivalence, and global stability of dynamical networks
• Title not available (Why is that?)
• Synchronization of networks with prescribed degree distributions
• Optimal network topologies: expanders, cages, Ramanujan graphs, entangled networks and all that
• Title not available (Why is that?)

Cited In (15)

• On symmetric equivalence of symmetric union diagrams
• General equitable decompositions for graphs with symmetries
• Exploring symmetries to decompose matrices and graphs preserving the spectrum
• Extensions and applications of equitable decompositions for graphs with symmetries
• Techniques for determining equality of the maximum nullity and the zero forcing number of a graph
• Spectral gap in random bipartite biregular graphs and applications
• On an infinite family of integral Cayley graphs of Pauli groups
• Analysis of node2vec random walks on networks
• Hidden symmetries in real and theoretical networks
• Perfect colorings of regular graphs
• Complete equitable decompositions
• Fourier decompositions of graphs with symmetries and equitable partitions
• Orbigraphs: a graph-theoretic analog to Riemannian orbifolds
• Characteristic polynomials and zeta functions of equitably partitioned graphs
• Finding hidden structures, hierarchies, and cores in networks via isospectral reduction

This page was built for publication: Equitable decompositions of graphs with symmetries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q344919)