✦ LIBER ✦

Generalized covering designs and clique coverings

✍ Scribed by Robert F. Bailey; Andrea C. Burgess; Michael S. Cavers; Karen Meagher

Publisher: John Wiley and Sons
Year: 2011
Tongue: English
Weight: 246 KB
Volume: 19
Category: Article
ISSN: 1063-8539
DOI: 10.1002/jcd.20288

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

Clique partitions and clique coverings

✍ Paul Erd'́os; Ralph Faudree; Edward T. Ordman 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 575 KB

Several new tools are presented for determining the number of cliques needed to (edge-)partition a graph. For a graph on n vertices, the clique partition number can grow et-? times as fast as the clique covering number, where c is at least l/64. If in a clique on n vertices, the edges between cn" ve

Covering cliques with spanning bicliques

✍ K�ndgen, Andr� 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 192 KB

The edges of the complete graph on n vertices can be covered by lg n spanning complete bipartite subgraphs. However, the sum of the number of edges in these subgraphs is roughly (n 2 /4)lg n, while a cover consisting of n -1 spanning stars uses only (n -1) 2 edges. We will show that the covering by

Multiple vertex coverings by cliques

✍ Wayne Goddard; Michael A. Henning 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 99 KB

For positive integers m 1 ; . . . ; m k , let f (m 1 ; . . . ; m k ) be the minimum order of a graph whose edges can be colored with k colors such that every vertex is in a clique of cardinality m i , all of whose edges have the ith color for all i ¼ 1; 2; . . . ; k. The value for k ¼ 2 was determin

Covering all cliques of a graph

✍ Zsolt Tuza 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 701 KB

The following conjecture of T. Gallai is proved: If G is a chordal graph on n vertices, such that all its maximal complete subgraphs have order at least 3, then there is a vertex set of cardinality ~n/3 which meets all maximal complete subgraphs of G. Further related results are given.

On clique covers and independence number

On clique covers and independence numbers of graphs

✍ Robert C. Brigham; Ronald D. Dutton 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 485 KB

Dominating sets with small clique coveri

Dominating sets with small clique covering number

✍ Penrice, Stephen G. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 84 KB 👁 2 views

Motivated by earlier work on dominating cliques, we show that if a graph G is connected and contains no induced subgraph isomorphic to P 6 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 cl