Premium
A partition approach to Vizing's conjecture
Author(s) -
Chen Guantao,
Piotrowski Wiktor,
Shreve Warren
Publication year - 1996
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199601)21:1<103::aid-jgt13>3.0.co;2-m
Subject(s) - combinatorics , cartesian product , mathematics , domination analysis , conjecture , partition (number theory) , product (mathematics) , upper and lower bounds , graph , discrete mathematics , geometry , mathematical analysis , vertex (graph theory)
In 1963, Vizing [ Vichysl.Sistemy 9 (1963), 30–43] conjectured that γ( G × H ) ≥ γ( G )γ( H ), where G × H denotes the cartesian product of graphs, and γ( G ) is the domination number. In this paper we define the extraction number x ( G ) and we prove thatP 2 ( G ) ≤ x(G ), and γ( G × H ) ≥ x(G )γ( H ),where P 2 ( G ) is the 2‐packing number of G . Though the equality x ( G ) = γ( G ) is proven to hold in several classes of graphs, we construct an infinite family of graphs which do not satisfy this condition. Also, we show the following lower bound: γ( G × H ) ≥ γ( G)P 2 ( H ) + P 2 ( G )(γ( H ) − P 2 ( H )). © 1996 John Wiley & Sons, Inc.