Distance magic labelings of graphs

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 grafifih 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.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