Original title:
Hrací varianty značkování grafů
Translated title:
Game variants of graph labeling
Authors:
Jedličková, Nikola ; Šámal, Robert (advisor) ; Fiala, Jiří (referee) Document type: Bachelor's theses
Year:
2017
Language:
slo Abstract:
[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
Keywords:
graph;labeling;games; graf;labeling;kombinatorické hry
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/90463