TAILIEUCHUNG - Báo cáo toán học: "Efficient covering designs of the complete graph"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: Efficient covering designs of the complete graph. | Efficient covering designs of the complete graph Yair Caro and Raphael Yuster y Department of Mathematics University of Haifa-ORANIM Tivon 36006 Israel. AMS Subject Classification 05B05 05B40 primary 05B30 51E05 94C30 62K05 62K10 secondary . Submitted November 1 1996 Accepted February 3 1997 Abstract Let H be a graph. We show that there exists n0 n0 H such that for every n n0 there is a covering of the edges of Kn with copies of H where every edge is covered at most twice and any two copies intersect in at most one edge. Furthermore the covering we obtain is asymptotically optimal. 1 Introduction All graphs considered here are finite undirected and simple unless otherwise noted. For the standard graph-theoretic notations the reader is referred to 5 . Let H Vh Eh be a graph. An H-covering design of a graph G Vg Eg is a set L G1 . Gsg of subgraphs of G such that each Gị is isomorphic to H and every edge e 2 EG appears in at least one member of L. The H-covering number of G denoted by cov G H is the minimum number of members in an H-covering design of G. If there is an edge of G which cannot be covered by a copy of H we put cov G H 1 . Clearly cov G H EG EH . In case equality holds the H-covering design is called an H-decomposition or H-design of G. Two trivial necessary conditions for a decomposition are that EH divides EG and that gcd H divides gcd G where the gcd of a graph e-mail zeac603@ y e-mail raphy@ 1 THE ELECTRONIC JOURNAL OF COMBINATORICS 4 1997 R10 2 is the greatest common divisor of the degrees of all the vertices. In case G Kn it was shown by Wilson in 17 that the two necessary conditions are also sufficient provided n n0 H where n0 H is a sufficiently large constant. If however the necessary conditions do not hold the best one could hope for is an H-covering design of Kn where the following three properties hold 1. 2-overlap Every edge is covered at most twice. 2. 1-intersection Any two copies of H intersect in at most one .

• 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ác bài toán hay
• trình bày báo cáo
• báo cáo ngành văn học
• báo cáo tiếng anh
• nghiên cứu văn thơ
• giọng điệu trào phúng
• nghiên cứu khoa học
• báo cáo khoa học
• thơ lục bát
• chính sách phát triển
• gia đình việt nam
• nghiên cứu xã hội