Two-fold isomorphisms

Abstract

In this dissertation, we present a natural generalization of the notion of isomorphism of a graph or digraph G, namely two-fold isomorphisms from a graph or digraph G to a graph or digraph H. A mixed graph is a pair G = (V (G),A(G)) where V (G) is a finite set and A(G) is a set of ordered pairs of elements of V (G). The elements of V (G) are called vertices and the elements of A(G) are called arcs. When referring to an arc (u, v), we say that u is adjacent to v and v is adjacent from u. The vertex u is the tail and v is the head of a given arc (u, v). An arc of the form (u, u) is a loop. A mixed graph cannot contain multiple arcs, that is, it cannot contain the arc (u, v) more than once. A set S of arcs is self-paired if, whenever (u, v) 2 S, (v, u) is also in S. If S = {(u, v), then(v, u)}, then we identify S with the unordered pair {u, v}; this unordered pair is called an edge. It will be useful to consider two special cases of mixed graphs. An undirected graph or, in short graph, is a mixed graph without loops whose arc-set is self-paired. The edge set of a graph is denoted by E(G). A digraph is a mixed graph with no loops in which no arc is self-paired. A two-fold isomorphism (TF-isomorphism) is a pair (α, β) of permutations of the vertex set V (G) which acts on ordered pairs of vertices of G in the natural way and such that (u, v) is an arc in G if and only if (α(u), β(v)) is also an arc in H. When α = β the TF-isomorphism is just a usual isomorphism. The following is a brief outline of this dissertation. Chapter 1: In this chapter, we define canonical double covers, incidence double covers and alternating double covers. We also define alternating trails or A-trails. Furthermore, we introduce the notion of stability of graphs. In later chapters, seemingly unrelated concepts and ideas are brought together through the concept of two-fold isomorphism. Chapter 2: As far as we know, TF-isomorphisms of graphs were first introduced by Zelinka [35, 36] who was motivated by the study of isotopy of groupoids, referring to what we call ‘TF-automorphisms’ as ‘autotopies’. Zelinka’s work had been overlooked for decades. Here we review the early work by Zelinka [34, 35, 36, 37, 38], Porcu [26], Pacco and Scapellato [24], and Maruˇsiˇc, Scapellato and Zagaglia-Salvi [21, 22] which, in hindsight, involved TFisomorphisms. Chapter 3: In this chapter we start developing material to tackle our problems. We start by addressing questions concerning invariance under TF-isomorphisms. Then we use alternating double covers of graphs to be able to extend certain results previously known to hold for graphs to mixed graphs. We conclude this chapter by defining an equivalence relation on the arc-set of any mixed graph G and bringing together the concept of A-trails and the construction of graph covers to ultimately explain how TF-isomorphisms arise. Chapter 4: In this chapter, we use and develop new theory with the aim of constructing graphs with specific properties. In particular, we are interested in asymmetric graphs which have a non-trivial TF-automorphism group. We construct a smallest unstable graph using two different constructions, one of which will be generalized in Chapter 5. We also show that a graph and a digraph can be TF-isomorphic. Chapter 5: In this chapter, we show how TF-isomorphisms provide a fresh outlook when considering the concept of unstable graphs. We first show that there is a link between TF-automorphisms and graph stability. We then present simple arguments concerning triangles to ultimately present a method for constructing unstable graphs of arbitrarily large diameter. We also generalize one of the methods used to construct a smallest asymmetric unstable graph and asymmetric unstable graphs of arbitrarily large instability index. Chapter 6: In this chapter, we look at TF-orbitals in some more detail. We define the TF-rank of a group of TF-permutations and look at the situation where the TF-rank equals 1 or 2. We then apply this to unstable rank 3 strongly regular graphs. We consider further properties on a TF-permutation group which force the TF-orbitals to satisfy structure constants similar to those of a coherent configuration. Chapter 7: In the final chapter, we review in a little more detail the connection between TF-isomorphisms and problems such as the Neighbourhood Reconstruction Problem. We also discuss a method suggested by Klin to extend the notion of stability to digraphs and finally we reveal new avenues for research which we plan to explore in the near future. Chapter 1 and Chapter 3 include results found in [16, 17, 18]. Chapter 4 includes constructions found in [16]. Most of the contents of Chapter 5 appear in [18], whereas the contents of Chapter 6 are included in a paper which at the time of writing has been accepted for publication in the Journal of Combinatorial Mathematics and Combinatorial Computing. At the time of writing, a paper which describes the construction of a smallest unstable graph and of a family of graphs with an arbitrarily large index of stability is being prepared. These constructions are found in Chapter 4 and Chapter 5 respectively.