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: | prof. RNDr. Martin Tancer, Ph.D. |
Řešitel: | skrytý![]() |
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. |