共查询到20条相似文献,搜索用时 15 毫秒
1.
D.T Todorov 《Journal of Combinatorial Theory, Series A》1985,39(1):83-101
Let n ? k ? t be positive integers, and let Ω be a set of n elements. Let C(n, k, t) denote the number of k-tuples of Ω in a minimal system of k-tuples such that every t-tuple is contained in at least one k-tuple of the system. C(n, k, t) has been determined in all cases for which [W. H. Mills, Ars Combinatoria8 (1979), 199–315]. C(n, k, t) is determined in the case . 相似文献
2.
3.
A(v, k, t) covering design, or covering, is a family of k-subnets, called blocks, chosen from a v-set, such that each t-subnet is contained in at least one of the blocks. The number of blocks is the covering's size, and the minimum size of such a covering is denoted by C(v,k,t). This paper gives three new methods for constructing good coverings; a greedy algorithm similar to Conway and Sloane's algorithm for lexicographic codes [6], and two methods that synthesize new coverings from preexisting ones. Using these new methods, together with results in the literature, we build tables of upper bounds on C(v,k,t) for v ? 32, k ? 16, and t ? 8. © 1995 John Wiley & Sons, Inc. 相似文献
4.
5.
François Margot 《Mathematical Programming》2003,94(2-3):207-220
A Branch-and-Cut algorithm for finding covering designs is presented. Its originality resides in the use of isomorphism pruning
of the enumeration tree. A proof that no 4-(10, 5, 1)-covering design with less than 51 sets exists is obtained together with
all non isomorphic 4-(10, 5, 1)-covering designs with 51 sets.
Received: August 16, 2000 / Accepted: July 18, 2001 Published online: September 5, 2002 相似文献
6.
Jianxing Yin 《Discrete Mathematics》2009,309(6):1422-1434
A Kirkman holey covering design, denoted by KHCD(gu), is a resolvable group-divisible covering design of type gu. Each of its parallel class contains one block of size δ, while other blocks have size 3. Here δ is equal to 2, 3 and 4 when gu≡2, 3 and 4 (mod 3) in turn. In this paper, we study the existence problem of a KHCD(gu) which has minimum possible number of parallel classes, and give a solution for most values of even g and u. 相似文献
7.
Inspired by the “generalized t‐designs” defined by Cameron [P. J. Cameron, Discrete Math 309 (2009), 4835–4842], we define a new class of combinatorial designs which simultaneously provide a generalization of both covering designs and covering arrays. We then obtain a number of bounds on the minimum sizes of these designs, and describe some methods of constructing them, which in some cases we prove are optimal. Many of our results are obtained from an interpretation of these designs in terms of clique coverings of graphs. © 2011 Wiley Periodicals, Inc. J Combin Designs 19:378‐406, 2011 相似文献
8.
9.
In this article we look at pair covering designs with a block size of 5 and . The number of blocks in a minimum covering design is known as the covering number C(v,5,2). For v?24, these values are known, and all but v=8 exceed the Schönheim bound, L(v,5,2)=⌈v/5⌈(v-1)/4⌉⌉. However, for all v?28 with , it seems probable that C(v,5,2)=L(v,5,2). We establish this for all but 17 possible exceptional values lying in the range 40?v?280. 相似文献
10.
《组合设计杂志》2018,26(3):101-118
Group divisible covering designs (GDCDs) were introduced by Heinrich and Yin as a natural generalization of both covering designs and group divisible designs. They have applications in software testing and universal data compression. The minimum number of blocks in a k‐GDCD of type is a covering number denoted by . When , the values of have been determined completely for all possible pairs . When , Francetić et al. constructed many families of optimal GDCDs, but the determination remained far from complete. In this paper, two specific 4‐IGDDs are constructed, thereby completing the existence problem for 4‐IGDDs of type . Then, additional families of optimal 4‐GDCDs are constructed. Consequently the cases for whose status remains undetermined arise when and , when and , and in several small families for which one of g and u is fixed. 相似文献
11.
12.
Ahmed M. Assaf 《Designs, Codes and Cryptography》1995,5(2):91-107
LetV be a finite set of order . A (, , ) covering design of index and block size is a collection of -element subsets, called blocks, such that every 2-subset ofV occurs in at least blocks. The covering problem is to determine the minimum number of blocks, (, , ), in a covering design. It is well known that
, where [x] is the smallest integer satisfyingx[X]. It is shown here that (, 5, 5)=(, 5, 5) for all positive integers 5 with the possible exception of =24, 28, 56, 104, 124, 144, 164, 184. 相似文献
13.
《Discrete Mathematics》1986,59(3):275-281
A packing (respectively covering) design of order v, block size k, and index λ is a collection of k-element subsets, called blocks, of a v-set, V, such that every 2-subset of V occurs in at most (at least) λ blocks. The packing (covering) problem is to determine the maximum (minimum) number of blocks in a packing (covering) design. Motivated by the recent work of Assaf [1] [2], we solve the outstanding packing and covering problems with block size 4. 相似文献
14.
Let D = {B1, B2,…, Bb} be a finite family of k-subsets (called blocks ) of a v-set X(v) = {1, 2,…, v} (with elements called points ). Then D is a (v, k, t) covering design or covering if every t-subset of X(v) is contained in at least one block of D. The number of blocks, b, is the size of the covering, and the minimum size of the covering is called the covering number , denoted C(v, k, t). This article is concerned with new constructions of coverings. The constructions improve many upper bounds on the covering number C(v, k, t) © 1998 John Wiley & Sons, Inc. J Combin Designs 6:21–41, 1998 相似文献
15.
Jianxing Yin 《组合设计杂志》2005,13(3):173-183
A Kirkman holey packing (resp. covering) design, denoted by KHPD(gu) (resp. KHCD(gu)), is a resolvable (gu, 3, 1) packing (resp. covering) design of pairs with u disjoint holes of size g, which has the maximum (resp. minimum) possible number of parallel classes. Each parallel class contains one block of size δ, while other blocks have size 3. Here δ is equal to 2, 3, and 4 when gu ≡ 2, 3, and 4 (mod 3) in turn. In this paper, the existence problem of a KHPD(2u) and a KHCD(2u) is solved with one possible exception of a KHPD(28). © 2004 Wiley Periodicals, Inc. 相似文献
16.
Darryn Bryant Melinda Buchanan Daniel Horsley Barbara Maenhaut Victor Scharaschkin 《Combinatorica》2011,31(5):507-528
We establish new lower bounds on the pair covering number C
λ
(υ,k) for infinitely many values of υ, k and λ, including infinitely many values of υ and k for λ=1. Here, C
λ
(υ,k) denotes the minimum number of k-subsets of a υ-set of points such that each pair of points occurs in at least λ of the k-subsets. We use these results to prove simple numerical conditions which are both necessary and sufficient for the existence
of (K
k
− e)-designs with more points than blocks. 相似文献
17.
18.
The purpose of this paper is to present new upper bounds for code distance and covering radius of designs in arbitrary polynomial metric spaces. These bounds and the necessary and sufficient conditions of their attainability were obtained as the solution of an extremal problem for systems of orthogonal polynomials. For antipodal spaces the behaviour of the bounds in different asymptotical processes is determined and it is proved that this bound is attained for all tight 2k-design. 相似文献
19.
A t-(v, k, λ) covering design is a pair (X, B) where X is a v-set and B is a collection of k-sets in X, called blocks, such that every t element subset of X is contained in at least λ blocks of B. The covering number, Cλ(t, k, v), is the minimum number of blocks a t-(v, k, λ) covering design may have. The chromatic number of (X, B) is the smallest m for which there exists a map φ: X → Zm such that ∣φ((β)∣ ≥2 for all β ∈ B, where φ(β) = {φ(x): x ∈ β}. The system (X, B) is equitably m-chromatic if there is a proper coloring φ with minimal m for which the numbers ∣φ?1(c)∣ c ∈ Zm differ from each other by at most 1. In this article we show that minimum, (i.e., ∣B∣ = C λ (t, k, v)) equitably 3-chromatic 3-(v, 4, 1) covering designs exist for v ≡ 0 (mod 6), v ≥ 18 for v ≥ 1, 13 (mod 36), v ≡ 13 and for all numbers v = n, n + 1, where n ≡ 4, 8, 10 (mod 12), n ≥ 16; and n = 6.5a 13b 17c ?4, a + b + c > 0, and n = 14, 62. We also show that minimum, equitably 2-chromatic 3-(v, 4, 1) covering designs exist for v ≡ 0, 5, 9 (mod 12), v ≥ 0, v = 2.5a 13b 17c + 1, a + b + c > 0, and v = 23. © 1993 John Wiley & Sons, Inc. 相似文献