Unstable graphs : a fresh outlook via TF-automorphisms

Abstract

In this paper, we first establish the very close link between stability of graphs, a concept first introduced in [7] and studied most notably by Surowski [10], [11] and Wilson [12] and two-fold automorphisms. The concept of two-fold isomorphisms, as far as we know, first appeared in literature in the form of isotopies of digraphs [13], [14], [15], [16] and later studied formally in [3], [4] 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.