Fair reception and Vizing's conjecture
Abstract
Vpeljemo koncept poštenega sprejema grafa, ki je povezan z njegovim dominantnim številom. Dokažemo, da za vse grafe, ki imajo pošten sprejem velikosti njihovega dominantnega števila, velja Vizingova domneva o dominantnem številu kartezičnega produkta grafov, s čimer posplošimo dobro znan rezultat Barcalkina in Germana o razstavljivih grafih. S kombiniranjem na\v sega koncepta in rezultata Aharonija, Bergerja in Ziva dobimo alternativen dokaz izreka Aharonija in Szaba, ki pravi, da tetivni grafi zadoščajo Vizingovi domnevi. Predstavimo tudi novo neskončno družino grafov, ki zadoščajo Vizingovi domnevi.
Keywords
matematika;teorija grafov;dominacija;kartezični produkt grafov;Vizingova domneva;mathematics;graph theory;domination;Cartesian product of graphs;Vizing's conjecture;
Data
| Language: | English |
|---|---|
| Year of publishing: | 2009 |
| Typology: | 1.01 - Original Scientific Article |
| Organization: | UM FNM - Faculty of Natural Sciences and Mathematics |
| UDC: | 519.17 |
| COBISS: |
15170393
|
| ISSN: | 0364-9024 |
| Views: | 785 |
| Downloads: | 93 |
| Average score: | 0 (0 votes) |
| Metadata: |
|
Other data
| Secondary language: | Unknown |
|---|---|
| Secondary title: | Pošten sprejem in Vizingova domneva |
| Secondary abstract: | We introduce the concept of fair reception of a graph which is related to its domination number. We prove that all graphs ▫$G$▫ with a fair reception of size ▫$\gamma(G)$▫ satisfy Vizing's conjecture on the domination number of Cartesian product graphs, by which we extend the well-known result of Barcalkin and German concerning decomposable graphs. Combining our concept with a result of Aharoni, Berger and Ziv, we obtain an alternative proof of the theorem of Aharoni and Szabó that chordal graphs satisfy Vizing's conjecture. A new infinite family of graphs that satisfy Vizing's conjecture is also presented. |
| URN: | URN:SI:UM: |
| Type (COBISS): | Not categorized |
| Pages: | str. 45-54 |
| Volume: | ǂVol. ǂ61 |
| Issue: | ǂno. ǂ1 |
| Chronology: | 2009 |
| ID: | 1474309 |
Recommended works:
Fair reception and Vizing's conjecture
2009,
no subtitle data available
Vizing's conjecture: a survey and recent results
2009,
no subtitle data available
On Vizing's conjecture
2001,
no subtitle data available
Vizing's conjecture: a survey and recent results
2012,
no subtitle data available
Behzad-Vizing conjecture and Cartesian-product graphs
2004,
no subtitle data available