On Vizing's conjecture
Povzetek
A dominating set ▫$D$▫ gor a graph ▫$G$▫ is a subset ▫$V(G)$▫ such that any vertex in ▫$V(G)-D$▫ has a neighbor in ▫$D$▫, and a domination number ▫$\gamma(G)$▫ is the size of a minimum dominating set for ▫$G$▫. For the Cartesian product ▫$G \Box H$▫ Vizing's conjecture states that ▫$\gamma(G \Box H) \ge \gamma(G)\gamma(H)$▫ for every pair of graphs ▫$G,H$▫. In this paper we introduce a new concept which extends the ordinary domination of graphs, and prove that the conjecture holds when ▫$\gamma(G) = \gamma(H) = 3$▫.
Ključne besede
matematika;teorija grafov;graf;kartezični produkt;dominantno število;mathematics;graph theory;graph;Cartesian product;domination number;
Podatki
| Jezik: | Angleški jezik |
|---|---|
| Leto izida: | 2001 |
| Tipologija: | 1.01 - Izvirni znanstveni članek |
| Organizacija: | UM FKBV - Fakulteta za kmetijstvo in biosistemske vede |
| UDK: | 519.17 |
| COBISS: |
11010137
|
| ISSN: | 1234-3099 |
| Št. ogledov: | 912 |
| Št. prenosov: | 87 |
| Ocena: | 0 (0 glasov) |
| Metapodatki: |
|
Ostali podatki
| Sekundarni jezik: | Slovenski jezik |
|---|---|
| Sekundarni naslov: | O Vizingovi domnevi |
| Sekundarni povzetek: | Dominirajoča množica ▫$D$▫ grafa ▫$G$▫ je taka podmnožica množice ▫$V(G)$▫, za katero ima vsaka točka iz množice ▫$V(G)-D$▫ kako sosedo v ▫$D$▫; dominantno število ▫$\gamma(G)$▫ pa je velikost najmanjše dominirajoče množice grafa ▫$G$▫. Za kartezični produkt grafov ▫$G \Box H$▫ Vizingova domneva trdi, da je ▫$\gamma(G \Box H) \ge \gamma(G)\gamma(H)$▫, kjer sta ▫$G$▫ in ▫$H$▫ poljubna grafa. V članku vpeljemo nov koncept, ki posploši običajno dominacijo grafov in dokažemo, da domneva drži v promeru, ko je ▫$\gamma(G) = \gamma(H) = 3$▫. |
| Sekundarne ključne besede: | matematika;teorija grafov;graf;kartezični produkt;dominantno število; |
| URN: | URN:SI:UM: |
| Vrsta dela (COBISS): | Znanstveno delo |
| Strani: | str. 5-11 |
| Letnik: | ǂVol. ǂ21 |
| Zvezek: | ǂno. ǂ1 |
| Čas izdaje: | 2001 |
| ID: | 9595946 |
Priporočena dela:
On Vizing's conjecture
2001,
ni podatka o podnaslovu
Vizing's conjecture: a survey and recent results
2009,
ni podatka o podnaslovu
Vizing's conjecture: a survey and recent results
2012,
ni podatka o podnaslovu
Game chromatic number of Cartesian product graphs
2008,
ni podatka o podnaslovu
ǂThe ǂperiphery graph of a median graph
2010,
ni podatka o podnaslovu