Johnson and Kneser graphs
Sabina Pintar · PeFprints (University of Ljubljana) · 2014
This graduation paper deals with the so-called J-graph family and two of its subfamilies, the Johnson graphs and the Kneser graphs. These graph families are well known and their members have some important properties. For instance, they are very symmetric: the Johnsons graphs are even distance-transitive and therefore very interesting for researches. In this graduation paper we first present some basic properties of these graph families, their degree, connectedness, regularity and vertex-, edge- and arc-transitivity. Later we focus on some of the more complex properties. We determine the diameter of Johnson graphs and show that they are distance-transitive and hamilton connected. We determine the girth of the Kneser graphs and their chromatic number. Even though matematicians have been studying these graph families for quite a while now, a lot of questions remain unanswered. At the end of this graduation paper we present one of the more interesting ones.