Dominating sets with small clique covering number

Motivated by earlier work on dominating cliques, we show that if a graph G is connected and contains no induced subgraph isomorphic to P₆ or H_t (the graph obtained by subdividing each edge of K_1,t, t ≥ 3, by exactly one vertex), then G has a dominating set which induces a connected graph with clique covering number at most t − 1. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 101–105, 1997     

On asymmetric coverings and covering numbers

An asymmetric covering is a collection of special subsets S of an n‐set such that every subset T of the n‐set is contained in at least one special S with . In this paper we compute the smallest size of any for We also investigate “continuous” and “banded” versions of the problem. The latter involves the classical covering numbers , and we determine the following new values: , , , , and . We also find the number of non‐isomorphic minimal covering designs in several cases. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 218–228, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10022     

Kirkman covering designs with even-sized holes

A Kirkman holey covering design, denoted by KHCD(g^u), is a resolvable group-divisible covering design of type g^u. 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(g^u) which has minimum possible number of parallel classes, and give a solution for most values of even g and u.     

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     

Edge clique cover of claw-free graphs

The smallest number of cliques, covering all edges of a graph , is called the (edge) clique cover number of and is denoted by . It is an easy observation that if is a line graph on vertices, then . G. Chen et al. [Discrete Math. 219 (2000), no. 1–3, 17–26; MR1761707] extended this observation to all quasi-line graphs and questioned if the same assertion holds for all claw-free graphs. In this paper, using the celebrated structure theorem of claw-free graphs due to Chudnovsky and Seymour, we give an affirmative answer to this question for all claw-free graphs with independence number at least three. In particular, we prove that if is a connected claw-free graph on vertices with three pairwise nonadjacent vertices, then and the equality holds if and only if is either the graph of icosahedron, or the complement of a graph on vertices called “twister” or the power of the cycle , for some positive integer .     

Optimal and near-optimal mixed covering arrays by column expansion

This paper describes constructions for strength-2 mixed covering arrays developed from index-1 orthogonal arrays, ordered designs and covering arrays. The constructed arrays have optimal or near-optimal sizes. Conditions for achieving optimal size are described. An optimization among the different ingredient arrays to maximize the number of factors of each alphabet size is also presented.     

Kirkman packing and covering designs with spanned holes of size 2

A Kirkman holey packing (resp. covering) design, denoted by KHPD(g^u) (resp. KHCD(g^u)), 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(2^u) and a KHCD(2^u) is solved with one possible exception of a KHPD(2⁸). © 2004 Wiley Periodicals, Inc.     

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.     

Iterated clique graphs with increasing diameters

A simple argument by Hedman shows that the diameter of a clique graph G differs by at most one from that of K(G), its clique graph. Hedman described examples of a graph G such that diam(K(G)) = diam(G) + 1 and asked in general about the existence of graphs such that diam(Kⁱ(G)) = diam(G) + i. Examples satisfying this equality for i = 2 have been described by Peyrat, Rall, and Slater and independently by Balakrishnan and Paulraja. The authors of the former work also solved the case i = 3 and i = 4 and conjectured that such graphs exist for every positive integer i. The cases i ≥ 5 remained open. In the present article, we prove their conjecture. For each positive integer i, we describe a family of graphs G such that diam(Kⁱ(G)) = diam(G) + i. © 1998 John Wiley & Sons, Inc. J. Graph Theory 28: 147–154, 1998     

Products of mixed covering arrays of strength two

A covering array CA(N;t,k, v is an N × k array such that every N × t subarray contains all t‐tuples from v symbols at least once, where t is the strength of the array. Covering arrays are used to generate software test suites to cover all t‐sets of component interactions. The particular case when t = 2 (pairwise coverage) has been extensively studied, both to develop combinatorial constructions and to provide effective algorithmic search techniques. In this paper, a simple “cut‐and‐paste” construction is extended to covering arrays in which different columns (factors) admit different numbers of symbols (values); in the process an improved recursive construction for covering arrays with t = 2 is derived. © 2005 Wiley Periodicals, Inc. J Combin Designs 14: 124–138, 2006     

Group divisible covering designs with block size four

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 $g^u$ is a covering number denoted by $C(k,g^u)$. When $k=3$, the values of $C(3,g^u)$ have been determined completely for all possible pairs $(g,u)$. When $k=4$, 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 ${(g,h)}^u$. Then, additional families of optimal 4‐GDCDs are constructed. Consequently the cases for $(g,u)$ whose status remains undetermined arise when $g\equiv 7mod12$ and $u\equiv 3mod6$, when $g\equiv 11,14,17,23mod24$ and $u\equiv 5mod6$, and in several small families for which one of g and u is fixed.     

Mixed covering arrays on graphs

Covering arrays have applications in software, network and circuit testing. In this article, we consider a generalization of covering arrays that allows mixed alphabet sizes as well as a graph structure that specifies the pairwise interactions that need to be tested. Let k and n be positive integers, and let G be a graph with k vertices v₁,v₂,…, v_k with respective vertex weights g₁ ≤ g₂ ≤ … ≤ g_k. A mixed covering array on G, denoted by , is an n × k array such that column i corresponds to v_i, cells in column i are filled with elements from ?_gi and every pair of columns i,j corresponding to an edge v_i,v_j in G has every possible pair from ?_gi × ?_gj appearing in some row. The number of rows in such array is called its size. Given a weighted graph G, a mixed covering array on G with minimum size is called optimal. In this article, we give upper and lower bounds on the size of mixed covering arrays on graphs based on graph homomorphisms. We provide constructions for covering arrays on graphs based on basic graph operations. In particular, we construct optimal mixed covering arrays on trees, cycles and bipartite graphs; the constructed optimal objects have the additional property of being nearly point balanced. © 2007 Wiley Periodicals, Inc. J Combin Designs 15: 393–404, 2007     

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     

On covering graphs by complete bipartite subgraphs

We prove that, if a graph with e edges contains m vertex-disjoint edges, then m²/e complete bipartite subgraphs are necessary to cover all its edges. Similar lower bounds are also proved for fractional covers. For sparse graphs, this improves the well-known fooling set lower bound in communication complexity. We also formulate several open problems about covering problems for graphs whose solution would have important consequences in the complexity theory of boolean functions.     

Variable strength covering arrays

We define and study variable strength covering arrays (also called covering arrays on hypergraphs), which are generalizations of covering arrays and covering arrays on graphs. Variable strength covering arrays have the potential for use in software testing, allowing the engineer to omit the parameter combinations known to not interact in order to reduce the number of tests required. The present paper shows that variable strength covering arrays are relevant combinatorial objects that have deep connections with hypergraph homomorphisms and generalize other important combinatorial designs. We give optimal constructions for special types of hypergraphs, constructions based on columns with uniform occurrence of symbols, and constructions for mixed alphabets.     

On the state of strength‐three covering arrays

A covering array of size N, strength t, degree k, and order υ is a k × N array on υ symbols in which every t × N subarray contains every possible t × 1 column at least once. We present explicit constructions, constructive upper bounds on the size of various covering arrays, and compare our results with those of a commercial product. Applications of covering arrays include software testing, drug screening, and data compression. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 217–238, 2002; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10002