Przypuszczenie Viizinga - Vizing's conjecture

W teorii wykres , hipoteza Vizing za dotyczy stosunku pomiędzy liczbą dominacji a iloczyn kartezjański wykresów . Przypuszczenie to 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 zbiorze dominującym dla G , to

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

Gravier i Khelladi (1995) wysnuli podobne ograniczenie dla liczby dominacji iloczynu tensorowego grafów ; kontrprzykład znaleźli jednak Klavžar i Zmazek (1996) . Odkąd Vizing przedstawił swoją hipotezę, wielu matematyków pracowało nad nią, z częściowymi wynikami opisanymi poniżej. Bardziej szczegółowy przegląd tych wyników można znaleźć w Brešar et al. (2012) .

Przykłady

Optymalny pięciowierzchołkowy zbiór dominujący w iloczynie dwóch gwiazd . Przykłady takie jak ten pokazują, że w przypadku niektórych produktów wykresu przypuszczenie Vizinga może być dalekie od ścisłego.${\ Displaystyle K_ {1,4} \, \ Box \, K_ {1,4}}$

Zawierające 4 cykl C ₄ ma numer dominacji dwa: Każdy wierzchołek dominuje wyłącznie siebie i jego dwoma sąsiadami, ale każda para wierzchołków dominuje cały wykres. Produkt jest czterowymiarowym grafem hipersześcianowym ; ma 16 wierzchołków, a każdy pojedynczy wierzchołek może dominować tylko nad sobą i czterema sąsiadami, więc trzy wierzchołki mogą zdominować tylko 15 z 16 wierzchołków. Dlatego wymagane są co najmniej cztery wierzchołki, aby zdominować cały wykres, granica podana przez przypuszczenie Vizinga. ${\ Displaystyle C_{4} \ \ Box \ C_ {4}}$

Możliwe jest, że liczba dominacji produktu będzie znacznie większa niż granica podana przez przypuszczenie 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 pojedynczym wierzchołkiem w jej piaście. Dlatego dla grafu utworzonego jako iloczyn dwóch gwiazd, przypuszczenie Vizinga mówi tylko, że liczba dominacji powinna wynosić co najmniej 1 × 1 = 1. Jednak liczba dominacji tego grafu jest w rzeczywistości znacznie wyższa. Ma n ²  + 2 n  + 1 wierzchołków: n ² utworzone z iloczynu liścia w jednym czynniku , 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 piasty liścia w G dominuje dokładnie n wierzchołków liścia, więc n wierzchołków piasty liścia jest potrzebnych do zdominowania wszystkich wierzchołków liścia. Jednak żaden wierzchołek piasty liścia nie dominuje nad żadnym innym takim wierzchołkiem, więc nawet po wybraniu n wierzchołków piasty liścia do włączenia do dominującego zbioru, pozostaje n więcej niezdominowanych wierzchołków piasty liścia, które mogą być zdominowane przez pojedynczą oś-piasta. wierzchołek piasty. Tak więc liczba dominacji tego wykresu jest znacznie wyższa niż trywialna granica jednego podanego przez przypuszczenie Vininga. ${\ Displaystyle G = K_ {1, n} \, \ Box \, K_ {1, n}}$${\ Displaystyle \ gamma (K_ {1, n} \, \ Box \, K_ {1, n}) = n + 1}$

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 dokładnie dwa razy więcej wierzchołków niż ich liczba dominacji, to . Wykresy G i H o tej własności składają się z czterowierzchołkowego cyklu C ₄ wraz z ukorzenionymi produktami grafu połączonego i pojedynczej krawędzi. ${\ Displaystyle \ gamma (G \ \ Box \ H) = \ gamma (G) \ gamma (H)}$

Wyniki częściowe

Oczywiście hipoteza jest słuszna, gdy G lub H mają dominację numer jeden: ponieważ iloczyn zawiera izomorficzną kopię drugiego czynnika, dominującego, który wymaga co najmniej γ( G )γ( H ) wierzchołków.

Wiadomo również, że przypuszczenie Viizinga sprawdza się w przypadku cykli i wykresów z dominacją numer dwa.

Clark i Suen (2000) wykazali, że liczba dominacji produktu jest co najmniej o połowę mniejsza niż przypuszczalna granica, dla wszystkich G i H .

Górne granice

Vizing (1968) zauważył, że

${\ Displaystyle \ gamma (G \ \ Box \ H) \ leq \ min \ {\ gamma (G) | V (H) | \ gamma (H) | V (G) | \}.}$

Zbiór dominujący spełniający to ograniczenie może być utworzony jako iloczyn kartezjański zbioru dominującego w jednym z G lub H ze zbiorem wszystkich wierzchołków z drugiego grafu.

Uwagi

Bibliografia

Linki zewnętrzne

• Weisstein, Eric W. „Domysł Vizing” . MatematykaŚwiat .