Hamiltonske prizme

diplomsko delo

Žan Močivnik (Author), Boštjan Brešar (Mentor)

Abstract

Obstoja hamiltonske prizme v grafu leži med problemoma obstoja Hamiltonove poti in obstoja 2-sprehoda v grafu, kar v diplomskem delu podrobneje osvetlimo. Pri dokazovanju obstoja hamiltonskih prizem nad grafi si pomagamo s posebnim barvanjem povezav grafa. V prvem poglavju so opisane osnovne definicije in rezultati, povezani z grafi, prizmami in hamiltonskostjo. V drugem poglavju podrobneje obravnavamo prizme nad dvodelnimi grafi, kubičnimi grafi, posplošenimi Halinovimi grafi in grafi povezav ter predstavimo nekatere rezultate, ki se nanašajo na iskanje njihovih Hamiltonovih prizem.

Keywords

matematika;teorija grafov;prizma;kartezični produkt;Hamiltonov cikel;drevesa;diplomska dela;

Data

Language:	Slovenian
Year of publishing:	2012
Source:	Maribor
Typology:	2.11 - Undergraduate Thesis
Organization:	UM FNM - Faculty of Natural Sciences and Mathematics
Publisher:	[Ž. Močivnik]
UDC:	51(043.2)
COBISS:	18944008
Views:	2586
Downloads:	234
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	HAMILTONIAN PRISMS
Secondary abstract:	The diploma thesis examines the existence of Hamiltonian prisms over graphs. The problem of the existence of a Hamiltonian prism in a graph is directly related to the problems of the existence of a Hamiltonian path and of a 2-walk in a graph, which is analyzed in more detail in this work. In proving the existence of a Hamiltonian prism over a graph we use a special colouring of its edges. In the first chapter basic definitions and results related to graphs, prisms and hamiltonicity are described. In the second chapter we study in more detail the prisms over bipartite graphs, cubic graphs, generalized Halin graphs and line graphs, and present some results concerning the search for their Hamiltonian prisms.
Secondary keywords:	Graph Theory;prism;cartesian product;Hamilton cycle;Hamiltonian graph;Hamiltonian prism;k-walk;k-tree;k-factor.;
URN:	URN:SI:UM:
Type (COBISS):	Undergraduate thesis
Thesis comment:	Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Pages:	30 f.
Keywords (UDC):	mathematics;natural sciences;naravoslovne vede;matematika;mathematics;matematika;
ID:	19778