Graph labelings with restrictive conditions
Graph labelings with restrictive conditions
Dátum
Szerzők
Halász, Veronika
Folyóirat címe
Folyóirat ISSN
Kötet címe (évfolyam száma)
Kiadó
Absztrakt
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.
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.
Leírás
Kulcsszavak
Channel assignment, Csatornakijelölés, Radio labeling, Tree, Unit interval graph, Mixed integer linear programming, Edge decompositions, Rádiócímkézés, Fa, Egységintervallum-gráf, Vegyes lineáris-egészértékű programozás, Éldekompozíciók