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.
@article{10_37236_8337,
author = {Matteo Cavaleri and Daniele D'Angeli and Alfredo Donno},
title = {Permutational powers of a graph},
journal = {The electronic journal of combinatorics},
year = {2019},
volume = {26},
number = {4},
doi = {10.37236/8337},
zbl = {1427.05129},
url = {http://geodesic.mathdoc.fr/articles/10.37236/8337/}
}
TY - JOUR
AU - Matteo Cavaleri
AU - Daniele D'Angeli
AU - Alfredo Donno
TI - Permutational powers of a graph
JO - The electronic journal of combinatorics
PY - 2019
VL - 26
IS - 4
UR - http://geodesic.mathdoc.fr/articles/10.37236/8337/
DO - 10.37236/8337
ID - 10_37236_8337
ER -
%0 Journal Article
%A Matteo Cavaleri
%A Daniele D'Angeli
%A Alfredo Donno
%T Permutational powers of a graph
%J The electronic journal of combinatorics
%D 2019
%V 26
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/8337/
%R 10.37236/8337
%F 10_37236_8337
Matteo Cavaleri; Daniele D'Angeli; Alfredo Donno. Permutational powers of a graph. The electronic journal of combinatorics, Tome 26 (2019) no. 4. doi: 10.37236/8337
