ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 8 (2015) 115-131
Unstable graphs: A fresh outlook via TF-automorphisms
Josef Lauri
University of Malta, Department of Mathematics, Malta
Russell Mizzi
University of Malta, Department of Mathematics, Malta
Raffaele Scapellato *
Dipartimento di Matematica, Politecnico di Milano, Italy
Received 4 September 2013, accepted 30 June 2014, published online 21 September 2014
In this paper, we first establish the very close link between stability of graphs, a concept first introduced by Marusic, Scapellato and Zagaglia Salvi and studied most notably by Surowski and Wilson, and two-fold automorphisms. The concept of two-fold isomorphisms, as far as we know, first appeared in Zelinka's work on isotopies of digraphs and later studied formally by the authors with a greater emphasis on undirected graphs. We then turn our attention to the stability of graphs which have every edge on a triangle, but with the fresh outlook provided by TF-automorphisms. Amongst such graphs are strongly regular graphs with certain parameters. The advantages of this fresh outlook are highlighted when we ultimately present a method of constructing and generating unstable graphs with large diameter having every edge lying on a triangle. This was a rather surprising outcome.
Keywords: Graphs, canonical double covers, two-fold isomorphisms. Math. Subj. Class.: 05C25, 05C20, 05C76
* Corresponding author.
E-mail addresses: josef.lauri@um.edu.mt (Josef Lauri), russell.mizzi@um.edu.mt (Russell Mizzi), raffaele.scapellato@polimi.it (Raffaele Scapellato)
Abstract
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
116
Ars Math. Contemp. 8 (2015) 149-162
1 General Introduction and Notation
Let G and H be simple graphs, that is, undirected and without loops or multiple edges. Consider the edge {u, v} to be the set of arcs {(u, v), (v, u)}. A two-fold isomorphism or TF-isomorphism from G to H is apair of bijections a, P: V(G) ^ V(H) such that (u, v) is an arc of G if and only if ((a(u), P(v)) is an arc of H. When such a pair of bijections exist, we say that G and H are TF-isomorphic and the TF-isomorphism is denoted by (a, P). The inverse of (a, P), that is, (a-1, P-1) is a TF-isomorphism from H to G. Furthermore, if (a1, and (a2, P2) are both TF-isomorphisms from G to H then so is (a1a2, When a = P, the TF-isomorphism can be identified with the isomorphism a.
1
1 7 4
H
G
2
6
2
6
7
5
3
3
5
4
Figure 1: G and H are two non-isomorphic TF-isomorphic graphs.
The two graphs G, H in Figure 1, which have the same vertex set V(G) = V(H), are non-isomorphic and yet they are TF-isomorphic. In fact (a, P) where a =(2 5) and P = (1 4)(3 6) is a TF-isomorphism from G to H.
The concept was first studied by Zelinka [15, 16] in the the context of isotopy of digraphs. We shall extend it further to the case of mixed graphs (see next section).
Some graph properties are preserved by a TF-isomorphism. Such is the case with the degree sequence, as illustrated by Figure 1. We also know that two graphs are TF-isomorphic if and only if that they have isomorphic canonical double covers [4]. Alternating paths or A-trails, which we shall define in full below, are invariant under TF-isomorphism. For instance, the alternating path 5 —> 6 <— 1 —> 2 in G is mapped by (a, P) to the similarly alternating path 2 —> 3 <— 1 —> 2 which we shall later be calling "semi-closed".
2 Notation
A mixed graph is a pair G = (V(G), A(G)) where V(G) is a 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. Sometimes we use u —> v to represent an arc (u, v) G
Josef Lauri et al.: Unstable graphs: Afresh outlook via TF-automorphisms
117
V(G). The vertex u is the start-vertex and v is the end-vertex of a given arc (u, v). An arc of the form (u, u) is called a loop. A mixed graph cannot contain multiple arcs, that is, it cannot contain the arc ( u, v) more than once. A mixed graph G is called bipartite if there is a partition of V(G) into two sets X and Y, which we call colour classes, such that for each arc (u, v) of G the set {u, v} intersects both X and Y. A set S of arcs is self-paired if, whenever (u, v) G S, (v, u) is also in S. If S = {(u, v), (v, u)}, then we consider S to be the unordered pair {u, v}; this unordered pair is called an edge.
It is useful to consider two special cases of mixed graphs. A 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 set of arcs is self-paired. The inverse G' of a mixed graph G is obtained from G by reversing all its arcs, that is V(G') =V(G) and (v, u) is an arc of G' if and only if (u, v) is an arc of G. A digraph G may therefore be characterised as a mixed graph for which A(G) and A(G') are disjoint. Given a mixed graph G and a vertex v G V(G), we define the in-neighbourhood Nin(v) by Nin(v) = {x G V(G)|(x,v) G A(G)}. Similarly we define the out-neighbourhood N0„t(v) by N0„t(v) = {x G V(G)|(v, x) G A(G)}. The in-degree Pi„(v) of a vertex v is defined by pin(v) = |Nin(v)| and the out-degree pout(v) of a vertex v is defined by Pout (v) = |Nout(v) |. When G is a graph, these notions reduce to the usual neighbourhood N(v) = Nin(v) = Nout(v) and degree p(v) = pin(v) = Pout(v).
Let G be a graph and let v G V(G). Let N(v) be the neighbourhood of v. We say that
G is vertex-determining if N(x) = N(y) for any two distinct vertices x and y of G [8].
A set P of arcs of G is called a trail of length k if its elements can be ordered in a sequence ai, a2,..., ak such that each ai has a common vertex with ai+i for all i = 1, ..., k — 1. If u is the vertex of a1, that is not in a2 and v is the vertex of ak which is not in ak-1, then we say that P joins u and v; u is called the first vertex of P and v is called the last vertex with respect to the sequence a1, a2, ..., ak. If, whenever ai = (x, y), either ai+1 = (x, z) or ai+1 = (z, y) for some new vertex z, P is called an alternating trail or A-trail.
If the first vertex u and the start-vertex v of an A-trail P are different, then P is said to be open. If they are equal then we have to distinguish between two cases. When the number of arcs is even then P is called closed while when the number of arcs is odd then P is called semi-closed. Note that if P is semi-closed then either (i) a1 = (u, x) for some vertex x and ak = (y, u) for some vertex y or (ii) a1 = (x, u) and ak = (u, y). If P is closed then either a1 = (u, x) and ak = (u, y) or a1 = (x, u) and ak = (y, u). Observe also that the choice of the first (equal to the last) vertex for a closed A-trail is not unique but depends on the ordering of the arcs. However, this choice is unique for semi-closed A-trails as this simple argument shows:
Suppose P is semi-closed and the arcs of P are ordered such that u is the unique (in that ordering) first and last vertex, that is, it is the unique vertex such as the first and the last arcs in the ordering in P do not alternate in direction at the meeting point u. Therefore, it is easy to see that both pin(u) and pout(u) (degrees taken in P as a subgraph induced by its arcs) are odd whereas any other vertex v in the trail has both pin(v) and pout(v) even. This is because, in the given ordering, arcs have to alternate in direction at v and therefore in-arcs
118
Ars Math. Contemp. 8 (2015) 149-162
of the form (x, v) are paired with out-arcs of the form (v, y). Therefore, in no ordering of the arcs of P can u be anything but the only vertex at which the first and last arcs do not alternate. The same argument holds for open A-trails.
Any other graph theoretical terms which we use are standard and can be found in any graph theory textbook such as [1]. For information on automorphism groups, the reader is referred to [7].
Let G and H be two mixed graphs and suppose that a, p are bijections from V(G) to V(H). The concept of TF-isomorphisms may be extended from graphs to mixed graphs. In fact, we can say that the pair (a, p) is a two-fold isomorphism (or TF-isomorphism) from G to H if the following holds: (u, v) is an arc of G if and only if (a(u), p(v)) is an arc of H. We then say that G and H are TF-isomorphic and write G =TF H. Note that when a = p the pair (a, p) is a TF-isomorphism if and only if a itself is an isomorphism. If a = p, then the given TF-isomorphism (a, p) is essentially different from a usual isomorphism and hence we call (a, p) a non-trivial TF-isomorphism. If (a, p) is a non-trivial TF-isomorphism from a mixed graph G to a mixed graph H, the bijections a and p need not necessarily be isomorphisms from G to H. This is illustrated by the graphs in Figure 1, examples found in [5], and also others presented below.
When G = H, (a, p) is said to be a TF-automorphism and it is again called nontrivial if a = p. The set of all TF-automorphisms of G with multiplication defined by (a,p)(Y, J) = (aY,pj) is a subgroup of SV(G) x SV(G) and it is called the two-fold automorphism group of G and is denoted by AutTF(G). Note that if we identify an automorphism a with the TF-automorphism (a, a), then Aut(G) C AutTF(G). When a graph has no non-trivial TF-automorphisms, Aut(G) =AutTF(G). It is possible for an asymmetric graph G, that is a graph with |Aut(G)| = 1, to have non-trivial TF-automorphisms. This was one of our main results in [5].
The main theme of this paper is stability of graphs, an idea introduced by Marusic et al. [8] and studied extensively by others, most notably by Wilson [14] andSurowski [12], [13]. Let G be a graph and let CDC(G) be its canonical double cover or duplex. This means that V(CDC(G)) = V(G) x Z2 and {(u, 0), (v, 1)} and {(u, 1), (v, 0)} are edges of CDC(G) if and only if {u, v} is an edge of G. One may think of the second entry in the notation used for vertices of CDC(G), that is 0 or 1 as colours. For the reader familiar with products of graphs we wish to add that CDC(G) is the direct product G x K2 of G by K2. Recall that the graph CDC(G) is bipartite and we may denote its colour classes by V0 = V x {0} and V1 = V x {1} containing vertices of the type (u, 0) and (u, 1) respectively. A graph is said to be unstable if Aut(G) x Z2 is aproper subgroup of the set Aut(CDC(G)). The elements of Aut(CDC(G)) \ Aut(G) x Z2 will be called unexpected automorphisms of CDC(G). In other words, a graph G is unstable if at least one element of Aut(CDC(G)) is not a lifting of some element of Aut(G). In this paper, we shall investigate the relationship between the stability of the graph G and its two-fold automorphism group AutTF(G).
Josef Lauri et al.: Unstable graphs: Afresh outlook via TF-automorphisms
119
3 Unstable Graphs and TF-automorphisms
Consider Aut(CDC(G)). Now, let E be the set-wise stabiliser of Vo in Aut(CDC(G)), which of course coincides with the set-wise stabiliser of V. Note that every a G E also fixes Vi set-wise. We will show that it is the structure of E which essentially determines whether CDC(G) has unexpected automorphisms which cannot be lifted from automorphisms of G. The following result, which is based on [9], Lemma 2.1, implies that these unexpected automorphisms of CDC(G) arise if the action of a on V0 is not mirrored by its action of Vi.
Lemma 3.1. Let f : E ^ Sym(V) x Sym(V) be defined by f : a ^ (a, ft) where (a(v), 0) = a(v, 0) and (ft(v), 1) = a(v, 1), that is a, ft extract from a its action on V0 and V respectively. Then:
1.	f is a group homomorphism;
2.	f is injective and therefore f : E ^ f (E) is a group automorphism;
3.	f (E) = {(a, ft) G Sym(V) x Sym(V) : x is adjacent to y in G if and only if a(x) is adjacent to ft (y) in G} that is, f (E) = AutTF(G) that is, (a, ft) (the ordered pair of separate actions of a on the two classes) is a TF-automorphism of G.
Proof. The fact that f is a group homomorphism, that is, that f is a structure preserving map from E to Sym(V) x Sym(V) follows immediately from the definition since for any a1, a2 G E where f (ai) = (ai, fti) and f (a2) = (a2, ft2), f (ai)f (a2) = (aifti)(a2ft2) = (a1a2, ft1ft2) = f (a1a2). This map is clearly injective and therefore f : E ^ f (E) is a group automorphism.
Consider an arc ((u, 0), (v, 1)). Since a G E C Aut(CDC(G)), (a(u), 0), (a(v), 1)) is also an arc of CDC(G). By definition, this arc may be denoted by ((a(u), 0), (ft(v), 1)) and, following the definition of CDC(G), it exists if and only if (a(u), ft(v)) is an arc of G. Hence f maps elements of E to ( a, ft) which clearly take arcs of G to arcs of G. This implies that (a, ft) is a TF-automorphism of G and hence f (E) CAutTF(G).
Conversely, let (a, ft) G AutTF(G). Define a by a(v, 0) = (a(v), 0) and a(v, 1) =
(ft(v), 1)), then f (a) = (a, ft). Hence, AutTF(G) C f (E). Therefore f(E)= AutTF(g). □
Theorem 3.2. Let G be a graph. Then
Aut(CDC(G)) = AutTF(G) x Z2. Furthermore, G is unstable if and only if it has a non-trivial TF-automorphism.
Proof. From Lemma 3.1, f (E) = AutTF(G) which must have index 2 in Aut (CDC(G)). The permutation S(v, e) ^ (v,e + 1) is an automorphism of CDC(G) and S ^ f (E). Then Aut(CDC(G)) is generated by f (E) and S. Furthermore, f (E) n (S) = id and f (E) < Aut (CDC(G)) being of index 2.
120
Ars Math. Contemp. 8 (2015) 215-223
Since Aut(CDC(G)) = AutTF(G) x Z2, G is stable if and only if AutTF(G) = Aut(G). □
As shown in [5], Proposition 3.1, if (a, ¡) G AutTF(G) then (7,7-1) G AutTF(G) (where 7 = a.3-1). This means that for any edge {x, y} of G, {y(x), Y-1(y)} is also an edge. A permutation 7 of V(G) with this property is called an anti-automorphism. Such maps possess intriguing applications to the study of cancellation of graphs in direct products with arbitrary bipartite graphs, that is, the characterisation of those graphs G for which G x C ~ H x C implies G ~ H, whenever C is a bipartite graph (see [2], Chapter 9). The second part of Theorem 3.2 could be rephrased as follows: "G is unstable if and only if it has an anti-automorphism of order different from 2". Note that the existence of an anti-automorphisms of order 2 does not imply instability since such a map corresponds to a trivial TF-automorphisms.
Notice that AutTF(G) is the edge set of the graph factorial G! introduced in [2] in the wake of investigations of anti-automorphisms. G! shares many properties with factorials of natural numbers and is interesting per se. As CDC(G) = G x K2 one could thus rephrase Theorem 3.2 in the language of [2] as Aut(G x K2) = E(G!) x Z2.
Figure 2: A stable and unstable graph which are TF-isomorphic.
It is natural to ask whether it can happen that a stable graph is TF-isomorphic to an unstable one. The answer is yes and an example is shown in Figure 2 with the Petersen graph being stable and the other graph which is TF-isomorphic to it being unstable. Both graphs have the same bipartite canonical double cover since they are TF-isomorphic. If loops are allowed, then the smallest pair of TF-isomorphic graphs, only one of which is stable is given by G = K3 and H the path of three vertices with a loop at each of the end-vertices.
2
1
3
4
5
Porcu, motivated by the quest of finding pairs of co-spectral graphs, was the first to study non-isomorphic graphs having the same canonical double cover [11], but his work was overlooked by several mathematicians interested in these questions. Porcu was the first author to study the example given in Figure 1. The same example was re-discovered much later in [3]. Pacco and Scapellato [10], answering a question raised by Porcu, proved a result giving the number of graphs having a given bipartite graph B as canonical double
Josef Lauri et al.: Unstable graphs: Afresh outlook via TF-automorphisms
121
covering terms of involutions in Aut(B). A later extension of their result appeared in [2], Theorem 9.15.
We should point out here (as noted by Surowski in [12]) that if a graph G is stable, that is, Aut(CDC(G)) = Aut(G) x Z2, then the semi-direct product must be a direct product because Aut(G) is normal in Aut(CDC(G)) since it has index 2 and also Z2 is normal since its generator commutes with every element of Aut(CDC(G)), by stability. In fact, as Surowski comments, the stability of G is equivalent to the centrality of Z2 in Aut(CDC(G)), which is the lift of the identity in Aut(G).
(b,0))< \(b,1)
(c,0)) ^(c,1) (d,0) / \(d,1) (e,0))
CDC(G)
Figure 3: An example used to show how a TF-automorphism (a, P) of G can be obtained from an automorphism a of CDC(G).
It is worth noting that the ideas explored in the proof of Lemma 3.1 may be used to extract TF-automorphisms of a graph G from automorphisms of CDC(G) which fix the colour classes. In fact, let a be such an automorphism. Define the permutations a and P of V(G) as follows: a(x) = y if and only if a(x, 0) = (y, 0) and P(x) = y if and only if a(x, 1) = (y, 1). Then (a, P) is a TF-automorphism of G. We remark that a and P are not necessarily automorphisms of G as we shall show in the example shown in Figure 3. The automorphism a is chosen so that it fixes one component of CDC(G) whilst being an automorphism of the other component. In order to have a more concise representation, we denote vertices of CDC(G) of the form (u, 0), that is, elements of the colour class V0 by u0 and similarly denote vertices of the form (u, 1) in Vi by ui. Using this notation, a = (a0)(b1)(c0)(d1)(e)(a1 e1)(b0 d0)(c1). The permutations a and P of G are extracted from a as described in the proof of Lemma 3.1. For instance, to obtain a, we restrict the action of a to the elements of V0, that is, those vertices of the form (v, 0) or v0 when using the new notation and then drop the subscript. Similarly, the permutation P is obtained from the action of a restricted to V1. Therefore, a = (a)(c)(e)(b d) and P = (b)(d)(a e)(c). Note that neither a nor P is an automorphism of G, but (a, P) is a TF-automorphism of G which in turn can be lifted to the unexpected automorphism a of CDC(G). This example illustrates Lemma 3.1 since the graph G is unstable and has a non-trivial TF-automorphism.
122
Ars Math. Contemp. 8 (2015) 215-223
The result of Lemma 3.1 and the subsequent example lead us to other questions regarding the nature of the permutations a and P which, as discussed in the preceding example given in Figure 3, may not be automorphisms of G.
If (a, id) is a non-trivial TF-automorphism of a graph G, then G is not vertex-determining. In fact, since a = id then a(u) = v for some u = v and the TF-automorphism (a, id) fixes the neighbours of u and takes u to v. Hence u and v must have the same neighbourhood set, which implies that G is not vertex-determining.
We shall use this idea to prove some results below. An alternative way of looking at this is to consider Lemma 3.1 and to note that a graph G is stable if and only if given a(v,0) = (a(v),0), there exists no P = a such that (P(v), 1)) = a(v,0). Hence, as implied by Theorem 3.2 a graph G is stable if and only if f (£) C AV where AV is the diagonal group of (a, P), a, P automorphisms of G, with a = P.
Proposition 3.3. If (a, P) is a non-trivial TF-automorphism of a graph G but a and P are automorphisms of G, then G is not vertex-determining.
Proof. Since a is an automorphism of G and (a, P) is a TF-automorphism, the group AutTF(G) must also contain (a, P)(a-1, a-1) = (id, Pa-1). Since aP-1 = id, let u be a vertex such that v = aP-1(u) is different from u. Then for each neighbour w of u the arc (w, u) is taken to the arc (w, v), so that N(u) is contained in N(v) and vice versa. Therefore u and v have the same neighbourhood, so G is not vertex-determining. □
Proposition 3.4. If (a, P) is a non-trivial TF-automorphism of a graph G and a, P have a different order, then G is not vertex-determining.
Proof. Let (a, P) be an element of AutTF(G) with the orders of a and P being p and q respectively and assume without loss of generality that p < q. Since AutTF(G) is a group, (a, P)p = (ap, Pp) = (id, Pp) must also be in AutTF(G). The same argument used in the proof of Proposition 3.3 holds since Pp = id. Hence G is not vertex-determining. □
Proposition 3.3 and Proposition 3.4 are equivalent to their counterparts in [8] in which they are stated in terms of adjacency matrices. In [8], it is shown that if a graph G is unstable but vertex-determining and (a, P) is a non-trivial TF-automorphism of G, then a and P must not be automorphisms of G and must have the same order. This then gives us information about automorphisms a of CDC(G) which are liftings of TF-automorphisms of G.
4 Triangles
In this section we shall study the behaviour of a non-trivial TF-automorphism of a graph G acting on a subgraph of G isomorphic to K3 with the intent of obtaining information regarding the stability of graphs which have triangles as a basic characteristic of their structure. Strongly regular graphs in which every pair of adjacent vertices has a common neighbour are an example. The stability of such graphs has been studied by Surowski [12]. We believe that this section is interesting because it is a source of simple examples of unstable graphs
Josef Lauri et al.: Unstable graphs: Afresh outlook via TF-automorphisms
123
and also because a detailed analysis of what happens to triangles can throw more light on TF-automorphisms of graphs.
Proposition 4.1. Let (a, P) be a TF-isomorphism from a graph G to a graph G. The action of (a, P) on some subgraph H = K3 yields either (a) a closed A-trail of length 6 with no repeated vertices, (b) a pair of oriented A-connected triangles with exactly one common vertex, (c) a pair of oriented triangles with exactly two common vertices or (d) an undirected triangle as illustrated in Figure 4(a),(b),(c) and (d) respectively.
Proof. Let V(H) = {1, 2, 3}. The semi-closed A-trials 1 —> 2 <— 3 —> 1 and 1 <— 2 —> 3 <— 1 of H are taken by (a, P) to a(1) —> £(2) <— a(3) —> P(1) and P(1) <— a(2) —> P(3) <— a(1), respectively; together, these two A-trails form a closed A-trail consisting of six arcs.
Consider the possible equalities a(v) = P(v) for v e V(H). Up to a reordering of the vertices, we have the following four cases, corresponding to the four cases stated above:
(a)	a(v) = P(v) for all v.
(b)	a(v) = P(v) for v = 1, 3 but a(2) = P(2).
(c)	a(v) = P(v) for v = 1 but a(v) = P(v) for v = 2, 3.
(d)	a(v) = P(v) for all v.
For each case, the corresponding graph is shown in Figure 4.	□
In general, when a TF-automorphism (a, P) acts on the arcs of G it maps any triangle H into another triangle if a(x) = P(x) for every vertex x of the triangle or it fits one of the other configurations described by Proposition 4.1. If a graph G in which every edge lies in a triangle is unstable, then it must have a non-trivial TF-automorphism which follows one of the configurations illustrated in Figure 4(a), (b) and (c).
Proposition 4.2. Let (a, P) be a TF-isomorphism from G to G'. When the TF-isomorphism acting on K3, a subgraph of G, yields a closed A-trail of length 6 with no repeated vertices as shown in Figure 4(a), either two triangles with no common vertex or a triangle and a closed A-trail with 6 arcs are mapped to a subgraph isomorphic to C6. In the cases when the TF-isomorphism acting on a K3 yields the images illustrated in Figure 4 (b), (c), the pair oftriangles which are either mapped to two triangles with exactly one common vertex or to two triangles with exactly one common edge must have a common vertex.
Proof. Refer to Figure 4. In the case illustrated in Figure 4(a) the arcs of one closed A-trail P of length 6 can be the co-domain the arcs of a triangle H. The A-trail P' obtained by reversing the arcs of P can be the co-domain of another triangle K. We claim that H and K are vertex disjoint. In fact, suppose not and assume that the two triangles have a common vertex u. The pair of vertices a(u) and P(u) where a(u) = P(u) are in both P and P' and this is contradiction as the in-degree of a(u) and similarly the out-degree of P(u) must be zero and this makes it impossible to identify arcs of P with arcs of P' to form the edges of a C6. Figure 5 shows an example where setting a(3) = P(5), P(2) = a(6), a(1) = P(4), P(3) = a(5), a(2) = P(6), P(1) = a(4) would be one way of associating one directed
124
Ars Math. Contemp. 8 (2015) 215-223
C6 with the other so that the alternating connected circuits form an undirected C6. The other possibility is illustrated in Figure 6. In this example ,0(1) = a(4), a(2) = 0(5), 0(3) = a(6), a(1) = 0(7), 0(2) = a(8) and a(3) = 0(9) so that a closed A-trail of length 6 covering a K3 is mapped to a closed A-trail of length 6 covering half of the arcs of an undirected C6 whilst the rest of the arcs come from an A-trail of length 6 covering half of the arcs of another subgraph isomorphic to C6. The K3 and the C6 in the domain of the TF-isomorphism cannot have a common vertex and the proof is analogous to the one concerning the former case.
The proof for the remaining cases may be carried over along the same lines as the above. Refer to Figure 7. We observe that the A-trail P1 described by 0(3) <— a(2) —> 0(1), the A-trail P2 described by a(1) —> 0(2) <— a(3) and the A-trails Pi and P2' obtained by reversing the arcs of P1 and P2 respectively would imply by the preservation of A-trails, that in the pre-image of the subgraph, there are four A-trails passing through the vertex 2. This is only possible if the triangles in the pre-image have a common vertex.	□
Figure 8 shows an example to illustrate the result of Proposition 4.2 where a(1) = 0 (4), 0(3) = a(5), a(3) = 0(5) and 0(1) = a(4). Figure 8 shows the smallest unstable graphs which have a TF-automorphism which takes a triangle to a pair of directed triangles with a common vertex as illustrated in Figure 4(b). Figure 9 shows the smallest graph which has a nontrivial TF-automorphism which maps a triangle to the mixed graph illustrated in Figure 4(c).
5 Unstable graphs of arbitrarily large diameter
In this section, we present a method of constructing unstable graphs of an arbitrarily high diameter.
If H, K are graphs, let [H, K] be the graph whose vertex set is the union V(H)U V(K) and whose edge set is the union of E(H), E(K) plus the edges of the complete bipartite graph with classes V(H) and V(K). More generally, if H are graphs, where i G Zm, let G = [Ho, H1, ..., Hm-1] be the graph whose vertex set is the union of all V(H) and whose edge set is the union of all E([Hj, H(i+1)]). In other words, G contains all vertices and edges of the graphs H, plus all edges of the complete bipartite graph connecting two consecutive Hj's.
Now, assume that none of the H has isolated vertices. Let (a, 0j) : H ^ Hi+1 be TF-isomorphisms as i runs over Zm. Assume that the product
(ao,0o)(a1,01)...(am_1,0m_1) = (id, id).
Note that the latter assumption is not a restriction, because one can always take (a0,0o) as the inverse of the product of the remaining TF-isomorphisms.
Josef Lauri et al.: Unstable graphs: Afresh outlook via TF-automorphisms
125
Theorem 5.1. With the above assumptions, let G = [H0, H1, ..., Hm-1]. Define two permutations a, ft of V (G) as follows. For v e V (G), let i be such that v e V (Hi); then set a(v) = ai(v) and ft(v) = fti(v).
Then the following hold:
1.	(a, ft) is a TF-automorphism of G;
2.	if m > 4, diam G = (m — e)/2, where e = 0 if m is even and e = 1 if m is odd;
3.	each edge of G belongs to a triangle.
Proof. First note that if (u, v) is an arc of G and both u, v belong to the same Hi, then the image of (u, v) is an arc of Hi+1, hence of G, because (a, ft) acts like (a^ fti) in Hi. If u, v do not belong to the same Hi, then they belong to consecutive graphs, say Hi, Hi+1, so a(u) and ft(u) belong to the consecutive graphs Hi+1, Hi+2, and are adjacent because all the arcs between these two graphs belong to G. This proves (1).
Concerning distance, a path from u in H0 to v in Hs, where s < (m — e)/2, must pass through all graphs H1, H2, ..., Hs-1 or else Hm-1, Hm-2, ..., Hs+1. Since such a path can be found, d(u, v) = s. For two vertices in, say, Hi and Hj with i = j, the same argument shows that d(u, v) cannot exceed (m — e)/2. Finally, if u, v lie in the same Hi, they have a common neighbour in Hi+1, then d(u, v) is less or equal than 2 (regardless to their distance within Hi). This proves (2).
What about triangles? If {u, v} is an edge of some Hi then letting w e Hi+1 the vertex w is adjacent to both u and v, hence {u, v, w} is a triangle. If {u, v} is an edge of some [Hi, Hi+1], say with u e Hi and v e Hi+1, take any neighbour w of u in Hi (recall the assumption about no isolated vertices) and get the triangle {u, v, w}. This proves (3). □
Until now, we did not mention that the concerned TF-isomorphisms are non-trivial, so all the above would work fine for the case of isomorphisms too. But adding the hypothesis that at least one of them is non-trivial, the obtained graph G has a non-trivial TF-isomorphism, namely (a, ft) as described above. Theorem 5.1 shows that there are unstable graphs of arbitrarily high diameter, where each edge belongs to a triangle.
Surowski [12, 13] proved various results concerning graph stability. In [12], Proposition 2.1, he claims that if G is a connected graph of diameter d > 4 in which every edge lies in a triangle, then G is stable. However, by taking m > 7 in Theorem 5.1 we get infinitely many counterexamples to this claim by taking all the Hi isomorphic to the same vertex-determining bipartite graph, because such a vertex-transitive graph is unstable, therefore one can find a non-trivial TF-isomorphism from Hi to Hi+1, and since these Hi are isomorphic, the resulting graph G is vertex-determining, has diameter k > 4, and is unstable. One of these counterexamples is illustrated in Figure 10.
We detected one possible flaw in Surowski's proof. It is claimed in [12] that whenever an automorphism of CDC(G) fixes (v, 1) it also fixes (v, —1). We have not seen a
126
Ars Math. Contemp. 8 (2015) 215-223
proof of this result. Besides, in our last example, G has a non-trivial fixed-point-free TF-automorphism, which implies that CDC(G) has a fixed-point-free automorphism that fixes the colour classes. This claim is also used in [12] Proposition 2.2 which states that if G is a strongly regular graph with k > p = A > 1, then G is stable. Hence, we believe that at this point, the stability of strongly regular graphs with these parameters requires further investigation.
6 Concluding Remarks
The use of TF-isomorphisms in the study of stability of graphs provides a fresh outlook which allows us to view facts within a more concrete framework and also provides tools to obtain new results. For instance, we can investigate the structure of the given graph without actually requiring to lift the graph to its canonical double cover, but only having to reason within the original graph. Furthermore, the insights that we already have about TF-isomorphisms of graphs may be considered to be new tools added to a limited toolkit. In particular, let us mention the idea of graph invariants under the action of TF-isomorphisms, such as A-trails, a topic which we have started to study in [6]. To be able to find out how the subgraphs of a graph are related to other subgraphs within the graph itself in the case of unstable graphs fills a gap in our understanding of graph stability and using TF-isomorphisms appears to be a promising approach in this sense. We believe that this paper substantiates these claims. Furthermore, it motivates us to carry out further investigations. Some pending questions such as those concerning the stability of certain strongly regular graphs have already been indicated. The study of how TF-isomorphisms act on common subgraphs such as triangles is another useful lead. Nevertheless, the more ambitious aim would be the classification of unstable graphs in terms of the types of TF-automorphisms which they admit.
Acknowledgement
The authors would like to thank two anonymous referees for their careful reading of the submitted paper and their detailed comments which enabled us to improve significantly the final version of the paper.
Josef Lauri et al.: Unstable graphs: Afresh outlook via TF-automorphisms
127
Figure 4: The configurations of possible images of a triangle under the action of a TF-automorphism as described in Proposition 4.1.
12S
Ars Math. Contemp. S(2G15) 115-131
Josef Lauri et al.: Unstable graphs: Afresh outlook via TF-automorphisms
129
/ \
Figure 7: An example to illustrate the result of Proposition 4.2.
a(3) = P(5)
a(4) = P(1) a(3) = fi(5)
a(4) = P(1)
Figure 8: The smallest unstable graphs where a triangle is taken to a two directed triangles sharing a vertex.
1	a(4) = P(1)
3 a(2) = /3(2)
a(3) = /(3)
a(1) = /(4)
3
1
5
4
2
Figure 9: The smallest unstable graph which has a TF-automorphism taking a triangle to the mixed graph as illustrated in Figure 4(c).
130
Ars Math. Contemp. 8 (2015) 215-223
Figure 10: A graph constructed using Theorem 5.1.
Josef Lauri et al.: Unstable graphs: Afresh outlook via TF-automorphisms
131
References
[1]	A. Bondy and U. Murty, Graph Theory (Graduate Texts in Mathematics), Springer, 2008.
[2]	R. Hammack, W. Imrich and S. Klavzar, Handbook of Product Graphs, Second Edition, Discrete Mathematics and Its Applications, Taylor & Francis, 2011.
[3]	W. Imrich and T. Pisanski, Multiple Kronecker covering graphs, Eur. J. Comb. 29 (2008), 1116— 1122, doi:10.1016/j.ejc.2007.07.001.
[4]	J. Lauri, R. Mizzi and R. Scapellato, Two-fold orbital digraphs and other constructions., International J. of Pure and Applied Math. 1 (2004), 63-93.
[5]	J. Lauri, R. Mizzi and R. Scapellato, Two-fold automorphisms of graphs., Australasian J. Combinatorics. 49 (2011), 165-176.
[6]	J. Lauri, R. Mizzi and R. Scapellato, A generalisation of isomorphisms with applications., Preprint (2014).
[7]	J. Lauri and R. Scapellato, Topics in Graph Automorphisms and Reconstruction, Cambridge University Press, 2003.
[8]	D. Marusic, R. Scapellato and N. Zagaglia Salvi, A characterization of particular symmetric (0,1)-matrices, Linear Algebra Appl. 119 (1989), 153-162, doi:10.1016/0024-3795(89) 90075-X.
[9]	D. Marusic, R. Scapellato and N. Zagaglia Salvi, Generalized Cayley graphs, Discrete Mathematics 102 (1992), 279 - 285, doi:http://dx.doi.org/10.1016/0012-365X(92)90121-U.
[10]	W. Pacco and R. Scapellato, Digraphs having the same canonical double covering, Discrete Math. (1997), 291-296.
[11]	L. Porcu, Sul raddoppio di un grafo, Att. Ist. Lombardo (Rend. Sci.) A (1976), 353-360.
[12]	D. B. Surowski, Stability of arc-transitive graphs, J. Graph Theory 38 (2001), 95-110, doi: 10.1002/jgt.1026.
[13]	D. B. Surowski, Automorphism groups of certain unstable graphs, Math. Slovaca 53 (2003), 215-232.
[14]	S. Wilson, Unexpected symmetries in unstable graphs, J. Combin. Theory Ser. B 98 (2008), 359-383, doi:10.1016/j.jctb.2007.08.001.
[15]	B. Zelinka, The group of autotopies of a digraph, Czechoslovak Mathematical Journal 21 (1971), 619-624.
[16]	B. Zelinka, Isotopy of digraphs, Czechoslovak Mathematical Journal 22 (1972), 353-360.