20.500.12556/DKUM-89748 A new framework to approach Vizing's conjecture Pakirna barvanja podkubičnih zunanje ravninskih grafov 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. V članku vpeljemo nov okvir za reševanje problema dominantnega števila kartezičnega produkta grafov, ki je povezan z Vizingovo domnevo. Novi okvir združi dva različna pristopa k domnevi. V najbolj standardnem pristopu se v enem faktorju produkta omejimo na neki razred grafov in dokažemo domnevano neenakost, pri čemer je drugi faktor produkta poljuben graf. Drugi pristop uporablja tako imenovano particijo Clarka in Suena, s katero se dokaže neka šibkejša neenakost za vse pare grafov. Moč našega novega pristopa demonstriramo z izboljšavo meje Clarka in Suena na naslednji način: ɣ(X◻Y) ≥ max{1/2ɣ(X) ɣt(Y), 1/2ɣt(X) ɣ(Y)}, kjer je ɣ dominantno število grafa, ɣt njegovo celotno dominantno število, X◻Y pa kartezični produkt grafov X in Y. Cartesian product total domination Vizing's conjecture Clark and Suen bound kartezični produkt celotna dominacija Vizingova domneva meja Clarka in Suena true false true Technical University Press Angleški jezik Slovenski jezik Znanstveno delo 2024-08-09 08:59:23 2024-08-09 09:32:02 2024-08-10 03:47:44 0000-00-00 00:00:00 2021 0 0 Str. 749-762 Št. 3 Letn. 41 2021 0000-00-00 Zaloznikova Objavljeno NiDoloceno 2019-09-21 2019-12-15 0000-00-00 519.17 52166915 10.7151/dmgt.2293 1234-3099 Bresar-2021-A_NEW_FRAMEWORK_TO_APPROACH_VIZING.pdf Bresar-2021-A_NEW_FRAMEWORK_TO_APPROACH_VIZING.pdf 1 CAFDC8DCB3BCE06743FB1E3A2F53E3EF cdb84ba85a3ff65b70fc1bfda64332c21e0087e27f5f0f800459cbc1e6516f03 4db2637c-5620-11ef-97b6-00155d000105 https://dk.um.si/Dokument.php?lang=slv&id=182172 https://doi.org/10.7151/dmgt 0 eaf8246a-561c-11ef-97b6-00155d000105 https://dk.um.si/Dokument.php?lang=slv&id=182167 Fakulteta za naravoslovje in matematiko 0 0 0