✦ LIBER ✦

Covering Regular Graphs

✍ Scribed by Jan Kratochvı́l; Andrzej Proskurowski; Jan Arne Telle

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 365 KB
Volume: 71
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1996.1743

No coin nor oath required. For personal study only.

✦ Synopsis

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 concern graph covers of regular graphs. The first one is called multicovers'': we show that for any regular graph H there exists a graph G that allows many different covering projections onto H. Secondly, we consider partial covers, which require only that G be a subgraph of a cover of H. As an application of our results we show that there are infinitely many rigid regular graphs H for which the H-cover problem deciding if a given graph G covers H is NP-complete. This resolves an open problem related to the characterization of graphs H for which H-COVER is tractable.

1997 Academic Press

1. MOTIVATION AND OVERVIEW

For a fixed graph H, the H-cover problem admits a graph G as input and asks about the existence of a ``local isomorphism'': a labeling of vertices of G by vertices of H so that the label set of the neighborhood of every v # V(G) is equal to the neighborhood (in H ) of the label of v and each article no. TB961743 1 0095-8956Â97 25.00

📜 SIMILAR VOLUMES

Regular factors of regular graphs

✍ B. Bollobás; Akira Saito; N. C. Wormald 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 242 KB

Given r 3 3 and 1 s A s r, we determine all values of k for which every r-regular graph with edge-connectivity A has a k-factor. Some of the earliest results in graph theory are due to Petersen [8] and concern factors in graphs. Among others, Petersen proved that a regular graph of even degree has a

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

Distance-Regular Graphs withbt=1 and Ant

Distance-Regular Graphs withbt=1 and Antipodal Double-Covers

✍ Makoto Araya; Akira Hiraki; Aleksandar Jurišić 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 239 KB

Let 1 be a distance-regular graph of diameter d and valency k>2. If b t =1 and 2t d, then 1 is an antipodal double-cover. Consequently, if f >2 is the multiplicity of an eigenvalue of the adjacency matrix of 1 and if 1 is not an antipodal doublecover then d 2f&3. This result is an improvement of God

From regular boundary graphs to antipoda

From regular boundary graphs to antipodal distance-regular graphs

✍ Fiol, M. A.; Garriga, E.; Yebra, J. L. A. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 383 KB 👁 2 views

Let Γ be a regular graph with n vertices, diameter D, and d + 1 In a previous paper, the authors showed that if P (λ) > n -1, then D ≤ d -1, where P is the polynomial of degree d-1 which takes alternating values ±1 at λ 1 , . . . , λ d . The graphs satisfying P (λ) = n -1, called boundary graphs, h

Regular Graphs, Eigenvalues and Regular

Regular Graphs, Eigenvalues and Regular Factors

✍ Hongliang Lu 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 97 KB

## Abstract In this article, we obtain a sufficient condition for the existence of regular factors in a regular graph in terms of its third largest eigenvalue. We also determine all values of __k__ such that every __r__‐regular graph with the third largest eigenvalue at most has a __k__‐factor.

Distance-regular Graphs with b2=1 and An

Distance-regular Graphs with b2=1 and Antipodal Covers

✍ Makoto Araya; Akira Hiraki; Aleksandar Jurisić 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 234 KB

We show that a distance-regular graph of valency k Ͼ 2 is antipodal , if b 2 ϭ 1 . This answers Problem (i) on p . 182 of Brouwer , Cohen and Neumaier [4] .