Visingin hypoteesi

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.

Esimerkkejä

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] .

Osatulokset

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 .

Ylärajat

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.

Muistiinpanot

  1. ↑ 1 2 Vizing, 1968 .
  2. ↑ Gravier, Khelladi, 1995 .
  3. ↑ Klavžar, Zmazek, 1996 .
  4. ↑ Payan, Xuong, 1982 .
  5. ↑ Fink, Jacobson, Kinch, Roberts, 1985 .
  6. ↑ 12 Jacobson , Kinch, 1986 .
  7. ↑ Hartnell, Rall, 1991 .
  8. ↑ 1 2 Fink, Jacobson, Kinch, Roberts, 1985 .
  9. ↑ El-Zahar, Pareek, 1991 .
  10. ↑ Bartsalkin, saksa, 1979 .
  11. ↑ Clark, Suen, 2000 .

Kirjallisuus

Linkit