Johnsonovi in Kneserjevi grafi

Abstract

Keywords

Data

Language:	Slovenian
Year of publishing:	2014
Source:	Ljubljana
Typology:	2.11 - Undergraduate Thesis
Organization:	UL PEF - Faculty of Education
Publisher:	[S. Pintar]
UDC:	519.17(043.2)
COBISS:	10045257
Views:	1219
Downloads:	160
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Johnson and Kneser graphs
Secondary abstract:	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.
Secondary keywords:	mathematics;matematika;
File type:	application/pdf
Type (COBISS):	Undergraduate thesis
Thesis comment:	Univ. Ljubljana, Pedagoška fak., Matematika in fizika
Pages:	VIII, 58 str.
Type (ePrints):	thesis
Title (ePrints):	Johnsonovi in Kneserjevi grafi
Keywords (ePrints):	Johnsonov graf
Keywords (ePrints, secondary language):	Johnson graph
Abstract (ePrints):	To diplomsko delo obravnava družino tako imenovanih J-grafov in dve njeni poddružini, Johnsonove in Kneserjeve grafe. Gre za zelo znane družine grafov, ki imajo nekaj pomembnih lastnosti. So, na primer, zelo simetrični - Johnsonovi grafi so tako celo razdaljno tranzitivni in jih kot takšne zelo radi študiramo. V diplomskem delu najprej raziščemo najosnovnejše lastnosti teh družin grafov, na primer red grafa, povezanost, regularnost ter točkovno, povezavno in ločno tranzitivnost, nato pa se posvetimo tudi nekaterim bolj zahtevnim. Tako določimo premer Johnsonovih grafov in pokažemo, da so razdaljno tranzitivni in hamiltonsko povezani. Določimo tudi ožino Kneserjevih grafov in njihovo kromatično število. Čeprav so vse te družine že nekaj časa pod drobnogledom matematikov, še kar nekaj vprašanj ostaja odprtih. Na koncu diplomskega dela predstavimo eno izmed bolj zanimivih.
Abstract (ePrints, secondary language):	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.
Keywords (ePrints, secondary language):	Johnson graph
ID:	8328001