Název:
Hrací varianty značkování grafů
Překlad názvu:
Game variants of graph labeling
Autoři:
Jedličková, Nikola ; Šámal, Robert (vedoucí práce) ; Fiala, Jiří (oponent) Typ dokumentu: Bakalářské práce
Rok:
2017
Jazyk:
slo
Abstrakt: [eng][cze] A graph labeling on a graph G is a mapping from the vertex set or the edge set to a set of labels L ⊆ N ∪ {0}. We will survey the existing results on graph labeling games. We also introduce a new type of labeling - ESD labeling and its game variant which was inspired by Tuza. An ESD labeling on a graph G is an injective mapping φ : V (G) → {1, . . . , n} such that for every two edges, the sum of the the labels on their endpoints is different. Apart from the question of existence of such labeling, we will examine game variant in which two players gradually build an ESD labeling. 1Značkovanie na grafe, nazývané tiež labeling, je zobrazenie z množiny vrcholov alebo hrán do množiny značiek L ⊆ N∪{0}. Popri prehl'ade doteraz známych hracích variant predstavíme aj nový typ labelingu - ESD labeling a s ním súvisiacu hraciu variantu, ktorá bola inšpirovaná článkom Tuzu. ESD labeling na grafe G je prosté zobrazenie φ : V (G) → {1, . . . , n}, kde pre každé dve rôzne hrany platí, že súčet značiek na ich koncových vrcholoch je rôzny. Okrem otázky existencie ESD labelingu sa budeme zaoberat' aj hracou variantou, kde labeling po- stupne vytvárajú dvaja hráči. 1
Klíčová slova:
graf;labeling;kombinatorické hry; graph;labeling;games