Vizingin olettamus on oletus hallitsevan joukon ja graafien suoratulon välisestä yhteydestä , jota ei ole vahvistettu vuoteen 2017 mennessä, kun taas hypoteesi on todistettu useille erikoistapauksille.
Sen ilmaisi ensimmäisenä Vadim Vizing [1] . Hypoteesin väite sanoo, että graafin hallitsevan joukon pisteiden minimimäärälle meillä on:
.Vuonna 1995 [2] ehdotettiin samanlaisia rajoja graafien tensoritulon hallitsevalle luvulle , mutta myöhemmin [3] löydettiin vastaesimerkki.
Neljän kärjen syklin hallitseva luku C 4 on kaksi - mikä tahansa yksittäinen kärki hallitsee itseään ja kaksi naapuria, mutta mikä tahansa pari hallitsee koko graafia. Tulo C 4 ◻ C 4 on neliulotteinen hyperkuutiograafi . Sillä on 16 kärkeä, ja mikä tahansa yksittäinen piste hallitsee itseään ja neljää naapuriaan, joten kolme kärkeä voi hallita vain 15:tä 16 pisteestä. Graafin hallitsevassa joukossa on siis oltava vähintään neljä kärkeä, vain Vizingin oletuksen antama luku.
Tuotteen hallitseva luku voi olla paljon suurempi kuin Viizing-arvauksessa annettu raja. Esimerkiksi tähdelle K 1, n hallitseva luku γ(K 1, n ) on yhtä suuri kuin yksi — vain yksi keskipiste hallitsee koko graafia. Kahden tähden tulosta muodostetulle graafille G = K 1, n ◻ K 1, n Vizing-oletus väittää, että hallitseva luku on vähintään 1 × 1 = 1. Itse asiassa hallitseva joukko on kuitenkin paljon suurempi. Graafi sisältää n 2 + 2 n + 1 kärkeä - n 2 saadaan kahden tekijän lehdistä, 2 n saadaan lehtien ja keskustan tulosta ja yksi kärki keskustan tulosta. Jokainen lehtikeskustuote hallitsee tarkalleen n tuotteen lehti-lehtipistettä, joten tarvitaan n lehtikeskipistettä hallitsemaan kaikkia lehti-lehtipisteitä. Mikään lehtien keskustan kärki ei kuitenkaan hallitse samaa toista kärkeä, joten vaikka n lehden keskustan kärkeä valitaan hallitsevaksi joukoksi, on n ei-dominoitua lehden keskustan kärkeä, joita hallitsee yksi keskipistepiste. Siten tämän graafin hallitseva luku on γ(K 1, n ◻ K 1, n ) = n + 1, joka on paljon suurempi kuin Viizing-oletuksen antama triviaaliraja.
Graafituloja on ääretön perhe, jolle Viizing-oletuksen estimaatti on terävä [4] [5] [6] [7] . Esimerkiksi, jos G ja H ovat molemmat yhdistettyjä graafia ja kummallakin on vähintään neljä kärkeä ja pisteiden lukumäärä on täsmälleen kaksi kertaa dominanttiluku, niin γ( G ◻ H ) = γ( G )γ( H ) [8] . Graafit G ja H , joilla on tämä ominaisuus, sisältävät C 4 -syklin , jossa on neljä kärkeä sekä yhdistetyn graafin ja yhden reunan juuritulo [8] .
On selvää, että olettamus pätee, kun joko G :llä tai H :lla on hallitseva numero 1 – tulo sisältää isomorfisen kopion toisesta, joten sen hallitsevassa joukossa on vähintään γ( G )γ( H )-pistettä.
Tiedetään, että Vizingin olettamus pätee jaksoille [6] [9] ja kuvaajille, joilla on hallitseva numero kaksi [10] .
Vuonna 2000 [11] todistettiin, että tulon hallitseva luku on vähintään puolet oletuksissa määritellystä rajasta kaikille G :lle ja H :lle .
Viizing alkuperäisessä artikkelissa [1] huomautti, että:
γ( G◻H ) ≤ min{γ( G )|V( H )|, γ( H )|V( G ) |}.Tämän rajan saavuttava hallitseva joukko voidaan saada toisen graafin G tai H hallitsevien joukkojen suorana tulona toisen graafin kaikkien kärkien joukon kanssa.