Graph labelings with restrictive conditions

Abstract

Elméleti munkám során egy speciális csúcscímkézéssel foglalkoztam két gráfosztályra vonatkozóan, méghozzá a fák és az egységintervallum-gráfok L(j, j − 1, ..., 2, 1)–címkézésével. A vizsgált paraméterek már ismertek voltak az L(2, 1)− és az L(3, 2, 1)−címkézések esetén, én ezeket általánosítottam tetszőleges j természetes számra. Az elméleti kutatás mellett gyakorlati szempontokból is vizsgáltam a problémát. Ezen vizsgálatokhoz a vegyes egészértékű-lineáris programozást választottam módszerként. A távolság szerint korlátozott címkézés problémáját formalizáltam az egészértékű programozás nyelvén. Ez lehetővé tette számomra néhány összehasonlítás elvégzését a gráfelméleti modell és a frekvenciakiosztási probléma egy precízebb modellje között. Ez utóbbit én definiáltam. Az értekezés utolsó fejezete éldekompozíciókról szól. A fő eredmény egy a közelmúltban definiált probléma megoldása. During my theoretical work I dealt with a special vertex labeling of two graph classes, namely the L(j, j − 1, ..., 2, 1)−labeling of trees and unit interval graphs. The studied values were known for L(2, 1)− and L(3, 2, 1)−labelings, I generalized them for arbitrary natural number j. In addition to the theoretical studies I examined the problem in practical terms. I chose the mixed integer linear programming for these studies. I formalized the distance-constrained labeling problem in terms of integer programming. This allowed me to make some comparisons between the graph model and a bit more precise model of the frequency assignment problem that was introduced by me. The last section of the thesis is about edge-decomposition. The main result here is the solution of a quite recently defined problem.