Půvabné značení

V teorii grafů , je elegantní značení z undirected graf s m hranami je označení z vrcholů podle různých přírodních čísla z množiny {0, ..., m }, který má tu vlastnost, že absolutní hodnoty rozdílů v etiketách konce okrajů jsou všechny odlišné a rovné 1, ..., m ; tak jednoznačně identifikují hrany. Graf, který připouští ladné označení, je ladný graf .

Termín „půvabné značení“ (v angličtině „ půvabné značení “ ) se objevuje v článku Solomona W. Golomba Koncept tváře, známý jako „β-značení“ v článku Alexandra Rosy označujícího grafy.

Půvabné stromy hádají

Jedním z nevyřešených dohadů v teorii grafů je půvabná domněnka stromu nebo Ringel-Kotzigova domněnka , pojmenovaná podle Gerharda Ringela a Antona Kotziga . Ona říká:

Ringel-Kotzigova domněnka - Všechny stromy jsou půvabné.

Ringel-Kotzigova domněnka je také známá jako „domnělá domněnka označování“. Slabší verze je

Ringel Conjecture - úplný graf může být rozložen do kopií jakékoli strom s hranami. ${\ displaystyle K_ {2n + 1}}$ $ne$

Tato domněnka Ringel byla prokázána pro velké hodnoty v článku zveřejněném dne $ne$ 8. ledna 2020Richard Montgomery, Alexey Pokrovskiy a Benny Sudakov ve společnosti Arxiv . Výsledek byl předmětem článku v časopise Quanta Magazine a v Pour la Science.

Částečné výsledky

Mnoho dílčích výsledků - pozitivních nebo negativních - se týká konkrétních tříd grafů. Katalog vede Joseph A. Gallian:

Eulerian graf s m hranami není ladný pokud m ≡ 1 (mod 4), nebo m ≡ 2 (mod 4).
Cyklus C n s n vrcholy je ladný právě tehdy, když n ≡ 0 (mod 4) nebo n ≡ 3 (mod 4).
Všechny řetězy a grafika prohledávače jsou elegantní.
All bipartitní graf plný , je elegantní.
Stromy maximálně 27 vrcholů jsou půvabné. Tento výsledek byl v roce 2003 rozšířen na stromy s 29 vrcholy, které vypracoval Michael Horton ve své bakalářské práci . Další prodloužení, na 35 vrcholů, oznámil v roce 2010 Wenjie Fang.
Jakýkoli graf kola , jakýkoli graf mřížky je elegantní.
Jakákoli hyperkrychle je ladná.
Tyto jednoduché grafy s nejvýše čtyřmi vrcholy jsou elegantní. Jediné grafy s 5 vrcholy, které nejsou elegantní, jsou 5- kroužek (dále pětiúhelník ); kompletní graf K 5 ; a motýlí graf .

Poznámky a odkazy

(de) / (en) Tento článek je částečně nebo zcela převzat z článků s názvem v němčině „ Graziöse Beschriftung “ ( viz seznam autorů ) a v angličtině „ Graceful labelling “ ( viz seznam autorů ) .

(en) Eric W. Weisstein , „ Půvabný graf “ , na MathWorld
Virginia Vassilevska, „Kódování a ladné označování stromů“, PostScript SURF 2001
Solomon W. Golomb, „ Největší půvabný podgraf úplného grafu “, Amer. Matematika. Měsíčně , sv. 81,1974, str. 499-501.
Martin Gardner, Kola, Život a další matematické zábavy , New York, WH Freeman,1983, Ch. 15: „Golombovy ladné grafy“ str. 152-165.
A. Rosa , „O určitých ocenění vrcholů grafu“ , v Theory of Graphs (Internat. Sympos., Rome, 1966) , New York, Gordon and Breach,1967( Math Reviews 0223271 ) , str. 349-355.
C. Huang, Anton Kotzig a Alexander Rosa, „ Další výsledky označování stromů “, Utilitas Mathematica , sv. 21,1982, str. 31–48 ( matematické recenze 668845 ).
" Důkaz o Ringelově domněnce " ,8. ledna 2020
Kevin Hartnett, „ Rainbow Proof Shows Graphs Have Uniform Parts “, na adrese https://www.quantamagazine.org , Quanta Magazine,19. února 2020(zpřístupněno 8. července 2020 ) .
" Ringelova domněnka prokázaná barvením grafů " ,30. června 2020.
Joseph A. Joseph A. Gallian , „ Dynamický průzkum značení grafů “, Electronic Journal of Combinatorics , 1998-2016, Dynamic Survey # DS6: 23. prosince 2016 ( Math Reviews = 1668059 , číst online ) .
REL Aldred a Brendan D. McKay, „ Půvabné a harmonické označování stromů, “ Bulletin of the Institute of Combinatorics and its Applications , vol. 23,1998, str. 69-72 ( matematické recenze 1621760 ).
Michael P. Horton, Půvabné stromy: Statistiky a algoritmy , University of Tasmania,2003( číst online ).
Wenjie Fang , „ Výpočetní přístup k půvabné domněnce stromu “, arxiv ,2010( arXiv 1003.3045 ).
Anton Kotzig , „ Rozklady celých grafů na izomorfní kostky “, Journal of Combinatorial Theory, Series B , sv. 31, n o 3,devatenáct osmdesát jedna, str. 292-296 ( DOI 10.1016 / 0095-8956 (81) 90031-9 , matematické recenze 638285 ).

Bibliografie

Shalom Eliahou, " Stromové sudoku " , Obrazy matematiky: Matematický výzkum slov a obrazů , CNRS,21. prosince 2013(zpřístupněno 5. prosince 2017 ) .
„ Jsou všechny stromy půvabné?“ " , Kafemath 2016-2017 ,29. září 2016(zpřístupněno 5. prosince 2017 ) .
Vasanti N. Bhat-Nayak a Ujwala N. Deshmukh, „ elegance z a ${\ displaystyle C_ {4t} \ pohár K_ {1,4t-1}}$ ${\ displaystyle C_ {4t + 3} \ pohár K_ {1,4t + 2}}$ “, J. Ramanujan Math. Soc. , sv. 11, n O 21996, str. 187-190 ( zbMATH 0867,05057 ).
Vasanti N. Bhat-Nayak a A. Selvam, „ elegance z -Konický $ne$ ${\ displaystyle C_ {m} \ vee K_ {n} ^ {c}}$ “, Ars Combin. , sv. 66,2003, str. 283–298 ( Math Reviews 1961491 ).
(en) Eric W. Weisstein , „ Půvabný graf “ , na MathWorld
Ping Zhang , Kaleidoskopický pohled na barvení grafů , Springer, kol. "SpringerBriefs in Mathematics",2016, 157 s. ( ISBN 978-3-319-30518-9 , číst online )

Související články

Okrajové ladění štítků (in)
Seznam matematických dohadů