Diameter bounds and recursive properties of Full-Flag Johnson graphs

作者：Dai Irving^*

来源：Discrete Mathematics, 2018, 341(7): 1932-1944.

DOI：10.1016/j.disc.2018.03.014

• Johnson graph
• Permutahedron
• Irreducible permutation
• Cayley graph
• Diameter
• Spectrum

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 S-n, generated by certain well-known classes of permutations and that they are in fact generalizations of permutahedra. We prove a tight Theta(n(2)/k(2)) 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.

• 出版日期2018-7