A New Framework to Approach Vizing's Conjecture

Boštjan Brešar, Bert L. Hartnell, Michael A. Henning, Kirsti Kuenzel, Douglas F. Rall

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)

Abstract

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 γ(X□Y)≥max12γ(X)γt(Y),12γ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.

Original languageEnglish
Pages (from-to)749-762
Number of pages14
JournalDiscussiones Mathematicae - Graph Theory
Volume41
Issue number3
DOIs
Publication statusPublished - 1 Aug 2021

Keywords

  • Cartesian product
  • Clark and Suen bound
  • Vizing's conjecture
  • total domination

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'A New Framework to Approach Vizing's Conjecture'. Together they form a unique fingerprint.

Cite this