Půvabné značení - Graceful labeling
v teorie grafů, a elegantní označení grafu s m hrany je a Značení jeho vrcholů s nějakou podmnožinou celá čísla mezi 0 a m včetně, takže žádné dva vrcholy nesdílejí štítek a každý okraj je jednoznačně identifikován pomocí absolutní rozdíl mezi svými koncovými body, takže tato velikost leží mezi 1 a m včetně.[1] Graf, který připouští ladné označení, se nazývá a elegantní graf.
Název „půvabné označování“ je způsoben Solomon W. Golomb; tento typ označování dostal původně název β-značení Alexander Rosa v dokumentu z roku 1967 o značení grafů.[2]
Hlavní domněnka v teorii grafů je Ladná domněnka stromu nebo Ringel – Kotzigova domněnka, pojmenoval podle Gerhard Ringel a Anton Kotzig, který předpokládá, že všechno stromy jsou ladné. Je to stále otevřená domněnka, i když v roce 2020 se ukázala jako pravdivá související, ale o něco slabší domněnka známá jako Ringelova domněnka.[3][4][5] Ringel – Kotzigova domněnka je také známá jako „domnělá domněnka označování“. Kotzig jednou nazval snahu dokázat domněnku jako „nemoc“.[6]
Další slabší verzí ladného označování je u ladné značení, ve kterém lze označit vrcholy pomocí některé podmnožiny souboru celá čísla mezi 0 a m + 1 včetně, takže žádné dva vrcholy nesdílejí štítek a každý okraj je jednoznačně identifikován znakem absolutní rozdíl mezi jeho koncovými body, takže tato velikost leží mezi 1 a m + 1 včetně.
Další domněnka v teorii grafů je Rosina domněnka, pojmenoval podle Alexander Rosa, který říká, že vše trojúhelníkové kaktusy jsou ladní nebo téměř ladní.[7]
Vybrané výsledky
- Rosa ve svém původním článku prokázal, že Euleriánský graf s počtem hran m ≡ 1 (mod 4) nebo m ≡ 2 (mod 4) nemůže být ladný.[2]
- Rosa také ve svém původním příspěvku dokázal, že cyklus Cn je půvabný právě tehdy n ≡ 0 (mod 4) nebo n ≡ 3 (mod 4).
- Všechno grafy cesty a housenkové grafy jsou ladné.
- Všechno humrové grafy s perfektní shoda jsou ladné.[8]
- Všechny stromy s maximálně 27 vrcholy jsou půvabné; tento výsledek prokázali Aldred a McKay v roce 1998 pomocí počítačového programu.[9][10] Toto bylo rozšířeno na stromy s maximálně 29 vrcholy v diplomové práci Michaela Hortona.[11] Další rozšíření tohoto výsledku až na stromy s 35 vrcholy si v roce 2010 vyžádal Graceful Tree Verification Project, a distribuované výpočty projekt vedený Wenjie Fang.[12]
- Všechno grafy kol, webové grafy, kormidelní grafy, převodové grafy, a obdélníkové mřížky jsou ladné.[9]
- Všechno n-dimenzionální hyperkrychle jsou ladné.[13]
- Všechno jednoduché grafy se čtyřmi nebo méně vrcholy jsou půvabné. Jediné nenáročné jednoduché grafy s pěti vrcholy jsou 5cyklus (Pentagon ); the kompletní graf K.5; a motýlí graf.[14]
Viz také
externí odkazy
Reference
- ^ Virginia Vassilevska „Kódování a ladné označování stromů.“ SURF 2001. PostScript
- ^ A b Rosa, A. (1967), „O určitých oceněních vrcholů grafu“, Theory of Graphs (Internat. Sympos., Řím, 1966), New York: Gordon and Breach, s. 349–355, PAN 0223271.
- ^ Montgomery, Richard; Pokrovskiy, Alexey; Sudakov, Benny (2020). "Důkaz o Ringelově domněnce". arXiv:2001.02665 [math.CO ].
- ^ Huang, C .; Kotzig, A.; Rosa, A. (1982), "Další výsledky označování stromů", Utilitas Mathematica, 21: 31–48, PAN 0668845.
- ^ Hartnett, Kevin. „Rainbow Proof Shows Graphs have Uniform Parts“. Časopis Quanta. Citováno 2020-02-29.
- ^ Huang, C .; Kotzig, A.; Rosa, A. (1982), "Další výsledky označování stromů", Utilitas Mathematica, 21: 31–48, PAN 0668845.
- ^ Rosa, A. (1988), „Cyclic Steiner Triple Systems and Labelings of Triangular Cacti“, Scientia, 1: 87–95.
- ^ Morgan, David (2008), „Všichni humři s dokonalým spojením jsou ladní“, Bulletin Ústavu kombinatoriky a jeho aplikací, 53: 82–85, hdl:10402 / era.26923.
- ^ A b Gallian, Joseph A. (1998), „Dynamický průzkum značení grafů“, Electronic Journal of Combinatorics, 5: Dynamic Survey 6, 43 s. (389 s. V 18. vyd.) (Elektronický), PAN 1668059.
- ^ Aldred, R. E. L .; McKay, Brendan D. (1998), „Půvabné a harmonické označování stromů“, Bulletin Ústavu kombinatoriky a jeho aplikací, 23: 69–72, PAN 1621760.
- ^ Horton, Michael P. (2003), Půvabné stromy: Statistiky a algoritmy.
- ^ Fang, Wenjie (2010), Výpočetní přístup k půvabné domněnce stromu, arXiv:1003.3045, Bibcode:2010arXiv1003.3045F. Viz také Půvabný projekt ověření stromu
- ^ Kotzig, Anton (1981), „Rozklady celých grafů na izomorfní kostky“, Journal of Combinatorial Theory, Series B, 31 (3): 292–296, doi:10.1016/0095-8956(81)90031-9, PAN 0638285.
- ^ Weisstein, Eric W. "Půvabný graf". MathWorld.
Další čtení
- (K.Eshghi) Úvod do půvabných grafů, Sharif University of Technology, 2002.
- (U.N.Deshmukh a Vasanti N.Bhat-Nayak), Nové rodiny půvabných banánových stromů - Proceedings Mathematical Sciences, 1996 - Springer
- (M. Haviar, M. Ivaska), Vertex Labellings of Simple Graphs, Research and Exposition in Mathematics, svazek 34, 2015.
- (Ping Zhang ), Kaleidoskopický pohled na barvení grafů, SpringerBriefs in Mathematics, 2016 - Springer