✦ LIBER ✦

Vizing's conjecture: a survey and recent results

✍ Scribed by Boštjan Brešar,; Paul Dorbec,; Wayne Goddard,; Bert L. Hartnell,; Michael A. Henning,; Sandi Klavžar;; and Douglas F. Rall

Publisher: John Wiley and Sons
Year: 2011
Tongue: English
Weight: 380 KB
Volume: 69
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20565

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Vizing's conjecture from 1968 asserts that the domination number of the Cartesian product of two graphs is at least as large as the product of their domination numbers. In this paper we survey the approaches to this central conjecture from domination theory and give some new results along the way. For instance, several new properties of a minimal counterexample to the conjecture are obtained and a lower bound for the domination number is proved for products of claw‐free graphs with arbitrary graphs. Open problems, questions and related conjectures are discussed throughout the paper. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 46–76, 2012

📜 SIMILAR VOLUMES

Fair reception and Vizing's conjecture

✍ Boštjan Brešar; Douglas F. Rall 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 150 KB

## Abstract In this paper 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 γ(__G__) satisfy Vizing's conjecture on the domination number of Cartesian product graphs, by which we extend the w

A partition approach to Vizing's conject

A partition approach to Vizing's conjecture

✍ Chen, Guantao; Piotrowski, Wiktor; Shreve, Warren 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 411 KB 👁 1 views

In 1963, Vizing [Vichysl. Sistemy 9 (19631, 30-431 conjectured that y ( G X H) 2 y ( G ) y ( H ) , where G X Hdenotes the Cartesian product of graphs, and y(G) is the domination number. In this paper we define the extraction number x(G) and w e prove that ## M G ) 5 x(G) 5 y(G), and y ( G x H) 2 x