Vizingova hypotéza

Vizingova domněnka  je předpokladem o souvislosti mezi dominující množinou a přímým součinem grafů , který se od roku 2017 nepotvrdil, přičemž hypotéza byla prokázána pro řadu speciálních případů.

Poprvé to vyjádřil Vadim Vizing [1] . Tvrzení hypotézy říká, že pro  minimální počet vrcholů v dominující množině grafu máme:

.

V roce 1995 [2] byly navrženy podobné hranice pro dominující číslo součinu tenzoru grafů , ale později [3] byl nalezen protipříklad.

Příklady

Dominantní číslo cyklu se 4 vrcholy C 4 je dva - libovolný jednotlivý vrchol dominuje sám sobě a dvěma sousedům, ale libovolná dvojice dominuje celému grafu. Součin C 4 ◻ C 4 je čtyřrozměrný graf hyperkrychle . Má 16 vrcholů a každý jednotlivý vrchol dominuje sám sobě a čtyřem sousedům, takže tři vrcholy mohou dominovat pouze 15 ze 16 vrcholů. V dominující množině grafu tedy musí být obsaženy alespoň čtyři vrcholy, právě počet daný Vizingovou domněnkou.

Dominantní číslo produktu může být mnohem větší než limit uvedený ve Vizingově domněnce. Například pro hvězdu K 1, n je dominantní číslo γ(K 1, n ) rovno jedné — celému grafu dominuje pouze jeden centrální vrchol. Pro graf G = K 1, n ◻ K 1, n , tvořený součinem dvou hvězd, Vizingova domněnka uvádí, že dominující číslo je alespoň 1 × 1 = 1. Ve skutečnosti je však dominantní množina mnohem větší. Graf obsahuje n 2 + 2 n + 1 vrcholů - n 2 se získá z listů dvou faktorů, 2 n se získá ze součinu listů a středu a jeden vrchol se získá ze součinu středů. Každý produkt ve středu listu dominuje přesně n vrcholům listu a listu produktu, takže k dominování všem vrcholům listu a listu je potřeba n vrcholů uprostřed listu. Žádný vrchol uprostřed listu však nedominuje stejnému druhému vrcholu, takže i když je jako dominantní množina vybráno n středových vrcholů listu, existuje n nedominovaných středových vrcholů, kterým dominuje jeden středový vrchol. Dominantní číslo tohoto grafu je tedy γ(K ​​1, n ◻ K 1, n ) = n + 1, což je mnohem větší než triviální hranice daná Vizingovou domněnkou.

Existuje nekonečná rodina grafových produktů, pro které je odhad ve Vizingově domněnce ostrý [4] [5] [6] [7] . Pokud jsou například G a H oba spojené grafy a každý má alespoň čtyři vrcholy a počet vrcholů je přesně dvojnásobkem dominantního čísla, pak γ( G ◻ H ) = γ( G )γ( H ) [8] . Grafy G a H s touto vlastností obsahují cyklus C 4 se čtyřmi vrcholy spolu s kořenovým součinem souvislého grafu a jedinou hranou [8] .

Dílčí výsledky

Je jasné, že domněnka platí, když má G nebo H dominantní číslo 1 – součin obsahuje izomorfní kopii druhého, takže jeho dominující množina má alespoň γ( G )γ( H ) vrcholy.

Je známo, že Vizingova domněnka platí pro cykly [6] [9] a pro grafy s dominujícím číslem dvě [10] .

V roce 2000 [11] bylo dokázáno, že dominující číslo součinu je pro všechna G a H rovno alespoň polovině hranice uvedené v domněnce .

Horní hranice

Vizing v původním článku [1] poznamenal, že:

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

Dominantní množinu dosahující této hranice lze získat jako přímý součin dominujících množin jednoho z grafů G nebo H s množinou všech vrcholů druhého grafu.

Poznámky

  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, Němec, 1979 .
  11. ↑ Clark, Suen, 2000 .

Literatura

Odkazy