The Clique Structure of Johnson Graphs

arXiv2208.12710MaRDI QIDQ6408935

R. Wayne Oldford, Pavel Shuldiner

Publication date: 26 August 2022

Abstract: Motivated by an approach to visualization of high dimensional statistical data given in Hurley and Oldford (2011), this work examines the clique structure of $J_n(m,m-1)$ Johnson graphs. Cliques and maximal cliques are characterized and proved to be of one of only two types. These types are characterized by features of the intersection and of the union of the subsets of [n] = {1, 2, ..., n} which define the vertices of the graph. Clique numbers and clique partition numbers follow. The results on Johnson graphs are connected to results on intersecting families of sets related to extremal set theory.

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Extremal set theory (05D05)

This page was built for publication: The Clique Structure of Johnson Graphs