The Johnson graph has the -element subsets of an -element set as vertices, with two vertices adjacent exactly when their intersection has elements. Relabelling the ground set gives graph automorphisms. The maximal cliques of a Johnson graph allow reconstruction of those ground-set labels when the two clique sizes are different.
A Johnson graph, denoted as \( J(n, k) \), is a type of vertex-transitive graph that represents the relationships between the \( k \)-element subsets of an \( n \)-element set. Specifically, the vertices of a Johnson graph are the \( k \)-element subsets of a set with \( n \) elements, and there is an edge between two vertices (subsets) if their intersection has exactly \( k-1 \) elements.
New to topics? Read the docs here!