| Naslov: | A new framework to approach Vizing's conjecture |
|---|
| Avtorji: | ID Brešar, Boštjan (Avtor)
ID Hartnell, Bert L. (Avtor)
ID Henning, Michael A. (Avtor)
ID Kuenzel, Kirsti (Avtor)
ID Rall, Douglas F. (Avtor) |
|---|
| Datoteke: |  Bresar-2021-A_NEW_FRAMEWORK_TO_APPROACH_VIZING.pdf (179,75 KB)
MD5: CAFDC8DCB3BCE06743FB1E3A2F53E3EF
 https://doi.org/10.7151/dmgt
|
|---|
| Jezik: | Angleški jezik |
|---|
| Vrsta gradiva: | Znanstveno delo |
|---|
| Tipologija: | 1.01 - Izvirni znanstveni članek |
|---|
| Organizacija: | FNM - Fakulteta za naravoslovje in matematiko
|
|---|
| Opis: | We introduce a new setting for dealing with the problem of the domination number of the Cartesian product of graphs related to Vizing's conjecture. The new framework unifies two different approaches to the conjecture. The most common approach restricts one of the factors of the product to some class of graphs and proves the inequality of the conjecture then holds when the other factor is any graph. The other approach utilizes the so-called Clark-Suen partition for proving a weaker inequality that holds for all pairs of graphs. We demonstrate the strength of our framework by improving the bound of Clark and Suen as follows: ɣ(X◻Y) ≥ max{1/2ɣ(X) ɣt(Y), 1/2ɣt(X) ɣ(Y)}, where ɣ stands for the domination number, ɣt is the total domination number, and X◻Y is the Cartesian product of graphs X and Y. |
|---|
| Ključne besede: | Cartesian product, total domination, Vizing's conjecture, Clark and Suen bound |
|---|
| Status publikacije: | Objavljeno |
|---|
| Verzija publikacije: | Objavljena publikacija |
|---|
| Poslano v recenzijo: | 21.09.2019 |
|---|
| Datum sprejetja članka: | 15.12.2019 |
|---|
| Založnik: | Technical University Press |
|---|
| Leto izida: | 2021 |
|---|
| Št. strani: | Str. 749-762 |
|---|
| Številčenje: | Letn. 41, Št. 3 |
|---|
| PID: | 20.500.12556/DKUM-89748  |
|---|
| UDK: | 519.17 |
|---|
| COBISS.SI-ID: | 52166915 |
|---|
| DOI: | 10.7151/dmgt.2293 |
|---|
| ISSN pri članku: | 1234-3099 |
|---|
| Datum objave v DKUM: | 09.08.2024 |
|---|
| Število ogledov: | 86 |
|---|
| Število prenosov: | 9 |
|---|
| Metapodatki: |    |
|---|
| Področja: | Ostalo
|
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Skupna ocena: | (0 glasov) |
|---|
| Vaša ocena: | Ocenjevanje je dovoljeno samo prijavljenim uporabnikom. |
|---|
| Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
