TAILIEUCHUNG - 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@ suen@ 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 . 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 .

• Báo cáo khoa học
• tài liệu báo cáo nghiên cứu khoa học
• cách trình bày báo cáo
• kiến thức toán học
• báo cáo toán học
• công trình toán học
• Nghiên cứu khoa học
• Phương pháp nghiên cứu khoa học
• Bài giảng Phương pháp nghiên cứu khoa học
• Báo cáo nghiên cứu khoa học
• Trình bày báo cáo nghiên cứu khoa học
• Văn phong sử dụng trong báo cáo khoa học
• Báo cáo khoa học công nghệ
• Đề tài nghiên cứu khoa học
• Nghiên cứu công nghệ làm phân vi sinh
• Báo cáo nghiên cứu phân vi sinh
• Báo cáo tình hình nghiên cứu khoa học
• Mẫu Báo cáo thực hiện nghiên cứu
• Trình bày Báo cáo thực hiện nghiên cứu
• Nội dung Báo cáo thực hiện nghiên cứu
• Hình thức Báo cáo thực hiện nghiên cứu
• Biên bản nghiên cứu khoa học
• Báo cáo khoa học và kỹ thuật
• Đề tài nghiên cứu khoa học y khoa
• Báo cáo nghiên cứu cấp nhà nước
• Nghiên cứu chất lượng chế phẩm thuốc
• Báo cáo nghiên cứu công nghệ sinh học
• Đề tài nghiên cứu thuốc sâu sinh học
• Báo cáo khoa học kỹ thuật
• Báo cáo quản lý chất thải sinh hoạt
• Báo cáo khoa học môi trường
• Nghiên cứu khoa học về môi trường
• Báo cáo nghiên cứu vệ sinh môi trường
• Nghiên cứu tình hình nhiễm độc Cadimi
• Báo cáo chế phẩm sinh học
• Báo cáo nghiên cứu ứng dụng sinh học
• Cách viết báo cáo khoa học
• Quy trình nghiên cứu khoa học
• Báo cáo kết quả nghiên cứu
• báo cáo khoa học
• tuyển tập báo cáo khoa học
• báo cáo ngành toán học
• báo cáo ngành vật lý
• báo cáo ngành chăn nuôi
• Nghiên cứu công nghệ phôi vô tính
• Báo cáo nghiên cứu nông nghiệp
• Báo cáo công nghệ xử lý chất thải
• Báo cáo nghiên cứu khoa học công nghệ
• Kết quả nghiên cứu lúa lai
• Cây lương thực
• Cây thực phẩm
• Một số nguyên tắc nghiên cứu khoa học
• Tiêu chuẩn báo cáo nghiên cứu khoa học
• Nguyên tắc báo cáo khoa học
• Báo cáo nghiên cứu công trình
• Nghiên cứu độ rỗng trong đá chứa dầu khí
• Nghiên cứu công nghệ UV–Fenton
• Nghiên cứu công nghệ xử lý nước thải
• Đề tài y tế đảm bảo an toàn người bệnh
• Báo cáo xây dựng hệ thống y tế
• Kỹ thuật viết báo cáo nghiên cứu
• Viết báo cáo nghiên cứu
• Báo cáo nghiên cứu
• khoa học
• Hình thức soạn thảo văn bản báo cáo
• Báo cáo nghiên cứu nước thải rượu
• Báo cáo công nghệ thiết bị UASB
• Đề tài công nghệ vi sinh
• luận văn mẫu
• người lính việt nam
• sau chiến tranh
• báo cáo ngành triết học
• báo cáo ngành lịch sử
• báo cáo ngành văn học