Equitable decompositions of graphs with symmetries

DOI10.1016/J.LAA.2016.10.017MaRDI QIDQ344919zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 740754 (Why is no real title available?)
• scientific article; zbMATH DE number 1054726 (Why is no real title available?)
• scientific article; zbMATH DE number 6125590 (Why is no real title available?)
• scientific article; zbMATH DE number 5936982 (Why is no real title available?)
• scientific article; zbMATH DE number 3349884 (Why is no real title available?)
• A note on limit points for algebraic connectivity
• Isospectral graph transformations, spectral equivalence, and global stability of dynamical networks
• Optimal network topologies: expanders, cages, Ramanujan graphs, entangled networks and all that
• Symmetry in complex networks
• Synchronization of networks with prescribed degree distributions

Cited in

(15)

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

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)