# Is there a name for this “stack” of graphs?

Let $$G_1,\ldots,G_m$$ be a sequence of graphs, all having the same number $$n$$ of vertices. For each pair $$(G_i, G_{i+1})$$ we add $$n$$ edges that connect the vertices of $$G_i$$ and $$G_{i+1}$$ bijectively. My question: Is there an established name for this "stack" of graphs?

• given @Rob Pratt's comment about this being the cartesian product whenever all the $G_i$ are equal, I wonder what the categorical formalisation of what you describe is? some sort of fibred product? I don't know – Tim Sep 2 '19 at 11:57

On page 4 of [1 ] , you find:

[...] a multiplex network can be represented as a collection of graphs $$\mathcal{G}=\{G^{(\ell)}=(V_n,E^{(\ell)})\}_{\ell \in V_L}$$ where $$V_n=\{1,\ldots,n\}$$ is the set of nodes, $$V_l=\{1,\ldots,L\}$$ s the set of layers and $$E^{(\ell)}\subset V_n\times V_n$$ is the set of edges on layer $$\ell$$.

These structures are also sometimes called multi-layer graphs. Note that in the above formulation it is assumed that the nodes on each layer are the same (this models the bijective edges you are referring to).

[1 ] Node and layer eigenvector centralities for multiplex networks. F Tudisco, F Arrigo, A Gautier - SIAM Journal on Applied Mathematics, 2018 (arXiv)

In the case that you only have two graphs, and they are the same, say $$G$$, then the edges between the two copies of $$G$$ can be described by a permutation, and your graphs are precisely the permutation graphs defined by Chartrand and Harary in their 1967 paper "Planar permutation graphs" [Ann. Inst. H. Poincaré Sect. B (N.S.), 3, pp. 433–438]. A cute example of such a "permutation graph" is the Petersen graph, which we can obtain with $$G=C_5$$.

(I cannot stress strongly enough that this is not the standard notion of permutation graphs!)

In the special case that $$G_i=G$$ for all $$i$$, this is the Cartesian product of $$G$$ with the path on $$n$$ nodes.

• That's not true if the vertices are simply connected "bijectively", as the question specifies. – Vince Vatter Aug 29 '19 at 12:07
• Yes, for the Cartesian product the bijection is the identity, not an arbitrary bijection. – Rob Pratt Aug 29 '19 at 13:15