Permutational powers of a graph

zbMATH Open1427.05129arXiv1811.09836MaRDI QIDQ2335692FDOQ2335692

Authors: Matteo Cavaleri, Daniele D'Angeli, Alfredo Donno 

Publication date: 15 November 2019

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

Abstract: This paper introduces a new graph construction, the permutational power of a graph, whose adjacency matrix is obtained by the composition of a permutation matrix with the adjacency matrix of the graph. It is shown that this construction recovers the classical zig-zag product of graphs when the permutation is an involution, and it is in fact more general. We start by discussing necessary and sufficient conditions on the permutation and on the adjacency matrix of a graph to guarantee their composition to represent an adjacency matrix of a graph, then we focus our attention on the cases in which the permutational power does not reduce to a zig-zag product. We show that the cases of interest are those in which the adjacency matrix is singular. This leads us to frame our problem in the context of equitable partitions, obtained by identifying vertices having the same neighborhood. The families of cyclic and complete bipartite graphs are treated in details.

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

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

Recommendations

• The permutational graph: A new network topology
• Connectedness and isomorphism properties of the zig-zag product of graphs
• Publication:3470494
• scientific article; zbMATH DE number 2076912
• On cycle permutation graphs

zbMATH Keywords

adjacency matrixequitable partitionpermutation matrixzig-zag product

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph operations (line graphs, products, etc.) (05C76) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Cites Work

• Spectra of graphs
• Entropy waves, the zig-zag graph product, and new constant-degree expanders
• Title not available (Why is that?)
• Handbook of product graphs
• Expander graphs in pure and applied mathematics
• On linear relations between roots of unity
• Random symmetric matrices are almost surely nonsingular.
• Associative products of graphs
• The composition of graphs
• Title not available (Why is that?)
• Compact graphs and equitable partitions
• Feasibility conditions for the existence of walk-regular graphs
• Wreath product of matrices
• Title not available (Why is that?)
• Discrete harmonic analysis. Representations, number theory, expanders, and the Fourier transform
• Connectedness and isomorphism properties of the zig-zag product of graphs

Cited In (2)

• Permutations in Coinductive Graph Representation
• Permutations generated by token passing in graphs

This page was built for publication: Permutational powers of a graph

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