Razdaljno magično označevanje grafov

diplomsko delo

Nika Švaljek (Author), Aleksandra Tepeh (Mentor)

Abstract

Razdaljno magično označevanje grafa je bijekcija f : V -> {1, 2,..., n}, z lastnostjo, da obstaja taka konstanta k, da za vsako vozlišče x grafa velja, f(x_1) + f(x_2) + ...+ f(x_j) = k, kjer je y_i (i = 1,..., j) iz odprte okolice vozlišča x. Diplomsko delo obravnava razdaljno magično označevanje polnih dvodelnih in polnih tridelnih grafov. V prvem poglavju so predstavljeni osnovni pojmi teorije grafov s poudarkom na polnih večdelnih grafih in barvanjih grafa. V drugem delu najprej predstavimo potreben pogoj za obstoj razdaljno magičnega označevanja. Glavni rezultat tega poglavja je karakterizacija polnih dvodelnih in polnih tridelnih grafov, za katere obstaja razdaljno magično označevanje. Delo zaključimo s seznamom različnih družin grafov, za katere razdaljno magično označevanje ne obstaja.

Keywords

matematika;teorija grafov;razdalja;magično označevanje;k-regularni grafi;večdelni grafi;polni dvodelni grafi;polni tridelni grafi;diplomska dela;

Data

Language:	Slovenian
Year of publishing:	2013
Typology:	2.11 - Undergraduate Thesis
Organization:	UM FNM - Faculty of Natural Sciences and Mathematics
Publisher:	[N. Švaljek]
UDC:	51(043.2)
COBISS:	19770376
Views:	2036
Downloads:	165
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Distance magic labelings of graphs
Secondary abstract:	A magic distance labeling is a bijection f : V -> {1, 2,..., n} with the property that there is a constant k such that f(y_1) + f(y_2) +...+f(y_j) = k for every vertex x, where y_i (i =1,..., j) is the set of vertices adjacent to x. The graduation thesis investigates magic distance labelings of complete bipartite and complete tripartite graphs. In the first chapter basic concepts of graph theory are presented with the emphasis on complete multipartite graphs and colourings of graphs. In the second part we first present a necessary condition for the existence of a magic distance labeling. The main result in this chapter is a caracterization of complete bipartite and complete tripartite graphs that admit magic distance labeling. We conclude by listing various families of graphs, all of which have no distance magic labeling.
Secondary keywords:	graph theory;magic distance labeling;k - regular graphs;multipartite graphs;complete bipartite graphs;complete tripartite graphs;
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.
ID:	8725951