Mychelskilainen

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 10. marraskuuta 2021 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

Suuntaamattoman graafin Mycielski- tai Mycielski-graafi on graafi, joka on luotu soveltamalla Mycielski- konstruktiota ( Mycielski 1955 ). Suunnittelu säilyttää kolmioiden puuttumisen , mutta lisää kromaattista lukua . Mycelsky osoitti, että toistamalla konstruktio toistuvasti alkuperäiseen kolmiovapaaseen graafiin, voidaan saada mielivaltaisen suurikokoisia kolmiota sisältämättömiä kuvaajia.

Rakentaminen

Olkoon annetun graafin G n pistettä v 0 , v 1 ja niin edelleen . G : n Mycielskin graafi μ( G ) sisältää G :n aligraafina ja n +1 pistettä lisää — yhden pisteen u i jokaiselle G :n pisteelle v i ja yhden pisteen w lisää . Jokainen kärki u i on yhdistetty reunalla w :hen niin, että kärjet muodostavat tähden K 1, n . Lisäksi graafin G kullekin reunalle v i v j Mycielski-graafi sisältää kaksi reunaa — u i v j ja v i u j .

Siten, jos G :llä on n kärkeä ja m reunaa, μ( G ) on 2 n + 1 kärkeä ja 3 m + n reunaa.

Esimerkki

Kuvassa on esitetty Mycielskin konstruktit sovellettuina sykliin , jossa on viisi kärkeä - v i , kun 0 ≤ i ≤ 4. Tuloksena oleva Mycielski on Grötsch- graafi , graafi, jossa on 11 pistettä ja 20 reunaa. Gröcz-graafi on pienin kolmioton graafi, jonka kromaattinen luku on 4 ( Chvátal 1974 ).

Mychelskin konstruktion useita toistoja

Soveltamalla Mycelskin konstruktiota toistuvasti, aloittaen graafista, jossa on yksi reuna, saadaan graafijono M i = μ( M i -1 ), jota joskus kutsutaan myös Mycelsky-graafiksi. Ensimmäiset graafit tässä sarjassa ovat M 2 = K 2 -graafit , joissa on kaksi kärkeä, jotka on yhdistetty reunalla, M 3 = C 5 -sykli ja Grötzschin graafi , jossa on 11 pistettä ja 20 reunaa.

Yleensä sekvenssin graafit M i eivät sisällä kolmioita , ( i -1) -kärkikytkettyjä ja i - kromaattisia . M i :ssä on 3 × 2 i -2 - 1 kärkeä (sekvenssi A083329 OEIS : ssä ). Reunojen lukumäärä M i :ssä pienelle i :lle on

0, 0, 1, 5, 20, 71, 236, 755, 2360, 7271, 22196, 67355, ... (sekvenssi A122695 OEIS : ssä ).

Ominaisuudet

Jos G :llä on kromaattinen luku k , niin μ( G ) on kromaattinen luku k + 1 ( Mycielski 1955 ).
Jos G :llä ei ole kolmioita , ei myöskään μ( G ) ole kolmioita ( Mycielski 1955 ).
Yleisemmin, jos G :llä on klikkiluku ω( G ), niin μ( G ):llä on klikkiluku max(2,ω( G )) ( Mycielski 1955 ).
Jos G on osamääräkriittinen kuvaaja , niin on myös μ( G ) ( Došlić 2005 ). Erityisesti jokainen graafi M i arvolle i ≥ 2 on tekijäkriittinen.
Jos G on Hamiltonin sykli , niin on myös μ( G ) ( Fisher, McKenna, Boyer 1998 ).
Jos G :llä on hallitseva luku γ( G ), niin μ( G ) on hallitseva luku γ( G )+1 ( Fisher, McKenna, Boyer 1998 ).

Kartio kaavioiden päällä

Mychelskin yleistyksen, jota kutsutaan kartioksi graafin päällä, esitteli Stiebitz ( Stiebitz 1985 ), ja sen myöhemmin tutkivat Tardif ( Tardif 2001 ) ja Lin, Wu, Lam ja Gu ( Lin, Wu, Lam, Gu 2006 ).

Olkoon G graafi, jossa on kärkijoukot ja reunajoukot . Olkoon kokonaisluku annettu . Graafille G kutsumme m-mychelskiksi graafia , jossa on joukko pisteitä ${\displaystyle V^{0}=\left\{v_{1}^{0},v_{2}^{0},...,v_{n}^{0}\oikea\))$ $E^{0}$ $m\geq 1$ $\mu _{m}(G)$

{\displaystyle V^{0}\cup V^{1}\cup V^{2}\cup ...\cup V^{m}\cup \left\{u\right\))

missä on i:s kopio , ja joukko reunoja $V^{i}=\left\{v_{j}^{i}:v_{j}^{0}\in V^{0}\right\}$ $V^{0}$ $i=1,2,...,m$

E^{0}\cup \left(\bigcup _{i=0}^{m-1}\left\{v_{j}^{i}v_{j'}^{i+1} :v_{j}^{0}v_{j'}^{0}\in E^{0}\oikea\}\oikea)\kuppi \vasen\{v_{j}^{m}u:v_{ j}^{m}V^{m}\oikea\}

Määrittele graafina, joka saadaan lisäämällä universaali kärkipiste u. Ilmeisesti mychelskian on vain [1] . $\mu _{0}(G)$ $\mu _{1}(G)$

Muistiinpanot

↑ Lin, Wu, Lam, Gu, 2006 .

Kirjallisuus

Vaclav Chvatal. Graphs and Combinatorics (Proc. Capital Conf., George Washington Univ., Washington, DC, 1973). - Springer-Verlag, 1974. - T. 406. - S. 243-246. — (Matematiikan luentomuistiinpanot).
Tomislav Došlić. Mycielskians and matchings // Discussions Mathematicae Graph Theory. - 2005. - T. 25 , no. 3 .
David C. Fisher, Patricia A. McKenna, Elizabeth D. Boyer. Mycielskin graafien hamiltonisuus, halkaisija, dominointi, pakkaus ja bikli-osiot // Discrete Applied Mathematics. - 1998. - T. 84 , no. 1-3 . - S. 93-105 . - doi : 10.1016/S0166-218X(97)00126-1 .
Wensong Lin, Jianzhuan Wu, Peter Che Bor Lam, Guohua Gu. Useita yleistettyjen Mycielskien parametreja // Diskreetti sovellettu matematiikka. - 2006. - T. 154 , no. 8 . - S. 1173-1182 . - doi : 10.1016/j.dam.2005.11.001 .
Jan Mycielski. Sur le coloriage des graphes // Colloq. Matematiikka.. - 1955. - T. 3 . - S. 161-162 .
M. Stiebitz. Beiträge zur Theorie der färbungskritschen Graphen. — Habilitaatiotutkielma, Technische Universität Ilmenau , 1985. Kuten julkaisussa Tardif ( 2001 ).
C. Tardif. Kartioiden kromaattiset murtoluvut graafien yli // Journal of Graph Theory. - 2001. - T. 38 , no. 2 . - S. 87-94 . - doi : 10.1002/jgt.1025 .
Weisstein, Eric W. Mycielski Graph (englanniksi) Wolfram MathWorld -verkkosivustolla .