A graph G is a cover of a graph K if there exists a pair of onto mappings
called projections, such that
$\varphi $
maps the edges incident to each vertex v in G bijectively onto the edges incident to
$\pi (v)$
in K. An example of a cover is illustrated in Figure 1. Here, we can define the vertex projection
$\pi $
by labelling every vertex v of G with its image
$\pi (v)$
. We often add a dash or subscript to distinguish between two or more vertices of G projected to the same vertex of K as in Figure 1.
G is a cover of
$K_5$
.
Figure 1 Long description
The diagram consists of two main graph structures connected by a right-pointing arrow.
On the left, graph G is a vertically oriented rectangular structure. It features two central triangular clusters. The top cluster contains vertices a sub 1, b sub 1, and c sub 1. The bottom cluster contains vertices a sub 2, d sub 2, and e sub 2. These are enclosed within a larger outer rectangle with vertices d sub 1 and e sub 1 at the top, and b sub 2 and c sub 2 at the bottom. Vertical lines connect c sub 1 to e sub 2, and b sub 1 to d sub 2.
In the top right, mathematical text defines the mapping. The first line reads pi (a sub 1) equals pi (a sub 2) equals a, followed by an ellipsis. The second line reads phi ((d sub 1, e sub 1)) equals (d, e), followed by an ellipsis.
On the bottom right, the target graph K sub 5 is shown. It is a complete graph with five vertices labeled a, b, c, d, and e. Vertex a is at the center, connected to b, c, d, and e which form a surrounding square. Additional curved edges connect b to d and c to e outside the square perimeter to complete the K sub 5 structure.
If K is connected, then
$|\pi ^{-1}(v)| = n$
is the same for all
$v \in V(K)$
; we speak of an n-fold cover. Note that graph covers have also appeared in the literature as ‘lifts’ of graphs (see [Reference Amit, Linial, Matoušek, Rozenman and Kosaraju1]).
In this thesis, we establish topological and combinatorial relationships between a graph and its covers. The thesis comprises six chapters. All the graphs in this thesis are simple and finite, unless stated otherwise.
Negami [Reference Negami10] famously conjectured that a connected graph is projective planar if and only if it has a finite planar cover. It is known that Negami’s conjecture holds if and only if the graph
$K_{1,2,2,2}$
(the octahedron plus an extra vertex joined to all other vertices) has no finite planar cover [Reference Archdeacon5–Reference Negami9]. In Chapter 2, we study the structure of planar covers of
$K_{1, 2, 2, 2}$
and as an application of our results, we prove the following result.
Theorem 1 [Reference Annor, Nikolayevsky and Payne4]
No n-fold cover of the graph
$K_{1, 2, 2, 2}$
is planar for
$n < 14$
.
This line of research is developed further in Chapter 3, which proves some technical results about the detailed structure of the kinds of covers considered in Chapter 2. These results may be helpful when looking for a counterexample to the conjecture, either by hand or by computer.
Chapter 4 proves several new results that restrict the structure of the kinds of planar covers being considered in the thesis. In particular, we prove the following results.
Theorem 2 [Reference Annor, Nikolayevsky and Payne3]
The graph
$K_{1,2,2,2}$
does not admit a planar cover in which the closed neighbourhood of each vertex covering the degree
$6$
vertex induces the wheel graph
$W_7$
.
Theorem 3 [Reference Annor, Nikolayevsky and Payne3]
If K is a
$4$
-connected graph, then a minimal planar cover of K is
$4$
-connected.
Chapter 5 explores the role of minors in the theory of graph. For a minor-closed class
$\mathcal {M}$
, we define
$\mathcal {F}(\mathcal {M})$
to be the class of graphs that have a cover in
$\mathcal {M}$
. We characterise
$\mathcal {F}(\mathcal {M})$
, where
$\mathcal {M}$
is the class of outerplanar graphs, the class of pseudoforests, the class of cactus graphs or the class of planar graphs with treewidth at most
$3$
. In particular, we prove the following results.
Theorem 4. A graph has a planar cover with treewidth at most
$3$
if and only if it is a planar graph with treewidth at most
$3$
.
Theorem 5. For
$k\leqslant 4$
, if a graph K is k-connected, then any minor-minimal cover of K is k-connected.
Chapter 6 establishes relationships between three domination parameters and graph covers. In particular, we study how the domination number
$\gamma $
, the total domination number
$\gamma _t$
and the connected domination number
$\gamma _c$
behave when passing from a graph to its covers. We prove upper and lower bounds for the domination parameters of the covers. Our main results in this chapter are the following results.
Theorem 6 [Reference Annor2]
Suppose that a graph G is an n-fold cover of a graph K. Then,
${\gamma (G) \geqslant n\gamma (K)/H(\Delta )}$
, where
$H(\Delta ) = 1 +\tfrac 12+\tfrac 13+\cdots +\Delta^{-1}$
and
$\Delta $
is the maximum degree of K.
Theorem 7 [Reference Annor2]
Suppose that a graph G is an n-fold cover of a graph K. Then:
-
(a) $\gamma (G) \geqslant \tfrac 35n\gamma (K)$
if K is a
$3$
-regular graph; -
(b) $\gamma (G) \geqslant \tfrac 12n\gamma (K)$
if K is a
$4$
- or
$5$
-regular graph.
Theorem 8 [Reference Annor2]
Suppose that a graph G is an n-fold cover of a graph K. Then:
-
(a) $\gamma _t(G) \geqslant \tfrac 35n\gamma _t(K)$
if K is a
$3$
-regular graph; -
(b) $\gamma _t(G) \geqslant \tfrac 12n\gamma _t(K)$
if K is a
$4$
- or
$5$
-regular graph.
