Pełen wdzięku etykietowanie

Zgrabna etykieta. Etykiety wierzchołków są w kolorze czarnym, etykiety krawędzi w kolorze czerwonym.

W teorii grafów wdzięczne etykietowanie grafu z m $krawędziami$ jest etykietowaniem jego wierzchołków pewnym podzbiorem liczb całkowitych od 0 do $m włącznie, tak że żadne$ dwa wierzchołki nie mają wspólnej etykiety, a każda krawędź jest jednoznacznie identyfikowana przez bezwzględną różnicę między jego punktami końcowymi, tak że ta wielkość leży między 1 a $m$ włącznie. Graf, który dopuszcza wdzięczne etykietowanie, nazywany jest grafem pełnym wdzięku .

Nazwa „wdzięczne etykietowanie” pochodzi od Solomona W. Golomba ; ten typ etykietowania został pierwotnie nazwany etykietowaniem β przez Alexandra Rosę w artykule z 1967 roku na temat etykietowania wykresów.

Głównym przypuszczeniem w teorii grafów jest przypuszczenie wdzięcznego drzewa lub przypuszczenie Ringela-Kotziga , nazwane na cześć Gerharda Ringela i Antona Kotziga , a czasem w skrócie GTC . Zakłada, że wszystkie drzewa są pełne wdzięku. Jest to nadal otwarta hipoteza, chociaż pokrewna, ale słabsza hipoteza, znana jako „hipoteza Ringela”, została częściowo udowodniona w 2020 roku. Kotzig nazwał kiedyś próbę udowodnienia tej hipotezy „chorobą”.

Inną słabszą wersją etykietowania z wdziękiem jest etykietowanie z wdziękiem , w którym wierzchołki można oznaczyć za pomocą pewnego podzbioru liczb całkowitych na $[0, m + 1]$ tak, że żadne dwa wierzchołki nie dzielą etykiety, a każda krawędź jest jednoznacznie identyfikowana przez bezwzględna różnica między jej punktami końcowymi (wielkość ta leży na $[1, m + 1]$ ).

Innym przypuszczeniem w teorii grafów jest przypuszczenie Rosy , nazwane na cześć Aleksandra Rosy , które mówi, że wszystkie trójkątne kaktusy są pełne wdzięku lub prawie pełne wdzięku.

pełen wdzięku wykres o krawędziach od 0 do $m$ ma nie mniej niż ${\ Displaystyle \ lewo \ lceil {\ sqrt {3 m + {\ tfrac {9} {4}}}} \ prawo \ rfloor }$ wierzchołków, ze względu na rzadkie wyniki linijki . To przypuszczenie zostało zweryfikowane dla wszystkich grafów o krawędziach 213 lub mniejszej.

Pełen wdzięku graf z 27 krawędziami i 9 wierzchołkami

Wybrane wyniki

W swojej oryginalnej pracy Rosa udowodnił, że graf Eulera o liczbie krawędzi m ≡ 1 (mod 4) lub m ≡ 2 (mod 4) nie może być pełen wdzięku.
Również w swojej oryginalnej pracy Rosa udowodnił, że cykl C _n jest pełen gracji wtedy i tylko wtedy, gdy n ≡ 0 (mod 4) lub n ≡ 3 (mod 4).
Wszystkie wykresy ścieżek i wykresy gąsienicowe są pełne wdzięku.
Wszystkie wykresy homara z idealnym dopasowaniem są pełne wdzięku.
Wszystkie drzewa z najwyżej 27 wierzchołkami są pełne wdzięku; wynik ten pokazali Aldred i McKay w 1998 roku za pomocą programu komputerowego. Zostało to rozszerzone na drzewa z co najwyżej 29 wierzchołkami w pracy dyplomowej Michaela Hortona z wyróżnieniem. Kolejne rozszerzenie tego wyniku do drzew z 35 wierzchołkami zostało zgłoszone w 2010 roku przez Graceful Tree Verification Project, przetwarzania rozproszonego prowadzony przez Wenjie Fang.
Wszystkie wykresy kół , wykresy internetowe, wykresy steru , wykresy biegów i prostokątne siatki są pełne wdzięku.
Wszystkie n -wymiarowe hipersześciany są pełne wdzięku.
Wszystkie proste grafy z czterema lub mniejszą liczbą wierzchołków są pełne wdzięku. Jedynymi prostymi grafami pozbawionymi wdzięku z pięcioma wierzchołkami są 5- cyklowe ( pięciokąt ); pełny wykres K ₅ ; i wykres motyla .

Zobacz też

^ Virginia Vassilevska , „Kodowanie i pełne wdzięku etykietowanie drzew”. SURF 2001. PostScript
^ ^ab ^Internat Rosa, A. (1967), „O niektórych wycenach wierzchołków wykresu”, Theory of Graphs ( . Sympos., Rzym, 1966) , New York: Gordon and Breach, s. 349–355, MR 0223271 .
^ Wang, Tao-Ming; Yang, Cheng-Chang; Hsu, Lih-Hsing; Cheng, Eddie (2015), „Nieskończenie wiele równoważnych wersji wdzięcznej przypuszczenia drzewa”, Applicable Analysis and Discrete Mathematics , 9 (1): 1–12, doi : 10,2298 / ADM141009017W , MR 3362693
Bibliografia _ Pokrowski, Aleksiej; Sudakow, Benny (2020). „Dowód hipotezy Ringela”. arXiv : 2001.02665 [ matematyka.CO ].
Bibliografia _ Kotzig, A .; Rosa, A. (1982), „Dalsze wyniki dotyczące etykietowania drzew”, Utilitas Mathematica , 21 : 31–48, MR 0668845 .
Bibliografia _ „Rainbow Proof pokazuje, że wykresy mają jednolite części” . Magazyn Quanta . Źródło 2020-02-29 .
Bibliografia _ Kotzig, A .; Rosa, A. (1982), „Dalsze wyniki dotyczące etykietowania drzew”, Utilitas Mathematica , 21 : 31–48, MR 0668845 .
^ Rosa, A. (1988), „Cyclic Steiner Triple Systems and Labelings of Triangular Cacti”, Scientia , 1 : 87–95 .
Bibliografia _ _ _ _ _ _ _ _ _
Referencje ^_^_ _ _ _ _ _ _ _ _ _ _ .
Bibliografia _ McKay, Brendan D. (1998), „Wdzięczne i harmonijne etykietowanie drzew”, Biuletyn Instytutu Kombinatoryki i jego zastosowań , 23 : 69–72, MR 1621760 .
^ Horton, Michael P. (2003), Graceful Drzewa: statystyki i algorytmy .
^ Fang, Wenjie (2010), A Computational Approach to the Graceful Tree , arXiv : 1003.3045 , Bibcode : 2010arXiv1003.3045F Conjecture Zobacz także Graceful Tree Verification Project
Referencje _ _ _ _ _ _ _ _ _ _ _ 0638285 .
^ Weisstein, Eric W. „Graceful graph” . MathWorld .

Linki zewnętrzne

Film Numberphile o domysłach o wdzięcznym drzewie

Dalsza lektura

(K. Eshghi) Wprowadzenie do Graceful Graphs , Sharif University of Technology, 2002.
(UN Deshmukh i Vasanti N. Bhat-Nayak), Nowe rodziny wdzięcznych bananowców – Proceedings Mathematical Sciences, 1996 – Springer
(M. Haviar, M. Ivaska), Vertex Labellings of Simple Graphs, Research and Exposition in Mathematics, tom 34, 2015.
( Ping Zhang ), Kalejdoskopowe spojrzenie na kolorowanie wykresów, SpringerBriefs in Mathematics, 2016 – Springer

[Vas2001-1] Virginia Vassilevska , „Kodowanie i pełne wdzięku etykietowanie drzew”. SURF 2001. PostScript

[Ros1967-2] Internat Rosa, A. (1967), „O niektórych wycenach wierzchołków wykresu”, Theory of Graphs ( . Sympos., Rzym, 1966) , New York: Gordon and Breach, s. 349–355, MR 0223271 .

[3] Wang, Tao-Ming; Yang, Cheng-Chang; Hsu, Lih-Hsing; Cheng, Eddie (2015), „Nieskończenie wiele równoważnych wersji wdzięcznej przypuszczenia drzewa”, Applicable Analysis and Discrete Mathematics , 9 (1): 1–12, doi : 10,2298 / ADM141009017W , MR 3362693

[4] Bibliografia _ Pokrowski, Aleksiej; Sudakow, Benny (2020). „Dowód hipotezy Ringela”. arXiv : 2001.02665 [ matematyka.CO ].

[5] Bibliografia _ Kotzig, A .; Rosa, A. (1982), „Dalsze wyniki dotyczące etykietowania drzew”, Utilitas Mathematica , 21 : 31–48, MR 0668845 .

[6] Bibliografia _ „Rainbow Proof pokazuje, że wykresy mają jednolite części” . Magazyn Quanta . Źródło 2020-02-29 .

[Hua1982-7] Bibliografia _ Kotzig, A .; Rosa, A. (1982), „Dalsze wyniki dotyczące etykietowania drzew”, Utilitas Mathematica , 21 : 31–48, MR 0668845 .

[Rosa1988-8] Rosa, A. (1988), „Cyclic Steiner Triple Systems and Labelings of Triangular Cacti”, Scientia , 1 : 87–95 .

[Morgan-9] Bibliografia _ _ _ _ _ _ _ _ _

[Gal2015-10] Referencje ^_^_ _ _ _ _ _ _ _ _ _ _ .

[11] Bibliografia _ McKay, Brendan D. (1998), „Wdzięczne i harmonijne etykietowanie drzew”, Biuletyn Instytutu Kombinatoryki i jego zastosowań , 23 : 69–72, MR 1621760 .

[Horton2003-12] Horton, Michael P. (2003), Graceful Drzewa: statystyki i algorytmy .

[13] Fang, Wenjie (2010), A Computational Approach to the Graceful Tree , arXiv : 1003.3045 , Bibcode : 2010arXiv1003.3045F Conjecture Zobacz także Graceful Tree Verification Project

[Kot1981-14] Referencje _ _ _ _ _ _ _ _ _ _ _ 0638285 .

[Mat2007-15] Weisstein, Eric W. „Graceful graph” . MathWorld .