✦ LIBER ✦

Covering cliques with spanning bicliques

✍ Scribed by K�ndgen, Andr�

Publisher: John Wiley and Sons
Year: 1998
Tongue: English
Weight: 192 KB
Volume: 27
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199804)27:4<223::aid-jgt3>3.0.co;2-p

No coin nor oath required. For personal study only.

✦ Synopsis

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 spanning stars has the smallest total number of edges among all coverings of the clique by spanning complete bipartite subgraphs, except when n is 4 or 8.

📜 SIMILAR VOLUMES

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

Kirkman packing and covering designs wit

Kirkman packing and covering designs with spanned holes of size 2

✍ Jianxing Yin 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 120 KB 👁 1 views

## Abstract 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.