Vining hipotézise

Viizing sejtése a domináns halmaz és a gráfok közvetlen szorzata  közötti kapcsolatra vonatkozó feltételezés , amely 2017-ig nem igazolódott be, míg a hipotézis számos speciális esetre beigazolódott.

Ezt először Vadim Vizing [1] fejezte ki . A hipotézis állítása szerint  a gráf domináns halmazában a csúcsok minimális számához a következőt kapjuk:

.

1995-ben [2] hasonló korlátokat javasoltak a gráfok tenzorszorzatának domináns számára , de később [3] találtak ellenpéldát.

Példák

A 4 C 4 csúcsú ciklus domináns száma kettő - bármelyik csúcs uralja önmagát és két szomszédja, de bármelyik pár uralja a teljes gráfot. A C 4 ◻ C 4 szorzat egy négydimenziós hiperkocka gráf . 16 csúcsa van, és bármelyik csúcs uralja önmagát és négy szomszédját, így három csúcs csak a 16 csúcs közül 15-öt uralhatja. Így legalább négy csúcsnak kell lennie a gráf domináns halmazában, csak a Vizing sejtés által adott számnak.

A szorzat domináns száma jóval nagyobb lehet, mint a Viizing-sejtésben megadott határ. Például egy K 1, n csillag esetében a domináns γ(K 1, n ) szám egyenlő eggyel – csak egy központi csúcs uralja a teljes gráfot. Egy G = K 1, n ◻ K 1, n gráf esetén , amelyet két csillag szorzata képez, a Vizin-sejtés azt állítja, hogy az uralkodó szám legalább 1 × 1 = 1. Valójában azonban az uralkodó halmaz sok nagyobb. A gráf n 2 + 2 n + 1 csúcsot tartalmaz - n 2 két tényező leveleiből, 2 n a levelek és a középpont szorzatából, egy csúcs pedig a központok szorzatából adódik. Minden levélközép termék pontosan a termék n levél-levél csúcsát uralja, tehát n levélközéppont szükséges az összes levél-levél csúcs dominálásához. Azonban egyetlen levélközépponti csúcs sem uralja ugyanazt a másik csúcsot, így még ha n levélközéppontot választunk is domináns halmaznak, van n olyan nem dominált levélközéppont, amelyet egyetlen középponti csúcs ural. Így ennek a gráfnak a domináns száma γ(K 1, n ◻ K 1, n ) = n + 1, ami sokkal nagyobb, mint a Viizing-sejtés által adott triviális korlát.

A gráfszorzatoknak van egy végtelen családja, amelyre a Viizing-sejtésben szereplő becslés éles [4] [5] [6] [7] . Például, ha G és H egyaránt összefüggő gráf, és mindegyiknek legalább négy csúcsa van, és a csúcsok száma pontosan kétszerese a domináns számnak, akkor γ( G ◻ H ) = γ( G )γ( H ) [8] . Az ezzel a tulajdonsággal rendelkező G és H gráfok egy négy csúcsú C 4 ciklust tartalmaznak egy összefüggő gráf gyökérszorzatával és egyetlen éllel [8] .

Részeredmények

Nyilvánvaló, hogy a sejtés akkor teljesül, ha akár G , akár H domináns 1-es számmal rendelkezik – a szorzat tartalmazza a második izomorf másolatát, így a domináns halmazának legalább γ( G )γ( H ) csúcsa van.

Ismeretes, hogy a Vizing-sejtés érvényes a ciklusokra [6] [9] és a kettes domináns számú gráfokra [10] .

2000-ben [11] bebizonyosodott, hogy a szorzat domináns száma minden G és H esetében legalább a sejtésben meghatározott korlát felével egyenlő .

Felső határok

Vining az eredeti cikkben [1] megjegyezte, hogy:

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

Az ezt a határt elérő domináns halmaz megkapható az egyik G vagy H gráf domináns halmazainak közvetlen szorzataként a másik gráf összes csúcsának halmazával.

Jegyzetek

  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émet, 1979 .
  11. ↑ Clark, Suen, 2000 .

Irodalom

Linkek