Razred grafov H (n, k)

diplomsko delo

Nuša Flajšman (Author), Andrej Taranenko (Mentor), Polona Pavlič (Co-mentor)

Abstract

Naj bosta $n$ in $k$ naravni števili in $n geq k$. To diplomsko delo predstavlja nov razred grafov $H(n,k)$, ki vsebuje hiperkocke ter Johnsonove in Kneserjeve grafe kot njegove podgrafe. V prvem poglavju so povzeti osnovni pojmi iz teorije grafov, v drugem delu pa bodo predstavljeni nekateri rezultati vezani na družino $H(n,k)$. Na primer, $H(n,k)$ ima maksimalno povezanost $(n nad k)$, $H(n,k)$ je Hamiltonov, če je k liho število ter je sestavljen iz dveh izomorfnih povezanih komponent, če je k sodo število.

Keywords

teorija grafov;hiperkocke;hamiltonovi grafi;Johnsonovi grafi;Kneserjevi grafi;diplomska dela;

Data

Language:	Slovenian
Year of publishing:	2016
Typology:	2.11 - Undergraduate Thesis
Organization:	UM FNM - Faculty of Natural Sciences and Mathematics
Publisher:	[N. Flajšman]
UDC:	519.17(043.2)
COBISS:	22569224
Views:	1158
Downloads:	81
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Class of graphs H(n,k)
Secondary abstract:	Let $n$ and $k$ be positive integers and $ geq k$. This Graduation Thesis represents a new class of graphs $H(n,k)$, which contains hypercubes, Johnson and Kneser graphs as its subgraphs. The first part summarizes the basic concepts of graph theory, while the second part will present some of the results linked to the family $H(n,k)$. For example, $H(n,k)$ has the maximum connectivity $(n choose k)$, $H(n,k)$ is hamiltonian if k is an odd number, and it consists of two isomorphic connected components if $k$ is even.
Secondary keywords:	graph theory;hypercubes;hamiltonian graphs;Johnson graphs;Kneser graphs;theses;
Type (COBISS):	Undergraduate thesis
Thesis comment:	Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Pages:	38 f.
ID:	9154761