An edge-isoperimetric problem for powers of the Petersen graph (Q1575084)

The Cartesian product \(G_1\times G_2\) of graphs \(G_1=(V_1,E_1)\) and \(G_2=(V_2,E_2)\) has vertex set \(V_1\times V_2\) and edge set \(\{\{(x,y),(u,v)\}\mid (x=u\) and \(\{y,v\}\in E_2)\) or \((\{x,u\}\in E_1\) and \(y=v)\}\). Denoting the Petersen graph by \(P\), the authors study the Cartesian product \(P^n\) of \(n\) copies of \(P\). From their introduction: ``\dots{} we introduce a new order \({\mathcal P}^n\) on the set of \(n\)-dimensional tuples\dots{} and show that this order provides nestedness in the edge isoperimetric problem for \(P^n\dots\;\). This result allows us to compute exactly the cutwidth and wirelength of \(P^n\), which are respectively defined as the maximum and the mean value of the minimum cut separating the graph into two parts. We extend these results to the product graph \(P^n_m=P^n\times Q^m\), where \(Q^m\) is the \(m\)-dimensional hypercube.'' The graphs \(P_m^n\), called the folded Petersen cubes, were first studied by \textit{S. Öhring} and \textit{S. K. Das} [The folded Petersen cube networks: New competitors for the hypercube, in Proc. 5th IEEE Symposium on Parallel and Distributed Processing, 582-589 (1993); Folded Petersen cube networks: New competitors for the hypercube, IEEE Transactions on Parallel and Distributed Systems 7, 151-168 (1996)].