Przypuszczenie Vizinga

W teorii grafów hipoteza Vizinga dotyczy związku między liczbą dominacji a iloczynem kartezjańskim grafów . To przypuszczenie zostało po raz pierwszy sformułowane przez Vadima G. Vizinga ( 1968 ) i stwierdza, że jeśli $γ(G)$ oznacza minimalną liczbę wierzchołków w dominującym zbiorze dla grafu $G$ , to

{\ Displaystyle \ gamma (G \ \ Box \, H) \ geq \ gamma (G) \ gamma (H). \,}

Gravier i Khelladi (1995) przypuszczali, że istnieje podobna granica dla liczby dominacji iloczynu tensorowego grafów ; jednakże kontrprzykład znaleźli Klavžar i Zmazek (1996) . Odkąd Vizing zaproponował swoją hipotezę, pracowało nad nią wielu matematyków, a częściowe wyniki opisano poniżej. Bardziej szczegółowy przegląd tych wyników można znaleźć w artykule Brešar i in. (2012) .

Przykłady

Optymalny zbiór dominujący z pięcioma wierzchołkami w iloczynie dwóch gwiazd,

K 1,4 □ K 1,4

. Przykłady takie jak ten pokazują, że w przypadku niektórych produktów grafowych hipoteza Vizinga może być daleka od ścisłej.

Czterocyklowy $C 4 ma dominację numer dwa: dowolny pojedynczy wierzchołek dominuje tylko nad sobą i dwoma sąsiadami, ale dowolna para wierzchołków$ dominuje nad całym grafem. Iloczyn $C 4 □ C 4$ jest czterowymiarowym grafem hipersześcianu ; ma 16 wierzchołków, a każdy pojedynczy wierzchołek może zdominować tylko siebie i czterech sąsiadów, więc trzy wierzchołki mogą zdominować tylko 15 z 16 wierzchołków. Dlatego do zdominowania całego wykresu wymagane są co najmniej cztery wierzchołki, granica określona przez hipotezę Vizinga.

Możliwe jest, że liczba dominacji produktu będzie znacznie większa niż granica określona przez hipotezę Vizinga. Na przykład dla gwiazdy $K 1, n$ jej liczba dominacji $γ(K 1, n)$ wynosi jeden: możliwe jest zdominowanie całej gwiazdy z jednym wierzchołkiem w jej centrum. Dlatego dla wykresu $G = K 1, n □ K 1, n$ utworzonego jako iloczyn dwóch gwiazd przypuszczenie Vizinga stwierdza tylko, że liczba dominacji powinna wynosić co najmniej $1 \times 1 = 1$ . Jednak liczba dominacji na tym wykresie jest w rzeczywistości znacznie wyższa. Ma $n 2 + 2 n + 1$ wierzchołków: $n 2$ utworzone z iloczynu liścia w obu czynnikach, $2 n$ z iloczynu liścia w jednym czynniku i piasty w drugim czynniku oraz jeden pozostały wierzchołek utworzony z produkt dwóch hubów. Każdy wierzchołek iloczynu liść-piasta w $G$ dominuje dokładnie $n$ wierzchołków liść-liść, więc $n$ wierzchołki piasty liścia są potrzebne do zdominowania wszystkich wierzchołków liścia-liścia. Jednak żaden wierzchołek piasty liścia nie dominuje nad żadnym innym takim wierzchołkiem, więc nawet po $n$ wierzchołków piasty liścia do włączenia do zbioru dominującego pozostaje $n$ więcej niezdominowanych wierzchołków piasty liścia, które mogą być zdominowane przez pojedynczą piastę- wierzchołek piasty. Zatem liczba dominacji tego wykresu jest $γ(K 1, n □ K 1, n) = n + 1$ znacznie wyższa niż trywialna granica jedności określona przez hipotezę Vizinga.

Istnieją nieskończone rodziny produktów grafowych, dla których granica hipotezy Vizinga jest dokładnie spełniona. Na przykład, jeśli $G$ i $H$ są grafami spójnymi, z których każdy ma co najmniej cztery wierzchołki i ma dokładnie dwa razy więcej wierzchołków ogółem niż ich liczby dominacji, to $γ(G □ H) = γ (G) γ (H)$ . Grafy $G$ i $H$ o tej własności składają się z czterowierzchołkowego cyklu $C 4$ wraz z iloczynami ukorzenionymi połączonego grafu i pojedynczej krawędzi.

Wyniki częściowe

Oczywiście przypuszczenie to zachodzi, gdy $G$ lub $H$ ma dominację numer jeden: ponieważ iloczyn zawiera izomorficzną kopię drugiego czynnika, dominującego, który wymaga co najmniej wierzchołków $γ (G) γ (H) .$

Hipoteza Vizinga jest również znana dla cykli i grafów z dominacją numer dwa.

Clark i Suen (2000) udowodnili, że liczba dominacji iloczynu jest co najmniej o połowę mniejsza od domniemanej granicy dla wszystkich $G$ i $H$ .

Górne granice

Zauważył to Vizing (1968).

{\ Displaystyle \ gamma (G \, \ Box \, H) \ równoważnik \ min \ {\ gamma (G) | V (H) |, \ gamma (H) | V (G) |\}.}

Zbiór dominujący spełniający to ograniczenie można utworzyć jako iloczyn kartezjański zbioru dominującego w jednym z G lub H ze zbiorem wszystkich wierzchołków na drugim grafie.

Notatki

Barcalkin, AM; Niemiecki, LF (1979), „Zewnętrzna liczba stabilności iloczynu kartezjańskiego grafów”, Bul. Akad. Stiince RSS Moldoven (po rosyjsku), 1 : 5–8, MR 0544028 .
Brešar, Boštjan; Dorbec, Paweł; Goddard, Wayne; Hartnell, Bert L.; Henning, Michael A.; Klavžar, Sandi; Rall, Douglas F. (2012), „Przypuszczenie Vizinga: ankieta i ostatnie wyniki”, Journal of Graph Theory , 69 (1): 46–76, doi : 10.1002/jgt.20565 , MR 2864622 .
Clark, W. Edwin; Suen, Stephen (2000), „Nierówność związana z hipotezą Vizinga” , Electronic Journal of Combinatorics , 7 (1): N4, MR 1763970 .
El-Zahar, M.; Pareek, CM (1991), "Liczba dominacji iloczynów grafów", Ars Combinatoria , 31 : 223–227, MR 1110240 .
Fink, JF; Jacobson, MS; Kinch, LF; Roberts, J. (1985), „Na wykresach o liczbie dominacji w połowie ich rzędu”, Okres. Matematyka węgierski. , 16 (4): 287–293, doi : 10.1007/BF01848079 , MR 0833264 .
Gravier, S.; Khelladi, A. (1995), „O liczbie dominacji iloczynów krzyżowych grafów”, Discrete Mathematics , 145 : 273–277, doi : 10,1016/0012-365X(95)00091-A , MR 1356600 .
Hartnell, BL; Rall, DF (1991), „O przypuszczeniach Vizinga”, Congr. liczba. , 82 : 87-96, MR 1152060 .
Jacobson, MS; Kinch, LF (1986), „O dominacji iloczynów grafów II: drzewa”, Journal of Graph Theory , 10 : 97–106, doi : 10.1002/jgt.3190100112 , MR 0830061 .
Klavžar, Sandi; Zmazek, B. (1996), "On a Vizing-like conjecture for direct product graphs", Discrete Mathematics , 156 : 243-246, doi : 10.1016/0012-365X(96)00032-5 , MR 1405022 .
Payan, C.; Xuong, NH (1982), „Wykresy zrównoważone przez dominację”, Journal of Graph Theory , 6 : 23–32, doi : 10.1002/jgt.3190060104 , MR 0644738 .
Vizing, VG (1968), „Niektóre nierozwiązane problemy w teorii grafów”, Uspekhi Mat. Nauk (po rosyjsku), 23 (6): 117–134, MR 0240000 .

Linki zewnętrzne

Weisstein, Eric W. „Przypuszczenie Vizinga” . MathWorld .