The graphicahedron

The paper describes a construction of abstract polytopes from Cayley graphs of symmetric groups. Given any connected graph GG with pp vertices and qq edges, we associate with GG a Cayley graph G(G)G(G) of the symmetric group SpSp and then construct a vertex-transitive simple polytope of rank qq, the graphicahedron  , whose 1-skeleton (edge graph) is G(G)G(G). The graphicahedron of a graph GG is a generalization of the well-known permutahedron; the latter is obtained when the graph is a path. We also discuss symmetry properties of the graphicahedron and determine its structure when GG is small.