Vizing's conjecture: A survey and recent results

Boštjan Brešar; Paul Dorbec; Wayne Goddard; Bert L. Hartnell; Michael A. Henning; Sandi Klavžar; And Douglas F. Rall

doi:10.1002/jgt.20565

Vizing's conjecture: A survey and recent results

Boštjan Brešar, Paul Dorbec, Wayne Goddard, Bert L. Hartnell, Michael A. Henning, Sandi Klavžar, And Douglas F. Rall

Mathematics and Applied Mathematics

Research output: Contribution to journal › Article › peer-review

82 Citations (Scopus)

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.

Original language	English
Pages (from-to)	46-76
Number of pages	31
Journal	Journal of Graph Theory
Volume	69
Issue number	1
DOIs	https://doi.org/10.1002/jgt.20565
Publication status	Published - Jan 2012

Keywords

Cartesian product
Vizing's conjecture
domination

ASJC Scopus subject areas

Geometry and Topology
Discrete Mathematics and Combinatorics

Access to Document

10.1002/jgt.20565

Cite this

@article{3c7b92a5586149cfb9ae899fca02b9a1,

title = "Vizing's conjecture: A survey and recent results",

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.",

keywords = "Cartesian product, Vizing's conjecture, domination",

author = "Bo{\v s}tjan Bre{\v s}ar and Paul Dorbec and Wayne Goddard and Hartnell, {Bert L.} and Henning, {Michael A.} and Sandi Klav{\v z}ar and Rall, {And Douglas F.}",

year = "2012",

month = jan,

doi = "10.1002/jgt.20565",

language = "English",

volume = "69",

pages = "46--76",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "1",

}

TY - JOUR

T1 - Vizing's conjecture

T2 - A survey and recent results

AU - Brešar, Boštjan

AU - Dorbec, Paul

AU - Goddard, Wayne

AU - Hartnell, Bert L.

AU - Henning, Michael A.

AU - Klavžar, Sandi

AU - Rall, And Douglas F.

PY - 2012/1

Y1 - 2012/1

N2 - 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.

AB - 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.

KW - Cartesian product

KW - Vizing's conjecture

KW - domination

UR - http://www.scopus.com/inward/record.url?scp=81955168121&partnerID=8YFLogxK

U2 - 10.1002/jgt.20565

DO - 10.1002/jgt.20565

M3 - Article

AN - SCOPUS:81955168121

SN - 0364-9024

VL - 69

SP - 46

EP - 76

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 1

ER -

Vizing's conjecture: A survey and recent results

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this