✦ LIBER ✦

Reorientations of covering graphs

✍ Scribed by Graham Brightwell; Jaroslav Nešetřil

Publisher: Elsevier Science
Year: 1991
Tongue: English
Weight: 252 KB
Volume: 88
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(91)90004-l

No coin nor oath required. For personal study only.

✦ Synopsis

The aim of this paper is to construct a graph G on n vertices which is a connected covering graph but has 2O(") diagram orientations.

This provides a negative answer to a question of I. Rival.

📜 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

Covering Graphs: The Covering Problem So

Covering Graphs: The Covering Problem Solved

✍ Yair Caro; Raphael Yuster 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 238 KB

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

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.

Covering spaces of locally homogeneous g

Covering spaces of locally homogeneous graphs

✍ Roman Nedela 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 818 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__