Cykl podwójna osłona
Czy każdy graf bezmostkowy ma zbiór wielokrotny cykli pokrywających każdą krawędź dokładnie dwa razy?
W matematyce opartej na teorii grafów podwójne pokrycie cyklu to zbiór cykli w grafie nieskierowanym , które razem obejmują każdą krawędź wykresu dokładnie dwa razy. Na przykład dla dowolnego wykresu wielościennego ściany wypukłego wielościanu reprezentującego wykres zapewniają podwójne pokrycie wykresu: każda krawędź należy do dokładnie dwóch ścian.
Jest to nierozwiązany problem, postawiony przez George'a Szekeresa i Paula Seymoura i znany jako hipoteza podwójnego pokrycia cyklu , czy każdy graf bez mostów ma podwójne pokrycie cyklu. Hipotezę można równoważnie sformułować w kategoriach osadzania grafu iw tym kontekście jest ona również znana jako hipoteza osadzania kołowego .
Sformułowanie
Zwykłe sformułowanie hipotezy podwójnego pokrycia cyklu pyta, czy każdy nieskierowany graf bez mostków ma taki zbiór cykli , że każda krawędź grafu jest zawarta w dokładnie dwóch cyklach. Wymóg, aby graf był bezmostkowy, jest oczywistym warunkiem koniecznym istnienia takiego zestawu cykli, ponieważ mostek nie może należeć do żadnego cyklu. Zbiór cykli spełniających warunek hipotezy podwójnego pokrycia cyklu nazywamy podwójnym pokryciem cyklu . Niektóre wykresy, takie jak wykresy cykli i wykresy kaktusów bez mostków , można pokryć tylko przy użyciu tego samego cyklu więcej niż jeden raz, więc ten rodzaj powielania jest dozwolony w przypadku podwójnego okładki cyklu.
Redukcja do snarków
Snark jest szczególnym przypadkiem grafu bezmostkowego, mającym dodatkowe właściwości , takie jak każdy wierzchołek ma dokładnie trzy przypadkowe krawędzie (to znaczy, że graf jest sześcienny ) i że nie jest możliwe podzielenie krawędzi grafu na trzy idealne dopasowania ( to znaczy, graf nie ma 3- krawędziowego kolorowania i zgodnie z twierdzeniem Vizinga ma indeks chromatyczny 4). Okazuje się, że snarki stanowią jedyny trudny przypadek hipotezy podwójnej pokrywy cyklu: jeśli hipoteza jest prawdziwa dla snarków, jest prawdziwa dla każdego wykresu.
Jaeger (1985) zauważa, że w każdym potencjalnym minimalnym kontrprzykładzie dla hipotezy podwójnego pokrycia cyklu wszystkie wierzchołki muszą mieć trzy lub więcej incydentnych krawędzi. Ponieważ wierzchołek z incydentną tylko jedną krawędzią tworzy most, podczas gdy jeśli dwie krawędzie stykają się z wierzchołkiem, można je skrócić, tworząc mniejszy graf, tak że każde podwójne pokrycie mniejszego grafu rozciąga się na jedno z oryginalnego wykresu. Z drugiej strony, jeśli wierzchołek v ma cztery lub więcej incydentnych krawędzi, można „oddzielić” dwie z tych krawędzi, usuwając je z grafu i zastępując je pojedynczą krawędzią łączącą ich dwa pozostałe punkty końcowe, zachowując przy tym brak mostków wynikowy wykres. Ponownie podwójne pokrycie grafu wynikowego można w prosty sposób rozszerzyć na podwójne pokrycie grafu pierwotnego: każdy cykl oddzielonego grafu odpowiada albo cyklowi grafu pierwotnego, albo parze cykli spotykających się w punkcie w . Zatem każdy minimalny kontrprzykład musi być sześcienny. Ale jeśli graf sześcienny może mieć krawędzie trójkolorowe (powiedzmy z kolorami czerwonym, niebieskim i zielonym), to podgraf o krawędziach czerwonych i niebieskich, podgraf o krawędziach niebieskich i zielonych oraz podgraf o krawędziach czerwonych i zielonych każdy tworzy zbiór rozłącznych cykli, które razem pokrywają dwukrotnie wszystkie krawędzie grafu. Dlatego każdy minimalny kontrprzykład musi być grafem sześciennym bez mostków, którego nie można pokolorować trzema krawędziami, czyli snark.
Redukowalne konfiguracje
Jednym z możliwych ataków na problem podwójnego pokrycia cyklu byłoby wykazanie, że nie może istnieć minimalny kontrprzykład, poprzez udowodnienie, że dowolny graf zawiera redukowalną konfigurację , podgraf, który można zastąpić mniejszym podgrafem w sposób, który zachowałby istnienie lub brak podwójnej osłony cyklu. Na przykład, jeśli wykres sześcienny zawiera trójkąt, transformacja Δ-Y zastąpi trójkąt pojedynczym wierzchołkiem; dowolne podwójne pokrycie cyklu mniejszego wykresu można rozszerzyć z powrotem do podwójnego pokrycia cyklu oryginalnego wykresu sześciennego. Dlatego minimalnym kontrprzykładem dla hipotezy podwójnej pokrywy cyklu musi być graf bez trójkątów , wykluczający niektóre snarki, takie jak wykres Tietze , który zawiera trójkąty. Dzięki wyszukiwaniom komputerowym wiadomo, że każdy cykl o długości 11 lub mniejszej na grafie sześciennym tworzy redukowalną konfigurację, a zatem każdy minimalny kontrprzykład dla hipotezy podwójnego pokrycia cyklu musi mieć obwód co najmniej 12.
Niestety, nie jest możliwe udowodnienie hipotezy o podwójnym pokryciu cyklu przy użyciu skończonego zestawu redukowalnych konfiguracji. Każda redukowalna konfiguracja zawiera cykl, więc dla każdego skończonego zbioru S redukowalnych konfiguracji istnieje taka liczba γ, że wszystkie konfiguracje w zbiorze zawierają cykl o długości co najwyżej γ. Istnieją jednak snarki o dowolnie wysokim obwodzie, to znaczy z dowolnie wysokimi granicami długości ich najkrótszego cyklu. Snark G o obwodzie większym niż γ nie może zawierać żadnej konfiguracji w zbiorze S , więc redukcje w S nie są wystarczająco silne, aby wykluczyć możliwość, że G może być minimalnym kontrprzykładem.
Przypuszczenie o okrągłym osadzeniu
Jeśli graf ma podwójną pokrywę cykliczną, cykle pokrywy można wykorzystać do utworzenia 2-komórek grafu osadzonych na dwuwymiarowym kompleksie komórek . W przypadku grafu sześciennego zespół ten zawsze tworzy rozmaitość . Mówi się, że wykres jest osadzony kołowo na rozmaitości, ponieważ każda ściana osadzania jest prostym cyklem na wykresie. Jednak podwójne pokrycie cyklu wykresu o stopniu większym niż trzy może nie odpowiadać osadzeniu na rozmaitości: kompleks komórek utworzony przez cykle pokrycia może mieć topologię niezróżnicowaną w swoich wierzchołkach. Hipoteza osadzania kołowego lub hipoteza silnego osadzania stwierdza, że każdy graf podwójnie spójny ma osadzanie kołowe na rozmaitości. Jeśli tak, to wykres ma również podwójne pokrycie cykliczne, utworzone przez ściany osadzania.
W przypadku grafów sześciennych bikonektywność i brak mostków są równoważne. Dlatego hipoteza o okrągłym osadzeniu jest wyraźnie co najmniej tak samo silna jak hipoteza o podwójnym pokryciu cyklu. Okazuje się jednak, że nie jest silniejszy. Jeśli wierzchołki grafu G zostaną rozszerzone w celu utworzenia wykresu sześciennego, który jest następnie osadzony kołowo, a rozwinięcia zostaną cofnięte przez skrócenie dodanych krawędzi, wynikiem będzie okrągłe osadzenie samego G. Dlatego też, jeśli hipoteza podwójnego pokrycia cyklu jest prawdziwa, każdy graf dwupołączony ma osadzenie kołowe. Oznacza to, że hipoteza podwójnego pokrycia cyklu jest równoważna hipotezie o okrągłym osadzeniu, mimo że podwójne pokrycie cyklu i okrągłe osadzanie nie zawsze są tym samym.
Jeśli istnieje okrągłe osadzenie, może nie znajdować się na powierzchni minimalnego rodzaju: Nguyen Huy Xuong opisał podwójnie połączony graf toroidalny , którego żadne z okrągłych osadzeń nie leży na torusie.
Silniejszą wersją hipotezy o osadzeniu kołowym, która również była rozważana, jest przypuszczenie, że każdy graf dwuspójny ma osadzanie kołowe na orientowalnej rozmaitości . Jeśli chodzi o hipotezę podwójnego pokrycia cyklu, jest to równoważne przypuszczeniu, że istnieje podwójne pokrycie cyklu i orientacja dla każdego z cykli w pokryciu, taka że dla każdej krawędzi e dwa cykle pokrywające e są zorientowane w przeciwnych kierunkach przez e .
rozważono również wzmocnienia przypuszczenia, które obejmują kolorystykę cykli w okładce. Najsilniejszym z nich jest przypuszczenie, że każdy graf bezmostkowy ma kołowe osadzenie na orientowalnej rozmaitości, w której twarze mogą być 5-kolorowe. Jeśli to prawda, oznaczałoby to przypuszczenie WT Tutte , że każdy graf bez mostków ma nigdzie zero 5-flow .
Silniejszym typem osadzania niż osadzanie kołowe jest osadzanie wielościenne , osadzenie wykresu na powierzchni w taki sposób, że każda ściana jest prostym cyklem, a każde dwie przecinające się ściany robią to albo w jednym wierzchołku, albo w jednej krawędzi . (W przypadku wykresu sześciennego można to uprościć do wymogu, aby co dwie przecinające się ściany odbywały się na jednej krawędzi). Tak więc, w związku z redukcją hipotezy o podwójnym pokryciu cyklu do snarks, jest to interesujące badać wielościenne osadzenie snarków. Nie mogąc znaleźć takich osad, Branko Grünbaum przypuszczał, że one nie istnieją, ale Kochol ( 2009a , 2009b ) obalił hipotezę Grünbauma, znajdując snarka z osadzeniem wielościennym.
Zobacz także przypuszczenie kolorowania Petersena .
Notatki
- Fleischner, Herbert (1976), "Eine gemeinsame Basis für die Theorie der Eulerschen Graphen und den Satz von Petersen", Monatshefte für Mathematik , 81 (4): 267–278, doi : 10.1007/BF01387754 , S2CID 118767538 .
- Huck, A. (2000), „Redukowalne konfiguracje dla hipotezy podwójnej pokrywy cyklu”, Discrete Applied Mathematics , 99 (1–3): 71–90, doi : 10.1016 / S0166-218X (99) 00126-2 .
- Jaeger, F. (1985), „Przegląd hipotezy podwójnej okładki cyklu”, Annals of Discrete Mathematics 27 - Cycles in Graphs , North-Holland Mathematics Studies, tom. 27, s. 1–12, doi : 10.1016/S0304-0208(08)72993-1 .
- Kochol, Martin (1996), „Snarks bez małych cykli”, Journal of Combinatorial Theory , seria B (1 wyd.), 67 (1): 34–47, doi : 10.1006 / jctb.1996.0032 .
- Kochol , Martin (2009a ) 5417, s. 319–323 .
- Kochol, Martin (2009b), „Wielościenne osadzenie snarków na powierzchniach orientowalnych”, Proceedings of the American Mathematical Society (5 wyd.), 137 (5): 1613–1619, doi : 10.1090 / S0002-9939-08-09698- 6 .
- Seymour, PD (1980), „Rozłączne ścieżki na wykresach”, Discrete Mathematics , 29 (3): 293–309, doi : 10.1016/0012-365X (80) 90158-2 .
- Szekeres, G. (1973), „Wielościenny rozkład grafów sześciennych”, Biuletyn Australijskiego Towarzystwa Matematycznego , 8 (3): 367–387, doi : 10.1017 / S0004972700042660 .
- Zhang, Cun-Quan (1997), Przepływy liczb całkowitych i okładki cykli wykresów , CRC Press, ISBN 978-0-8247-9790-4 .
- Zhang, Cun-Quan (2012), Circuit Double Cover of Graphs , Cambridge University Press, ISBN 978-0-5212-8235-2 .