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?

  • $\begingroup$ 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 $\endgroup$ – 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.