Palično število grafa

diplomsko delo

Barbara Mikelj (Author), Janja Jerebic (Mentor)

Abstract

Diplomsko delo je sestavljeno iz šestih poglavij. Uvodu sledi poglavje z osnovnimi pojmi teorije grafov, ki so uporabljeni v diplomskem delu. V drugem poglavju so predstavljene osnovne lastnosti igre s palicami in definirani pojmi palično število, optimalno palično število, palična poteza, dvopalična poteza, odstranitvena poteza, razporeditev na grafu, dobra (multi) razporeditev na grafu, cilj poteze in izid razporeditve. V tretjem poglavju sta podana palično in optimalno palično število poti, ciklov in spojev grafov. Prikazani so tudi primeri razporeditve za nekatere poti in cikle manjšega reda. V četrtem poglavju sta podani palično in optimalno palično število kartezičnega produkta polnih grafov ter določeni spodnja in zgornja meja paličnega števila kartezičnega produkta $G \square K_n$, ki temelji na dvopaličnem številu. V petem poglavju je določeno palično število hiperkock. Ob tem sta določeni tudi spodnja in zgornja meja za optimalno palično število hiperkock. V šestem poglavju so določene spodnje in zgornje meje za palično in optimalno palično število grafov z majhnim premerom.

Keywords

matematika;grafi;palično število;teorija grafov;igre;diplomska dela;

Data

Language:	Slovenian
Year of publishing:	2011
Source:	Maribor
Typology:	2.11 - Undergraduate Thesis
Organization:	UM FNM - Faculty of Natural Sciences and Mathematics
Publisher:	[B. Mikelj]
UDC:	51(043.2)
COBISS:	18751752
Views:	1678
Downloads:	71
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	GRAPH PEGGING NUMBER
Secondary abstract:	The graduation thesis consists of six sections. After introduction the basic concepts of the Graph Theory used in the thesis are presented. In the second section the basic properties of pegging are introduced and the definitions of pegging number, optimal pegging number, pegging move, pebbling move, removal move, distribution on a graph, proper (multi) distribution on a graph, target vertex and reach of a distribution are given. In the third section the pegging and the optimal pegging number of paths, cycles and joins are given and some examples of distributions for paths and cycles of small order are presented. In the fourth section the pegging and the optimal pegging number of the Cartesian product of complete graphs are determined. Moreover, the lower and the upper bound for the pegging number of the Cartesian product $G \square K_n$, which are based on the pebbling number, are established. In the fifth section the pegging number of the hypercubes and also the lower and the upper bound for the optimal pegging number of the hypercubes are determined. In the sixth section the lower and the upper bound for the pegging and the optimal pegging number of graphs of small diameter are presented.
Secondary keywords:	graph theory;games on graphs;graph pegging;pegging number;
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:	43 f.
Keywords (UDC):	mathematics;natural sciences;naravoslovne vede;matematika;mathematics;matematika;
ID:	19598