[feed] pefprints@pef.uni-lj.si | [feed] Atom [feed] RSS 1.0 [feed] RSS 2.0 |
  Logo Login | Create Account

Johnson and Kneser graphs

Sabina Pintar (2014) Johnson and Kneser graphs. Diploma thesis.

Download (866Kb)


    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.

    Item Type: Thesis (Diploma thesis)
    Keywords: Johnson graph, Kneser graph, J-graph, diameter, girth of graph, chromatic number, hamilton connectedness, regular graph
    Number of Pages: 58
    Language of Content: Slovenian
    Mentor / Comentors:
    Mentor / ComentorsIDFunction
    doc. dr. Primož ŠparlMentor
    Link to COBISS: http://www.cobiss.si/scripts/cobiss?command=search&base=50126&select=(ID=10045257)
    Institution: University of Ljubljana
    Department: Faculty of Education
    Item ID: 2125
    Date Deposited: 12 May 2014 13:46
    Last Modified: 12 May 2014 13:46
    URI: http://pefprints.pef.uni-lj.si/id/eprint/2125

    Actions (login required)

    View Item