On the { k } -domination number of Cartesian products of graphs

Let G □ H denote the Cartesian product of graphs G and H . In this paper, we study the { k } -domination number of Cartesian product of graphs and give a new lower bound of γ { k } ( G □ H ) in terms of packing and { k } -domination numbers of G and H . As applications of this lower bound, we prove...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2009-05, Vol.309 (10), p.3413-3419
Main Authors: Hou, Xinmin, Lu, You
Format: Article
Language:English
Subjects:
[formula omitted]-domination number
Applied sciences
Cartesian product
Combinatorics
Combinatorics. Ordered structures
Computer science
control theory
systems
Designs and configurations
Domination number
Exact sciences and technology
Graph theory
Information retrieval. Graph
Mathematics
Packing number
Sciences and techniques of general use
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Let G □ H denote the Cartesian product of graphs G and H . In this paper, we study the { k } -domination number of Cartesian product of graphs and give a new lower bound of γ { k } ( G □ H ) in terms of packing and { k } -domination numbers of G and H . As applications of this lower bound, we prove that: (i) For k = 1 , the new lower bound improves the bound given by Chen, et al. [G. Chen, W. Piotrowski, W. Shreve, A partition approach to Vizing’s conjecture, J. Graph Theory 21 (1996) 103–111]. (ii) The product of the { k } -domination numbers of two any graphs G and H , at least one of which is a ( ρ , γ ) -graph, is no more than k γ { k } ( G □ H ) . (iii) The product of the { 2 } -domination numbers of any graphs G and H , at least one of which is a ( ρ , γ − 1 ) -graph, is no more than 2 γ { 2 } ( G □ H ) .
ISSN:0012-365X
1872-681X
DOI:10.1016/j.disc.2008.07.030