Johnson graphs, Diameter (Geometry), Uniform subset graphs, Set theory
Let v > k > i be non-negative integers. The generalized Johnson graph, J(v,k,i), is the graph whose vertices are the k-subsets of a v-set, where vertices A and B are adjacent whenever |A∩B|= i. In this article, we derive general formulas for the girth and diameter of J(v,k,i). Additionally, we provide a formula for the distance between any two vertices A and B in terms of the cardinality of their intersection.
Agong, Louis Anthony; Amarra, Carmen; Caughman, John; Herman, Ari J.; and Terada, Taiyo S., "On the Girth and Diameter of Generalized Johnson Graphs" (2018). Mathematics and Statistics Faculty Publications and Presentations. 201.
Available for download on Wednesday, January 01, 2020