Permutational powers of a graph

MaRDI QIDQ2335692zbMATH OpenFDO

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)

Full work available at URL https://arxiv.org/abs/1811.09836, https://www.combinatorics.org/ojs/index.php/eljc/article/view/v26i4p22

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

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)

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.

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

Cites work

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

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)