On Vizing's conjecture
Abstract
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$▫.
Keywords
matematika;teorija grafov;graf;kartezični produkt;dominantno število;mathematics;graph theory;graph;Cartesian product;domination number;
Data
| Language: | English |
|---|---|
| Year of publishing: | 2001 |
| Typology: | 1.01 - Original Scientific Article |
| Organization: | UM FKBV - Faculty of Agriculture |
| UDC: | 519.17 |
| COBISS: |
11010137
|
| ISSN: | 1234-3099 |
| Views: | 912 |
| Downloads: | 87 |
| Average score: | 0 (0 votes) |
| Metadata: |
|
Other data
| Secondary language: | Slovenian |
|---|---|
| Secondary title: | O Vizingovi domnevi |
| Secondary abstract: | 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$▫. |
| Secondary keywords: | matematika;teorija grafov;graf;kartezični produkt;dominantno število; |
| URN: | URN:SI:UM: |
| Type (COBISS): | Scientific work |
| Pages: | str. 5-11 |
| Volume: | ǂVol. ǂ21 |
| Issue: | ǂno. ǂ1 |
| Chronology: | 2001 |
| ID: | 9595946 |
Recommended works:
On Vizing's conjecture
2001,
no subtitle data available
Vizing's conjecture: a survey and recent results
2009,
no subtitle data available
Vizing's conjecture: a survey and recent results
2012,
no subtitle data available
Fair reception and Vizing's conjecture
2009,
no subtitle data available
Game chromatic number of Cartesian product graphs
2008,
no subtitle data available