Properties of Full-Flag Johnson Graphs

2013/01/07 by Irving Dai, Dai, Irving, Michael Greenberg +5
Computer Science · Engineering · Mathematics · #Advanced Combinatorial Mathematics #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #graph theory and CDMA systems #math.CO

paper · pdf · doi:10.48550/arxiv.1301.1131

openalex publication_date 2013/01/07 · arxiv created 2013/09/16 · arxiv updated 2013/09/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We introduce and study a variant of the family of Johnson graphs, the Full-Flag Johnson graphs. We show that Full-Flag Johnson graphs are Cayley graphs on S_n generated by certain classes of permutations, and that they are in fact generalizations of permutahedra. We derive some results about the adjacency matrices of Full-Flag Johnson graphs and apply these to the set of permutahedra to deduce part of their spectra.

Related

• Cayley properties of merged Johnson graphs
• The Clique Structure of Johnson Graphs
• Spectra and eigenspaces from regular partitions of Cayley (di)graphs of permutation groups
• Faces of Generalized Permutohedra
• On the chromatic numbers of Johnson type graphs