Fair reception and Vizing's conjecture
Povzetek
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.
Ključne besede
matematika;teorija grafov;dominacija;kartezični produkt grafov;Vizingova domneva;mathematics;graph theory;domination;Cartesian product of graphs;Vizing's conjecture;
Podatki
| Jezik: | Angleški jezik |
|---|---|
| Leto izida: | 2009 |
| Tipologija: | 1.01 - Izvirni znanstveni članek |
| Organizacija: | UM FNM - Fakulteta za naravoslovje in matematiko |
| UDK: | 519.17 |
| COBISS: |
15170393
|
| ISSN: | 0364-9024 |
| Št. ogledov: | 785 |
| Št. prenosov: | 93 |
| Ocena: | 0 (0 glasov) |
| Metapodatki: |
|
Ostali podatki
| Sekundarni jezik: | Neznan jezik |
|---|---|
| Sekundarni naslov: | Pošten sprejem in Vizingova domneva |
| Sekundarni povzetek: | 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: |
| Vrsta dela (COBISS): | Delo ni kategorizirano |
| Strani: | str. 45-54 |
| Letnik: | ǂVol. ǂ61 |
| Zvezek: | ǂno. ǂ1 |
| Čas izdaje: | 2009 |
| ID: | 1474309 |
Priporočena dela:
Fair reception and Vizing's conjecture
2009,
ni podatka o podnaslovu
Vizing's conjecture: a survey and recent results
2009,
ni podatka o podnaslovu
On Vizing's conjecture
2001,
ni podatka o podnaslovu
Vizing's conjecture: a survey and recent results
2012,
ni podatka o podnaslovu
Behzad-Vizing conjecture and Cartesian-product graphs
2004,
ni podatka o podnaslovu