Tato práce se věnuje \vyraz{L(i,j,k)}-ohodnocení grafů, se speciálním zaměřením na \vyraz{L(3,2,1)}-ohodnocení, a hledá minimální rozpětí, případně horní či dolní odhady tohoto rozpětí, kterým lze daný graf ohodnotit. Pro \vyraz{i, j, k}, \vyraz{L(i,j,k)}-ohodnocením grafu \vyrazG rozumíme přiřazení celých nezáporných čísel vrcholům grafu \vyrazG tak, že sousední vrcholy musejí být ohodnoceny hodnotami s rozdílem aspoň \vyrazi, vrcholy ve vzdálenosti \vyraz2 musejí být ohodnoceny hodnotami s rozdílem aspoň \vyrazj a vrcholy ve vzdálenosti \vyraz3 musejí být ohodnoceny hodnotami s rozdílem aspoň \vyrazk. V první části práce jsou shrnuty již známé výsledky z oblasti základních tříd grafů. Vlastní výzkum se zaměřuje na \vyraz{L(i,j,k)}-ohodnocení zobecněných Petersenových grafů.
Annotation in English
This bachelor thesis deals with \vyraz{L(i,j,k)}-labelling of graphs with special focus on \vyraz{L(3,2,1)}-labelling, and searches for minimal spread or upper and lower bounds on this spread by which the graph can be evaluated. For integers \vyraz{i, j, k}, \vyraz{L(i,j,k)}-labelling of a graph \vyrazG is a mapping of non-negative integers to vertices of \vyrazG such that the difference between the values of neighbouring vertices has to be at least \vyrazi, the difference between the values of vertices at distance \vyraz2 has to be at least \vyrazj, and the difference between the values of vertices at distance \vyraz3 has to be at least \vyrazk. Already known results for basic families of graphs are summarized in the first part of the thesis. Our own research concentrates on \vyraz{L(i,j,k)}-labelling of generalized Petersen graphs.
Tato práce se věnuje \vyraz{L(i,j,k)}-ohodnocení grafů, se speciálním zaměřením na \vyraz{L(3,2,1)}-ohodnocení, a hledá minimální rozpětí, případně horní či dolní odhady tohoto rozpětí, kterým lze daný graf ohodnotit. Pro \vyraz{i, j, k}, \vyraz{L(i,j,k)}-ohodnocením grafu \vyrazG rozumíme přiřazení celých nezáporných čísel vrcholům grafu \vyrazG tak, že sousední vrcholy musejí být ohodnoceny hodnotami s rozdílem aspoň \vyrazi, vrcholy ve vzdálenosti \vyraz2 musejí být ohodnoceny hodnotami s rozdílem aspoň \vyrazj a vrcholy ve vzdálenosti \vyraz3 musejí být ohodnoceny hodnotami s rozdílem aspoň \vyrazk. V první části práce jsou shrnuty již známé výsledky z oblasti základních tříd grafů. Vlastní výzkum se zaměřuje na \vyraz{L(i,j,k)}-ohodnocení zobecněných Petersenových grafů.
Annotation in English
This bachelor thesis deals with \vyraz{L(i,j,k)}-labelling of graphs with special focus on \vyraz{L(3,2,1)}-labelling, and searches for minimal spread or upper and lower bounds on this spread by which the graph can be evaluated. For integers \vyraz{i, j, k}, \vyraz{L(i,j,k)}-labelling of a graph \vyrazG is a mapping of non-negative integers to vertices of \vyrazG such that the difference between the values of neighbouring vertices has to be at least \vyrazi, the difference between the values of vertices at distance \vyraz2 has to be at least \vyrazj, and the difference between the values of vertices at distance \vyraz3 has to be at least \vyrazk. Already known results for basic families of graphs are summarized in the first part of the thesis. Our own research concentrates on \vyraz{L(i,j,k)}-labelling of generalized Petersen graphs.
Cílem této práce je studium zobecněných ohodnocení grafů distančního typu, konkrétně \vyraz{L(3,2,1)} - ohodnocení a jeho variant. Úkolem je shrnout a setřídit základní poznatky z této oblasti a nalézt horní a dolní meze pro příslušná ohodnocení některých tříd grafů s repetitivní strukturou, např. zobecněných Petersenových grafů.
Research Plan
Cílem této práce je studium zobecněných ohodnocení grafů distančního typu, konkrétně \vyraz{L(3,2,1)} - ohodnocení a jeho variant. Úkolem je shrnout a setřídit základní poznatky z této oblasti a nalézt horní a dolní meze pro příslušná ohodnocení některých tříd grafů s repetitivní strukturou, např. zobecněných Petersenových grafů.
Recommended resources
T. Calamoneri: Optimal \vyraz{L(d1,d2,1)
-labeling of eight-regular graphs.
Inform. Pross. Let. 113 (2013), 361-364.
S. Das, S.C. Ghosh, S. Nandi: Optimal \vyraz{L(3,2,1)
-labeling of triangular lattice.
Disc. Appl. Math. 228 (2017), 32-40.
J. L. Gross, J. Yellen: Handbook of graph theory. Reading (Massachusetts):
CRC Press LLC, 2004, ISBN-13 978-1584880905.
X. Zhang: Characterization results for the \vyraz{L(2,1,1)
-labeling problem on trees.
Discuss. Math. Graph Theory 37 (2017), 611-622.
Recommended resources
T. Calamoneri: Optimal \vyraz{L(d1,d2,1)
-labeling of eight-regular graphs.
Inform. Pross. Let. 113 (2013), 361-364.
S. Das, S.C. Ghosh, S. Nandi: Optimal \vyraz{L(3,2,1)
-labeling of triangular lattice.
Disc. Appl. Math. 228 (2017), 32-40.
J. L. Gross, J. Yellen: Handbook of graph theory. Reading (Massachusetts):
CRC Press LLC, 2004, ISBN-13 978-1584880905.
X. Zhang: Characterization results for the \vyraz{L(2,1,1)
-labeling problem on trees.
Discuss. Math. Graph Theory 37 (2017), 611-622.