Paired-domination of Cartesian products of graphs and rainbow domination

Boštjan Brešar; Michael A. Henning; Douglas F. Rall

doi:10.1016/j.endm.2005.06.059

Paired-domination of Cartesian products of graphs and rainbow domination

Boštjan Brešar, Michael A. Henning, Douglas F. Rall

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

38 Citations (Scopus)

Abstract

The most famous open problem involving domination in graphs is Vizing's conjecture which states the domination number of the Cartesian product of any two graphs is at least as large as the product of their domination numbers. We investigate a similar problem for paired-domination, and obtain a lower bound in terms of product of domination number of one factor and 3-packing of the other factor. Some results are obtained by applying a new graph invariant called rainbow domination.

Original language	English
Pages (from-to)	233-237
Number of pages	5
Journal	Electronic Notes in Discrete Mathematics
Volume	22
DOIs	https://doi.org/10.1016/j.endm.2005.06.059
Publication status	Published - 15 Oct 2005
Externally published	Yes

Keywords

3-packing
Vizing's conjecture
graph products
paired-domination

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/j.endm.2005.06.059

Cite this

@article{be65d5c6a62a44db8fd84917eb956f2f,

title = "Paired-domination of Cartesian products of graphs and rainbow domination",

abstract = "The most famous open problem involving domination in graphs is Vizing's conjecture which states the domination number of the Cartesian product of any two graphs is at least as large as the product of their domination numbers. We investigate a similar problem for paired-domination, and obtain a lower bound in terms of product of domination number of one factor and 3-packing of the other factor. Some results are obtained by applying a new graph invariant called rainbow domination.",

keywords = "3-packing, Vizing's conjecture, graph products, paired-domination",

author = "Bo{\v s}tjan Bre{\v s}ar and Henning, {Michael A.} and Rall, {Douglas F.}",

year = "2005",

month = oct,

day = "15",

doi = "10.1016/j.endm.2005.06.059",

language = "English",

volume = "22",

pages = "233--237",

journal = "Electronic Notes in Discrete Mathematics",

issn = "1571-0653",

publisher = "Elsevier",

}

TY - JOUR

T1 - Paired-domination of Cartesian products of graphs and rainbow domination

AU - Brešar, Boštjan

AU - Henning, Michael A.

AU - Rall, Douglas F.

PY - 2005/10/15

Y1 - 2005/10/15

N2 - The most famous open problem involving domination in graphs is Vizing's conjecture which states the domination number of the Cartesian product of any two graphs is at least as large as the product of their domination numbers. We investigate a similar problem for paired-domination, and obtain a lower bound in terms of product of domination number of one factor and 3-packing of the other factor. Some results are obtained by applying a new graph invariant called rainbow domination.

AB - The most famous open problem involving domination in graphs is Vizing's conjecture which states the domination number of the Cartesian product of any two graphs is at least as large as the product of their domination numbers. We investigate a similar problem for paired-domination, and obtain a lower bound in terms of product of domination number of one factor and 3-packing of the other factor. Some results are obtained by applying a new graph invariant called rainbow domination.

KW - 3-packing

KW - Vizing's conjecture

KW - graph products

KW - paired-domination

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

U2 - 10.1016/j.endm.2005.06.059

DO - 10.1016/j.endm.2005.06.059

M3 - Article

AN - SCOPUS:34247118369

SN - 1571-0653

VL - 22

SP - 233

EP - 237

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

ER -

Paired-domination of Cartesian products of graphs and rainbow domination

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this