Vizings dohad - Vizings conjecture - Wikipedia

v teorie grafů, Vizingova domněnka se týká vztahu mezi dominantní číslo a kartézský součin grafů. Tuto domněnku poprvé uvedl Vadim G. Vizing  (1968 ) a uvádí, že pokud γ (G) označuje minimální počet vrcholů v dominující sadě pro G, pak

Gravier & Khelladi (1995) domyslel podobnou hranici pro dominantní číslo tenzorový součin grafů; nicméně, protipříklad byl nalezen Klavžar & Zmazek (1996). Vzhledem k tomu, že Vizing navrhl jeho domněnku, mnoho matematiků na tom pracovalo s dílčími výsledky popsanými níže. Podrobnější přehled těchto výsledků naleznete v části Brešar a kol. (2012).

Příklady

Optimální sada pěti vrcholů v součinu dvou hvězd, . Příklady, jako je tento, ukazují, že u některých grafových produktů nemusí být Vizingova domněnka ani zdaleka těsná.

4-cyklus C4 má nadvládu číslo dvě: jakýkoli jediný vrchol ovládá pouze sebe a své dva sousedy, ale jakýkoli pár vrcholů dominuje celému grafu. Produkt je čtyřrozměrný hyperkrychlový graf; má 16 vrcholů a jakýkoli jeden vrchol může dominovat pouze sobě a čtyřem sousedům, takže tři vrcholy mohou dominovat pouze 15 z 16 vrcholů. Proto jsou k ovládnutí celého grafu zapotřebí minimálně čtyři vrcholy, které jsou dány Vizingovou domněnkou.

Je možné, aby dominantní číslo produktu bylo mnohem větší, než je vázané danou Vizingovou domněnkou. Například pro a hvězda K.1,n, jeho dominantní číslo γ (K.1,n) je jeden: je možné ovládnout celou hvězdu jediným vrcholem v jejím středu. Proto pro graf Vizingova domněnka, vytvořená jako produkt dvou hvězd, uvádí pouze to, že číslo dominance by mělo být alespoň 1 × 1 = 1. Avšak číslo dominance tohoto grafu je ve skutečnosti mnohem vyšší. Má to n2 + 2n + 1 vrcholy: n2 vytvořené z produktu listu v obou faktorech, 2n z produktu listu v jednom faktoru a náboje v druhém faktoru a jeden zbývající vrchol vytvořený z produktu dvou nábojů. Každý vrchol produktu s listovým nábojem G přesně dominuje n vrcholů listových listů, tak n vrcholy listů a nábojů jsou potřeba k tomu, aby ovládly všechny vrcholy listů a listů. Žádný vrchol listového náboje však nedominuje nad žádným jiným takovým vrcholem, takže ani po něm n vrcholy listových nábojů jsou vybrány tak, aby byly zahrnuty do dominující sady, zůstávají n více nedominovaných vrcholů listových hubů, kterým může dominovat jediný vrchol hub-hub. Takže číslo dominance tohoto grafu je mnohem vyšší než triviální hranice jedné dané Vizingovou domněnkou.

Existují nekonečné rodiny grafových produktů, pro které je přesně splněna hranice Vizingova domněnky.[1] Například pokud G a H jsou oba spojené grafy, z nichž každý má alespoň čtyři vrcholy a má přesně dvakrát tolik celkových vrcholů než jejich čísla nadvlády, pak .[2] Grafy G a H s touto vlastností se skládá z cyklu čtyř vrcholů C4 společně s kořenové produkty propojeného grafu a jedné hrany.[2]

Částečné výsledky

Je zřejmé, že domněnka platí, i když G nebo H má dominanci číslo jedna: produkt totiž obsahuje izomorfní kopii dalšího faktoru, který dominuje a který vyžaduje alespoň γ (G) γ (H) vrcholy.

Je také známo, že Vizingova domněnka platí pro cykly[3] a pro grafy s dominancí číslo dvě.[4]

Clark & ​​Suen (2000) prokázal, že dominantní číslo produktu je u všech alespoň o polovinu větší než domnělá vazba G a H.

Horní hranice

Vizing (1968) pozoroval to

Dominující množina splňující tuto vazbu může být vytvořena jako kartézský součin dominující množiny v jednom z G nebo H se sadou všech vrcholů v druhém grafu.

Poznámky

  1. ^ Payan a Xuong (1982); Fink a kol. (1985); Jacobson & Kinch (1986); Hartnell & Rall (1991).
  2. ^ A b Fink a kol. (1985).
  3. ^ Jacobson & Kinch (1986); El-Zahar & Pareek (1991).
  4. ^ Barcalkin & German (1979).

Reference

  • Barcalkin, A. M .; German, L. F. (1979), „The external stability number of the cartesian product of graphs“, Bul. Akad. Stiince RSS Moldoven (v Rusku), 1: 5–8, PAN  0544028.
  • Brešar, Boštjan; Dorbec, Paul; Goddard, Wayne; Hartnell, Bert L .; Henning, Michael A .; Klavžar, Sandi; Rall, Douglas F. (2012), „Vizingova domněnka: průzkum a nedávné výsledky“, Journal of Graph Theory, 69 (1): 46–76, doi:10,1002 / jgt.20565, PAN  2864622.
  • Clark, W. Edwin; Suen, Stephen (2000), „Nerovnost související s Vizingovým dohadem“, Electronic Journal of Combinatorics, 7 (1): N4, PAN  1763970.
  • El-Zahar, M .; Pareek, C. M. (1991), „Dominance number of products of graphs“, Ars Combin., 31: 223–227, PAN  1110240.
  • Fink, J. F .; Jacobson, M. S .; Kinch, L. F .; Roberts, J. (1985), „Na grafech, které mají dominantní číslo polovinu jejich pořadí“, Doba. Matematika. Hungar., 16 (4): 287–293, doi:10.1007 / BF01848079, PAN  0833264.
  • Gravier, S .; Khelladi, A. (1995), „O počtu dominujících křížových produktů grafů“, Diskrétní matematika, 145: 273–277, doi:10.1016 / 0012-365X (95) 00091-A, PAN  1356600.
  • Hartnell, B.L .; Rall, D. F. (1991), „O Vizingově domněnce“, Congr. Číslo., 82: 87–96, PAN  1152060.
  • Jacobson, M. S .; Kinch, L. F. (1986), „O dominanci produktů grafů II: stromy“, J. Teorie grafů, 10: 97–106, doi:10.1002 / jgt.3190100112, PAN  0830061.
  • Klavžar, Sandi; Zmazek, B. (1996), „O Vizingově domněnce pro přímé produktové grafy“, Diskrétní matematika, 156: 243–246, doi:10.1016 / 0012-365X (96) 00032-5, PAN  1405022.
  • Payan, C .; Xuong, N. H. (1982), „Grafy vyvážené nadvládou“, J. Teorie grafů, 6: 23–32, doi:10,1002 / jgt.3190060104, PAN  0644738.
  • Vizing, V. G. (1968), „Některé nevyřešené problémy v teorii grafů“, Uspekhi Mat. Nauk (v Rusku), 23 (6): 117–134, PAN  0240000.

externí odkazy