Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "An Inequality Related to Vizing’s Conjecture"

Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: An Inequality Related to Vizing’s Conjecture. | An Inequality Related to Vizing s Conjecture W. Edwin Clark and Stephen Suen Department of Mathematics University of South Florida Tampa FL 33620-5700 USA eclark@math.usf.edu suen@math.usf.edu Submitted November 29 1999 Accepted May 24 2000 Abstract Let y G denote the domination number of a graph G and let G H denote the Cartesian product of graphs G and H. We prove that y G y H 2y G H for all simple graphs G and H. 2000 Mathematics Subject Classifications Primary 05C69 Secondary 05C35 We use V G E G Y G respectively to denote the vertex set edge set and domination number of the simple graph G. For a pair of graphs G and H the Cartesian product G H of G and H is the graph with vertex set V G X V H and where two vertices are adjacent if and only if they are equal in one coordinate and adjacent in the other. In 1963 V. G. Vizing 2 conjectured that for any graphs G and H Y G y H Y G H . 1 The reader is referred to Hartnell and Rall 1 for a summary of recent progress on Vizing s conjecture. We note that there are graphs G and H for which equality holds in 1 . However it was previously unknown 1 whether there exists a constant c such that y G y H c y G H . We shall show in this note that Y G y H 2 y G H . For S c V G we let NG S denote the set of vertices in V G that are in S or adjacent to a vertex in S i.e. the set of vertices in V G dominated by vertices in S. 1 THE ELECTRONIC .JOURNAL OF COMBINATORICS 7 2000 N4 2 Theorem 1 For any graphs G and H iG H 2y G H . Proof. Let D be a dominating set of G H. It is sufficient to show that y G y H 2 D . 2 Let u1 u2 . uY G be a dominating set of G. Form a partition Hl n2 . nY G of V G so that for all i i ui 2 n and ii u 2 ni implies u u or u is adjacent to ui. This partition of V G induces a partition D1 D2 . DY G of D where Di Hi X V H n D. Let Pi be the projection of Di onto H. That is Pi v u v 2 Di for some u 2 ni . Observe that for any i Pi u V H NH Pi is a dominating set of H and hence the number of vertices in V H not .