Vizings hypotese

Vizings formodning er en antagelse om sammenhængen mellem det dominerende sæt og det direkte produkt af grafer , som ikke er blevet bekræftet i 2017, mens hypotesen er bevist for en række særlige tilfælde.

Det blev først udtrykt af Vadim Vizing [1] . Hypotesens udsagn siger, at for det mindste antal hjørner i det dominerende sæt af grafen har vi: $\gamma (G)$ $G$

\gamma (G\,\square \,H)\geqslant \gamma (G)\,\gamma (H)

I 1995 [2] blev lignende grænser foreslået for det dominerende antal af tensorproduktet af grafer , men senere [3] blev der fundet et modeksempel.

Eksempler

Det dominerende tal for en cyklus med 4 toppunkter C 4 er to - ethvert enkelt toppunkt dominerer sig selv og to naboer, men ethvert par dominerer hele grafen. Produktet C 4 ◻ C 4 er en firedimensionel hyperkubegraf . Den har 16 toppunkter, og ethvert enkelt toppunkt dominerer sig selv og fire naboer, så tre toppunkter kan kun dominere 15 af de 16 toppunkter. Således skal mindst fire hjørner være indeholdt i grafens dominerende sæt, kun tallet givet af Vizings formodning.

Det dominerende antal af produktet kan være meget større end grænsen givet i Vizing-formodningen. For eksempel, for en stjerne K 1, n , er det dominerende tal γ(K 1, n ) lig med én — kun ét centralt toppunkt dominerer hele grafen. For en graf G = K 1, n ◻ K 1, n , dannet af produktet af to stjerner, siger Vizing-formodningen, at det dominerende tal er mindst 1 × 1 = 1. Faktisk er det dominerende sæt meget større. Grafen indeholder n 2 + 2 n + 1 toppunkter - n 2 fås fra bladene af to faktorer, 2 n fås fra produktet af bladene og midten, og et toppunkt fås fra produktet af centrene. Hvert blad-center-produkt dominerer nøjagtigt n blad-blad-hjørnepunkter af produktet, så n blad-center-hjørner er nødvendige for at dominere alle blad-blad-hjørner. Der er dog ingen blad-center-spidser, der dominerer det samme andet knudepunkt, så selvom n blad-center-spidser er valgt som det dominerende sæt, er der n ikke-dominerede blad-center-hjørner, der er domineret af et center-center-toppunkt. Det dominerende tal for denne graf er således γ(K 1, n ◻ K 1, n ) = n + 1, hvilket er meget større end den trivielle grænse givet af Vizing-formodningen.

Der er en uendelig familie af grafprodukter, for hvilke estimatet i Vizing-formodningen er skarp [4] [5] [6] [7] . For eksempel, hvis G og H begge er forbundne grafer og hver har mindst fire hjørner, og antallet af hjørner er nøjagtigt det dobbelte af det dominerende tal, så er γ( G ◻ H ) = γ( G )γ( H ) [8] . Graferne G og H med denne egenskab indeholder en C 4 cyklus med fire hjørner sammen med rodproduktet af en forbundet graf og en enkelt kant [8] .

Delvise resultater

Det er klart, at formodningen gælder, når enten G eller H har et dominerende tal 1 - produktet indeholder en isomorf kopi af den anden, så dets dominerende sæt har mindst γ( G )γ( H )-hjørnepunkter.

Det er kendt, at Vizings formodning gælder for cyklusser [6] [9] og for grafer med dominerende nummer to [10] .

I 2000 [11] blev det bevist, at produktets dominerende tal er mindst lig med halvdelen af grænsen specificeret i formodningen for alle G og H .

Øvre grænser

Vizing i den originale artikel [1] bemærkede, at:

γ( G ◻ H ) ≤ min{γ( G )|V( H )|, y( H )|V( G )|}.

Den dominerende mængde, der når denne grænse, kan opnås som et direkte produkt af de dominerende sæt af en af graferne G eller H med mængden af alle toppunkter i den anden graf.

Noter

Litteratur