✦ LIBER ✦

Covering Graphs: The Covering Problem Solved

✍ Scribed by Yair Caro; Raphael Yuster

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 238 KB
Volume: 83
Category: Article
ISSN: 0097-3165
DOI: 10.1006/jcta.1998.2867

No coin nor oath required. For personal study only.

✦ Synopsis

For every fixed graph H, we determine the H-covering number of K n , for all n>n 0 (H ). We prove that if h is the number of edges of H, and gcd(H )=d is the greatest common divisor of the degrees of H, then there exists n 0 =n 0 (H ), such that for all n>n 0 ,

Our main tool in proving this result is the deep decomposition result of Gustavsson.

📜 SIMILAR VOLUMES

Covering Regular Graphs

✍ Jan Kratochvı́l; Andrzej Proskurowski; Jan Arne Telle 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 365 KB

A covering projection from a graph G onto a graph H is a ``local isomorphism'': a mapping from the vertex set of G onto the vertex set of H such that, for every v # V(G), the neighborhood of v is mapped bijectively onto the neighborhood (in H ) of the image of v. We investigate two concepts that con

The gradual covering problem

✍ Zvi Drezner; George O. Wesolowsky; Tammy Drezner 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 106 KB

Packing and covering dense graphs

✍ Noga Alon; Yair Caro; Raphael Yuster 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 498 KB 👁 1 views

Mixed covering arrays on graphs

✍ Karen Meagher; Lucia Moura; Latifa Zekaoui 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 169 KB

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

Automorphism Groups of Covering Graphs

✍ Norbert Seifter; Vladimir I. Trofimov 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 226 KB

For a large class of finite Cayley graphs we construct covering graphs whose automorphism groups coincide with the groups of lifted automorphisms. As an application we present new examples of 1Â2-transitive and 1-regular graphs.

A dynamic programming algorithm for the

A dynamic programming algorithm for the conditional covering problem on tree graphs

✍ Jennifer A. Horne; J. Cole Smith 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 195 KB 👁 1 views