Graph Covers
Nakrývání grafů
diploma thesis (DEFENDED)

View/ Open
Permanent link
http://hdl.handle.net/20.500.11956/199297Identifiers
Study Information System: 279480
Collections
- Kvalifikační práce [11502]
Author
Advisor
Referee
Nedela, Roman
Faculty / Institute
Faculty of Mathematics and Physics
Discipline
Mathematical Structures
Department
Department of Applied Mathematics
Date of defense
3. 6. 2025
Publisher
Univerzita Karlova, Matematicko-fyzikální fakultaLanguage
English
Grade
Excellent
Keywords (Czech)
graf|multigraf|půlhrana|jednoduchý graf|nakrytí grafuKeywords (English)
graph|multigraph|semi-edge|simple graph|graph coverNakrytí je lokálně bijektivní homomorfismus z grafu A do souvislého grafu B. Ví- cenásobné hrany, smyčky a půlhrany jsou připouštěny, ale hypotéza Strong Dichotomy Conjecture tvrdí, že pro fixní souvislý graf H, výpočetní složitost otázky zda G nakrývá H je již plně určena jednoduchými grafy G. Následující kvaziuspořádání bylo zavedeno: Souvislý graf A je silnější než souvislý graf B, pokud každý jednoduchý graf G nakrývající A také nakrývá B. V roce 2022 Kratochvíl vyslovil hypotézu, že když A nemá půlhrany, pak A je silnější než B právě, když A nakrývá B. Kratochvíl a Nedela tuto hypotézu dokázali v případech kdy B je kubický graf na jednom vrcholu nebo A je dipól bez smyček a půlhran. My tuto relaci plně charakterizujeme pro A na jednom vrcholu, dipól bez půlhran, neregulární dipól a, částečně, obecný dipól. Tím pro tyto případy speciálně ověříme Kra- tochvílovu hypotézu. Nové metody jsou v průběhu vyvinuty a my představíme jejich důsledky pro počítání disjunktních perfektních párování v jednoduchých regulárních gra- fech.
A covering projection is a locally bijective homomorphism from a graph A to a con- nected graph B. Multiple edges, loops and semi-edges are considered but the Strong Dichotomy Conjecture asserts that for a fixed connected graph H, the complexity of de- termining whether G covers H is already dictated by simple graphs G. A quasi-order was introduced: A connected graph A is stronger than a connected graph B if every simple graph covering A also covers B. In 2022, Kratochvíl conjectured that if A has no semi-edges, then A is stronger than B iff A covers B. Kratochvíl & Nedela proved this conjecture when B is a cubic one-vertex graph, or A is a dipole with no loops and no semi-edges. We describe this relation fully for A being a one-vertex graph, a dipole with no semi- edges, an irregular dipole, and, partially, a general dipole. Consequently, we verify the conjecture in such cases. New methods are developed and their impact on counting disjoint perfect matchings in simple regular graphs is presented.