Název: Algebraické, strukturální a výpočetní vlastnosti geometrických reprezentací grafů
Překlad názvu: Algebraic, Structural, and Complexity Aspects of Geometric Representations of Graphs
Autoři: Zeman, Peter ; Klavík, Pavel (vedoucí práce) ; Nešetřil, Jaroslav (oponent)
Typ dokumentu: Diplomové práce
Rok: 2016
Jazyk: eng
Abstrakt: Title: Algebraic, Structural and Complexity Aspects of Geometric Representations of Graphs Author: Peter Zeman Department: Computer Science Institute Supervisor: RNDr. Pavel Klavík Supervisor's e-mail: klavik@iuuk.mff.cuni.cz Keywords: automorphism groups, interval graphs, circle graphs, comparability graphs, H-graphs, recognition, dominating set, graph isomorphism, maximum clique, coloring Abstract: We study symmetries of geometrically represented graphs. We describe a tech- nique to determine the automorphism group of a geometrically represented graph, by understanding the structure of the induced action on all geometric representations. We prove that interval graphs have the same automorphism groups as trees, and for a given interval graph, we construct a tree with the same automorphism group which answers a question of Hanlon [Trans. Amer. Math. Soc 272(2), 1982]. For permutation and circle graphs, we give an inductive characterization by semidirect and wreath prod- ucts. We also prove that every abstract group can be realized by the automorphism group of a comparability graph/poset of the dimension at most four. We also study H-graphs, introduced by Biró, Hujter, and Tuza in 1992. Those are intersection graphs of connected subgraphs of a subdivision of a graph H. This thesis is the first comprehensive...
Klíčová slova: geometrické reprezentace grafů; grupy automorfismů; průnikové reprezentace; rozšiřování částečných reprezentací; automorphism groups; geometric representations of graphs; intersection representations; partial representation extension

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/83134

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-352783


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Diplomové práce