Lower bounds estimation of factor‐covering design sizes

Factor‐covering designs have been studied with the aim of making efficient suites of test cases for software testing. One of the major concerns in these studies is the construction of factor‐covering designs of smaller sizes. In this paper, we propose a method of estimating the lower bounds of the sizes. The proposed method is based on two assumptions that a test design has parameters of the same range, and that all the values in the range are tested equally. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 89–99, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10039     

New coverings of t-sets with (t + 1)-sets

The minimum number of k-subsets out of a v-set such that each t-set is contained in at least one k-set is denoted by C(v, k, t). In this article, a computer search for finding good such covering designs, leading to new upper bounds on C(v, k, t), is considered. The search is facilitated by predetermining automorphisms of desired covering designs. A stochastic heuristic search (embedded in the general framework of tabu search) is then used to find appropriate sets of orbits. A table of upper bounds on C(v, t + 1, t) for v 28 and t 8 is given, and the new covering designs are listed. © 1999 John Wiley & Sons, Inc. J. Combin Designs 7: 217–226, 1999     

Constructions for cyclic 3‐designs and improved results on cyclic Steiner quadruple systems

This paper gives some recursive constructions for cyclic 3‐designs. Using these constructions we improve Grannell and Griggs's construction for cyclic Steiner quadruple systems, and many known recursive constructions for cyclic Steiner quadruple systems are unified. Finally, some new infinite families of cyclic Steiner quadruple systems are obtained. © 2010 Wiley Periodicals, Inc. J Combin Designs 19:178‐201, 2011     

Primitive symmetric designs with up to 2500 points

By this article we conclude the construction of all primitive ( v, k,λ ) symmetric designs with v < 2500 , up to a few unsolved cases. Complementary to the designs with prime power number of points published previously, here we give 55 primitive symmetric designs with v ≠ p ^m , p prime and m positive integer, together with the analysis of their full automorphism groups. The research involves programming and wide‐range computations. We make use of the software package GAP and the library of primitive groups which it contains. © 2011 Wiley Periodicals, Inc. J Combin Designs 19:463‐474, 2011     

Correction to: “Exponential bounds on the number of designs with affine parameters”

It is well known that the number of designs with the parameters of a classical design having as blocks the hyperplanes in PG(n, q) or AG(n, q), n?3, grows exponentially. This result was extended recently [5] to designs having the same parameters as a projective geometry design whose blocks are the d‐subspaces of PG(n, q), for any 2?d?n ? 1. In this paper, exponential lower bounds are proved on the number of non‐isomorphic designs having the same parameters as an affine geometry design whose blocks are the d‐subspaces of AG(n, q), for any 2≤d≤n ? 1. Exponential bounds are also proved for the number of resolvable designs with these parameters. © 2011 Wiley Periodicals, Inc. J Combin Designs 19:156‐166, 2011     

Restricted b‐factors in bipartite graphs and t‐designs

We present a new equivalence result between restricted b‐factors in bipartite graphs and combinatorial t‐designs. This result is useful in the construction of t‐designs by polyhedral methods. We propose a novel linear integer programming formulation, which we call GDP, for the problem of finding t‐designs that has a noteworthy advantage compared to the traditional set‐covering formulation. We analyze some polyhedral properties of GPD, implement a branch‐and‐cut algorithm using it and solve several instances of small designs to compare with another point‐block formulation found in the literature. © 2006 Wiley Periodicals, Inc. J Combin Designs 14: 169–182, 2006     

Resolvable candelabra quadruple systems with three groups

Candelabra quadruple systems play an important role in the construction of Steiner 3‐designs. In this article, we consider resolvable candelabra quadruple systems with three groups and show that the necessary conditions on the existence of RCQS(g³: s) when g is even are also sufficient. © 2011 Wiley Periodicals, Inc. J Combin Designs 19:247‐267, 2011     

Equitable resolvable coverings

In an earlier article, Willem H. Haemers has determined the minimum number of parallel classes in a resolvable 2‐(qk,k,1) covering for all k ≥ 2 and q = 2 or 3. Here, we complete the case q = 4, by construction of the desired coverings using the method of simulated annealing. Secondly, we look at equitable resolvable 2‐(qk,k,1) coverings. These are resolvable coverings which have the additional property that every pair of points is covered at most twice. We show that these coverings satisfy k < 2q ? , and we give several examples. In one of these examples, k > q. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 113–123, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10024     

Asymptotic Bounds for General Covering Designs

Given five positive integers and t where and a t‐ general covering design is a pair where X is a set of n elements (called points) and a multiset of k‐subsets of X (called blocks) such that every p‐subset of X intersects at least λ blocks of in at least t points. In this article we continue the work carried out by Etzion, Wei, and Zhang [Des. Codes Cryptogr. 5 (1995), 217–239] on the asymptotic covering density of general covering designs. We will present combinatorial constructions leading to new upper bounds on the asymptotic covering density of 4‐(n, 4, 6, 1) general covering designs and 4‐ general covering designs with . The new bound on the asymptotic covering density of 4‐(n, 4, 6, 1) general covering designs is equivalent to a new lower bound for the Turán density .     

Classification of 6‐(14,7,4) designs with nontrivial automorphism groups

In this paper, we introduce some intersection matrices for t‐designs. Utilizing these matrices together with a modified version of a backtracking algorithm, we classify all 6‐(14,7,4) and 5‐(13,6,4) designs with nontrivial automorphism groups and obtain 13 and 21 such designs, respectively. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 180–194, 2002; Published online in Wiley InterScience ( www.interscience.wiley.com ) DOI 10.1002/jcd.10004     

A Note on q‐Covering Designs in PG(5, q)

A construction of q‐covering designs in PG(5, q) is given, providing an improvement on the upper bound of the q‐covering number .     

Group construction of covering arrays

A covering array t‐CA (n, k, g) is a k × n array on a set of g symbols with the property that in each t × n subarray, every t × 1 column appears at least once. This paper improves many of the best known upper bounds on n for covering arrays, 2‐CA (n, k, g) with g + 1 ≤ k ≤ 2g, for g = 3 · · · 12 by a construction which in many of these cases produces a 2‐CA (n, k, g) with n = k (g ? 1) + 1. The construction is an extension of an algebraic method used by Chateauneuf, Colbourn, and Kreher which uses an array and a group action on the array. © 2004 Wiley Periodicals, Inc. J Combin Designs 13: 70–77, 2005.     

A note on triangle‐free quasi‐symmetric designs

Triangle‐free quasi‐symmetric 2‐ (v, k, λ) designs with intersection numbers x, y; 0<x<y<kand λ>1, are investigated. It is proved that λ?2y ? x ? 3. As a consequence it is seen that for fixed λ, there are finitely many triangle‐free quasi‐symmetric designs. It is also proved that: k?y(y ? x) + x. Copyright © 2011 Wiley Periodicals, Inc. J Combin Designs 19:422‐426, 2011     

New upper bounds on the minimum size of covering designs

Let D = {B₁, B₂,…, B_b} 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     

Adding more observations to saturated D‐optimal resolution III two‐level factorial designs

We consider the class of saturated main effect plans for the 2^k factorial. With these saturated designs, the overall mean and all main effects can be unbiasedly estimated provided that there are no interactions. However, there is no way to estimate the error variance with such designs. Because of this and other reasons, we like to add some additional runs to the set of (k+1) runs in the D‐optimal design in this class. Our goals here are: (1) to search for s additional runs so that the resulting design based on (k+s+1) runs yields a D‐optimal design in the class of augmented designs; (2) to classify all the runs into equivalent classes so that the runs in the same equivalent class give us the same value of the determinant of the information matrix. This allows us to trade runs for runs if this becomes necessary; (3) to obtain upper bounds for determinant of the information matrices of augmented designs. In this article we shall address these approaches and present some new results. © 2002 Wiley Periodicals, Inc. J Combin Designs 11: 51–77, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10026     

Constructing regular self‐complementary uniform hypergraphs

In this article, we examine the possible orders of t‐subset‐regular self‐complementary k‐uniform hypergraphs, which form examples of large sets of two isomorphic t‐designs. We reformulate Khosrovshahi and Tayfeh–Rezaie's necessary conditions on the order of these structures in terms of the binary representation of the rank k, and these conditions simplify to a more transparent relation between the order n and rank k in the case where k is a sum of consecutive powers of 2. Moreover, we present new constructions for 1‐subset‐regular self‐complementary uniform hypergraphs, and prove that these necessary conditions are sufficient for all k, in the case where t = 1. © 2011 Wiley Periodicals, Inc. J Combin Designs 19: 439‐454, 2011     

On DRC‐covering of Kn by cycles

This paper considers the cycle covering of complete graphs motivated by the design of survivable WDM networks, where the requests are routed on INF‐networks which are protected independently from each other. The problem can be stated as follows: for a given graph G, find a cycle covering of the edge set of K_n, where V(K_n) = V(G), such that each cycle in the covering satisfies the disjoint routing constraint (DRC7rpar;, relatively to G, which can be stated as follows: to each edge of K_n we associate in G a path and all the paths associated to the edges of a cycle of the covering must be vertex disjoint. Here we consider the case where G = C_n, a ring of size n and we want to minimize the number of cycles in the covering. We give optimal solutions for the problem as well as for variations of the problem, namely, its directed version and the case when the cycle length is fixed to 4. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 100–112, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10040     

Resolvable minimum coverings with quadruples

Let V be a finite set of v elements. A covering of the pairs of V by k-subsets is a family F of k-subsets of V, called blocks, such that each pair in V occurs in at least one member of F. For fixed v and k, the covering problem is to determine the number of blocks in any minimum covering. A minimum covering is resolvable if we can partition the blocks into classes (called resolution classes) such that every element is contained in precisely one block of each class. A resolvable minimum covering of the pairs of V by k-subsets is denoted by RC(v, k). In this article, we show that there exist RC(v, 4) for v ≡ 0 (mod 4) except for v = 12 and possibly for v ∈ {104, 108, 116, 132, 156, 164, 204, 212, 228, 276}. © 1998 John Wiley & Sons, Inc. J Combin Designs 6: 431–450, 1998     

Intriguing sets in partial quadrangles

The point‐line geometry known as a partial quadrangle (introduced by Cameron in 1975) has the property that for every point/line non‐incident pair (P, ?), there is at most one line through P concurrent with ?. So in particular, the well‐studied objects known as generalized quadrangles are each partial quadrangles. An intriguing set of a generalized quadrangle is a set of points which induces an equitable partition of size two of the underlying strongly regular graph. We extend the theory of intriguing sets of generalized quadrangles by Bamberg, Law and Penttila to partial quadrangles, which gives insight into the structure of hemisystems and other intriguing sets of generalized quadrangles. © 2010 Wiley Periodicals, Inc. J Combin Designs 19:217‐245, 2011     

Antidesigns and regularity of partial spreads in dual polar graphs

We give several examples of designs and antidesigns in classical finite polar spaces. These types of subsets of maximal totally isotropic subspaces generalize the dualization of the concepts of m ‐ovoids and tight sets of points in generalized quadrangles. We also consider regularity of partial spreads and spreads. The techniques that we apply were developed by Delsarte. In some polar spaces of small rank, some of these subsets turn out to be completely regular codes. © 2010 Wiley Periodicals, Inc. J Combin Designs 19: 202‐216, 2011