Diameter bounds and recursive properties of Full-Flag Johnson graphs

The Johnson graphs J(n,k) are a well-known family of combinatorial graphs whose applications and generalizations have been studied extensively in the literature. In this paper, we present a new variant of the family of Johnson graphs, the Full-Flag Johnson graphs, and discuss their combinatorial properties. We show that the Full-Flag Johnson graphs are Cayley graphs on Sn generated by certain well-known classes of permutations and that they are in fact generalizations of permutahedra. We prove a tight Θ(n2∕k2) bound for the diameter of the Full-Flag Johnson graph FJ(n,k) and establish recursive relations between FJ(n,k) and the lower-order Full-Flag Johnson graphs FJ(n−1,k) and FJ(n−1,k−1). We apply this recursive structure to partially compute the spectrum of permutahedra.