Set Theory Commons^™

On The Girth And Diameter Of Generalized Johnson Graphs, Louis Anthony Agong, Carmen Amarra, John Caughman, Ari J. Herman, Taiyo S. Terada

Mathematics and Statistics Faculty Publications and Presentations

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.