Graph Covers

• Název práce v češtině: Nakrývání grafů
• Název v anglickém jazyce: Graph Covers
• Klíčová slova: graf|multigraf|půlhrana|jednoduchý graf|nakrytí grafu
• Klíčová slova anglicky: graph|multigraph|semi-edge|simple graph|graph cover
• Akademický rok vypsání: 2024/2025
• Typ práce: diplomová práce
• Jazyk práce: angličtina
• Ústav: Katedra aplikované matematiky (32-KAM)
• Vedoucí / školitel: prof. RNDr. Jan Kratochvíl, CSc.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 08.01.2025
• Datum zadání: 08.01.2025
• Datum potvrzení stud. oddělením: 08.01.2025
• Datum a čas obhajoby: 03.06.2025 08:00
• Datum odevzdání elektronické podoby: 30.04.2025
• Datum odevzdání tištěné podoby: 30.04.2025
• Datum proběhlé obhajoby: 03.06.2025
• Oponenti: prof. RNDr. Roman Nedela, DrSc.

Zásady pro vypracování

Předmětem diplomové práce je zkoumání nakrývání multigrafů s půlhranami jednoduchými grafy. Nakrytí grafů je pojem motivovaný z topologie nakrytími topologických prostorů. Student se seznámí s definicí nakrytí a dostupnou literaturou. Následně bude zkoumat otázky existence tzv. zobecněných snarků, tedy jednoduchých grafů, které nakrývají jeden předepsaný graf a nenakrývají druhý. Pro dva multigrafy A a B řekneme, že A je silnější než B, pokud každý jednoduchý graf, který nakrývá graf A, také nakrývá graf B. V tomto smyslu každý (A,B)-snark, definovaný jako jednoduchý graf, který nakrývá A, ale nenakrývá B, je svědkem, že A není silnější než B. Cílem diplomové práce je studovat hypotézu, že graf A bez půlhran je silnější než graf B právě tehdy, když A nakrývá B. Platnost této hypotézy zatím byla ověřena jen pro několik speciálních případů (A je bipól, nebo B je trivalentní graf na jednom vrcholu). Úkolem je prověřit tuto hypotézu pro větší třídy grafů (např. dvouvrcholové grafy A se smyčkami, nebo jednovrcholové grafy B stupně vyššího než 3).

Seznam odborné literatury

Jiří Fiala, Michaela Seifrtová: A novel approach to covers of multigraphs with semi-edges, Discussiones Mathematicae Graph Theory, 2025 early access, https://doi.org/10.7151/dmgt.2540
Aleksandr Malnič, Roman Nedela and Martin Škoviera, Lifting graph automorphisms by voltage assignments, European J. Combin. 21 (2000) 927–947, https://doi.org/10.1006/eujc.2000.0390
Jan Bok, Jiří Fiala, Nikola Jedličková, Jan Kratochvíl, Michaela Seifrtová: Computational complexity of covering disconnected multigraphs. Discret. Appl. Math. 359 (2024) 229-243, https://doi.org/10.1016/j.dam.2024.07.035
Jan Kratochvíl, Roman Nedela: Graph covers and generalized snarks, in: Proceedings of EUROCOMB 2023, Masaryk University Press (2023) 681-687, https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-094
a případně další časopisecká literatura podle doporučení vedoucího

Předběžná náplň práce

(Multi)graf A je silnější než (multi)graf B, pokud každý jednoduchý graf, který nakrývá A, také nakrývá B. Byla vyslovena hypotéza, že pokud A nemá půlhrany, pak A je silnější než B právě tehdy, když A nakrývá B. Cílem je prověřit tuto hypotézu pro netriviální třídy grafů.

Předběžná náplň práce v anglickém jazyce

A (multi)graph A is stronger than a (multi)graph B if every simple graph that covers A also covers B. It has been conjectured that if A has no semi-edges, then A is stronger than B if and only if A covers B. The goal is to check this conjecture for nontrivial classes of graphs.