Vertex-transitive Supergraphs
| Název práce v češtině: | Vrcholově tranzitivní nadgrafy |
|---|---|
| Název v anglickém jazyce: | Vertex-transitive Supergraphs |
| Klíčová slova: | teorie grafů|symetrie|automorfismy|výpočetní zložitost|grafový isomorfizmus |
| Klíčová slova anglicky: | graph theory|symmetry|automorphisms|computational complexity|graph isomorphism |
| Akademický rok vypsání: | 2018/2019 |
| Typ práce: | bakalářská práce |
| Jazyk práce: | angličtina |
| Ústav: | Katedra aplikované matematiky (32-KAM) |
| Vedoucí / školitel: | doc. RNDr. Martin Tancer, Ph.D. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 30.03.2019 |
| Datum zadání: | 16.04.2019 |
| Datum potvrzení stud. oddělením: | 18.04.2019 |
| Datum a čas obhajoby: | 10.09.2021 09:00 |
| Datum odevzdání elektronické podoby: | 26.05.2021 |
| Datum odevzdání tištěné podoby: | 27.05.2021 |
| Datum proběhlé obhajoby: | 10.09.2021 |
| Oponenti: | RNDr. Radek Hušek, Ph.D. |
| Zásady pro vypracování |
| Nechť G je graf, jak velký musí být vrcholově tranzitivní graf takový, že G je indukovaným podgrafem H? Cílem práce bude studovat otázku výše, tedy popsat nějaké konstrukce, kdy zmiňovaný graf H není příliš velký, a to jak v obecnosti nebo pro G z některých speciálních tříd (například bipartitní grafy). Zároveň se zájemce pokusí o dolní odhady.
Otázka je do značné míry motivovaná vztahem mezi složitostí problému grafového izomorfismu a problému rozpoznávání vrcholově tranzitivních grafů. Cílem práce by tedy zároveň bylo nastudovat zázemí v této oblasti a dobře ho v práci vysvětlit. |
| Seznam odborné literatury |
| V. N. Zemlyachenko, N. M. Korneenko and R. I. Tyshkevich. Graph isomorphism problem. Journal of Soviet Mathematics, 29(4), 1426-1481, 1985.
G. L. Miller. Graph isomorphism, general remarks. Journal of Computer and System Sciences, 18(2), 128-142, 1979. M. J. Colbourn and C. J. Colbourn. Graph isomorphism and self-complementary graphs. ACM SIGACT News, 10(1), 25-29, 1978. P. Hamburger, A. Por and M. Walsh. Kneser representations of graphs. SIAM Journal on Discrete Mathematics, 23(2), 1071-1081, 2009. Další literatura bude dodaná podle potřeby. |