Girth of pancake graphs

We consider four families of pancake graphs, which are Cayley graphs, whose vertex sets are either the symmetric group on nn objects or the hyperoctahedral group on nn objects and whose generating sets are either all reversals or all reversals inverting the first kk elements (called prefix reversals). We find that the girth of each family of pancake graphs remains constant after some small threshold value of nn.

► Pancake graphs are four families of Cayley graphs on permutation groups. ► Breakpoints and kk-compressibility help determine the girth of pancake graphs. ► All four families of pancake graphs have constant girth after a small value of nn.