Journal
JOURNAL OF GRAPH THEORY
Volume 61, Issue 1, Pages 45-54Publisher
WILEY
DOI: 10.1002/jgt.20366
Keywords
Cartesian product of graphs; domination; Vizing's conjecture
Categories
Funding
- The Ministry of Science of Slovenia [PI-0297]
Ask authors/readers for more resources
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 gamma(G) satisfy Vizing's conjecture on the domination number of Cartesian product graphs, by which we extend the well-known result of Barcalkin and German concerning decomposable graphs. Combining our concept with a result of Aharoni, Berger and Ziv, we obtain an alternative proof of the theorem of Aharoni and Szabo that chordal graphs satisfy Vizing's conjecture. A new infinite family of graphs that satisfy Vizing's conjecture is also presented. (c) 2009 Wiley Periodicals, Inc. J Graph Theory 61: 45-54, 2009
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available