A graph \(G\) is asymmetric if its automorphism group is trivial. Asymmetric graphs were introduced by Erdős and Rényi [1]. They suggested the problem of starting with an asymmetric graph and removing some number, \(r\), of edges and/or adding some number, \(s\), of edges so that the resulting graph is non-asymmetric. Erdős and Rényi defined the degree of asymmetry of a graph to be the minimum value of \(r+s\). In this paper, we consider another property that measures how close a given non-asymmetric graph is to being asymmetric. Brewer et al defined the asymmetric index of a graph \(G\), denoted \(ai(G)\) is the minimum of \(r+s\) so that the resulting graph \(G\) is asymmetric [2]. It is noted that \(ai(G)\) is only defined for graphs with at least six vertices. We investigate the asymmetric index of both connected and disconnected graphs including paths, cycles, and grids, with the addition of up to two isolated vertices. Furthermore for a graph in these families \(G\) we determine the number of labelled asymmetric graphs that can be obtained by adding or removing \(ai(G)\) edges. This leads to the related question: Given a graph \(G\) where \(ai(G)=1\), what is the probability that for a randomly chosen edge \(e\), that \(G-e\) will be asymmetric? A graph is called minimally non-asymmetric if this probability is \(1\). We give a construction of infinite families of minimally non-asymmetric graphs.
For a graph \(G\) we will use \(V(G)\) to denote the set of vertices, and \(E(G)\) to denote the set of edges. The edge between vertices \(u\) and \(v\) will be denoted \(\{u,v\}\). Two graphs \(G\) and \(H\) are isomorphic if there is a bijection \(f:G\rightarrow H\) where \(\{u,v\}\in E(G)\Leftrightarrow \{f(u),f(v)\}\in E(H)\). Such a function is an automorphism if it is an isomorphism from a graph to itself, and the set of all automorphisms of a graph forms a group under function composition. We will use \(\text{Aut}{G}\) to denote the automorphism group of a graph \(G\). For more information on graph automorphisms, see the text by Godsil and Royle [3].
Here we start with a non-asymmetric graph and remove some number, \(r\), of edges and/or add some number, \(s\), of edges so that the resulting graph is asymmetric. The asymmetric index of a graph \(G\), denoted \(ai(G)\), is the minimum \(r+s\) so that the resulting graph \(G\) is asymmetric. This parameter was introduced by Brewer et al. [2].
Many graphs with asymmetric index of \(1\) have been identified [2,4]. In this paper we focus on enumerating the edges that “realize” the asymmetric index of \(G\). Alternatively we consider the question: Given a graph \(G\) where \(ai(G)=1\), what is the probability that for a randomly chosen edge \(e\), \(G-e\) will be asymmetric? For some graphs the asymmetric index is realized by adding an edge, as opposed to deleting an edge, and in these cases we will consider the probability of adding a randomly selected edge to make the resulting graph \(G\) asymmetric.
Before considering specific families of graphs, we note in the next theorem that no graph has a single edge whose removal gives an asymmetric graph.
Theorem 1. There is no non-asymmetric graph \(G\) with a unique edge \(e\) such that \(G-e\) is asymmetric.
Proof. An orbital is an orbit of \(Aut(G)\) acting on the ordered pairs \(V(G)\times V(G)\). Note that the orbitals partition the arcs of \(G\). Suppose that \(G\) is non-asymmetric, and \(G-\{u,v\}\) is asymmetric, for some \(\{u,v\}\in E(G)\). Since \(G-\{u,v\}\) is asymmetric, there is no non-identity automorphism \(\phi\) of \(G\) so that \(\phi(\{u,v\})=\{u,v\}\).
Consider the orbital \(O\) containing \((u,v)\). If \((x,y)\in O\), then \(G-\{x,y\}\) is asymmetric, as there is an automorphism of \(G\) that maps the edge \(\{u,v\}\) to the edge \(\{x,y\}\). Thus if \(\{u,v\}\) is the unique edge for which \(G-\{u,v\}\) is asymmetric, then either \(O=\{(u,v)\}\), or \(O=\{(u,v),(v,u)\}\).
In the first case, every automorphism of \(G\) fixes both \(u\) and \(v\) pointwise. In the second case, every automorphism of \(G\) either fixes \(u\) and \(v\) pointwise, or maps \(u\mapsto v\) and \(v\mapsto u\). In both cases we see that every automorphism of \(G\) fixes \(\{u,v\}\) setwise. Since \(G\) contains a non-trivial automorphism, this contradicts our assumption that \(G-\{u,v\}\) is asymmetric. Therefore there is some edge \(\{x,y\}\neq \{u,v\}\) so that \(G-\{x,y\}\) is asymmetric. ◻
In Sections 2, 3, and 4 we investigate paths, cycles, and grid graphs. We determine the number of labelled asymmetric graphs that can be obtained by adding or removing \(ai(G)\) edges for each of these graphs \(G\). Extending these results, we also consider the graphs \(G\cup 2K_1\) for each \(G\) in these classes.
A graph is called minimally non-asymmetric if the deletion of any edge results in an asymmetric graph. In Section 5, we give a construction of infinite families of minimally non-asymmetric graphs. Let \(\operatorname{Pr}_e(G)\) denote the probability that \(G-e\) is asymmetric for a randomly selected edge \(e\) of \(G\). Then a graph is minimally non-asymmetric if \(\operatorname{Pr}_e(G)=1\). For the complete graphs, the deletion of any edge from \(K_n\) does not result in an asymmetric graph, so \(\operatorname{Pr}_e(K_n)=0\). In Section 6, we show that if \(0\leq\alpha\leq 1\) is rational, then there is a graph \(G\) for which \(\operatorname{Pr}_e(G)=\alpha\).
Throughout, \(P_n\) denotes the path with \(n\) vertices. In this section we consider \(G\) to be a path and up to two isolated vertices where \(ai(G) = 1\). We ask what is the probability that for a randomly chosen edge, what is the probability that \(G-e\) will be asymmetric? We establish that \(ai\left( P_{n}\cup tK_{1}\right) =1\) if and only if \(t\leq 2\). We begin with the following result from Brewer et al. [2].
Theorem 2. When \(n\geq 6\), the number of non-isomorphic asymmetric graphs obtained by adding an edge to a path \(P_{n}\) is \(\left\lfloor \frac{\left( n-4\right) ^{2}}{4}\right\rfloor\).
It was shown that \(ai\left( P_{n}\right) =1\) for all \(n\geq 6\) [2]. Next we count the number of asymmetric labelled graphs that can be obtained by adding an edge to \(P_n\). As an easy consequence of Theorem 2 we have the following.
Lemma 1. When \(n\geq 6\), the number of labelled asymmetric graphs obtained by adding an edge to a path \(P_{n}\) is \(2\left\lfloor \frac{\left( n-4\right) ^{2}}{4}\right\rfloor\). ◻
Theorem 3. Let \(n\geq6\) and \(t\in\{1,2\}\). The number of labelled asymmetric graphs obtained by adding an edge between a path \(P_{n}\) and \(tK_1\) is \(t(n-4)\) if \(n\) is even and \(t(n-5)\) if \(n\) is odd.
Proof. Let the vertices of \(P_{n}\) \(v_{0},v_{1},…,v_{n-1}\) and let the two isolated vertices be \(u\) and \(w\). We first note to obtain an asymmetric graph an added edge must be incident to either \(u\) or \(w\). Without loss of generality we will consider adding an edge that is incident to \(u\). We first note that adding an edge from \(u\) to either \(v_{0}\) or \(v_{n-1}\) will result in a path that is not asymmetric with one isolated vertex. Also, adding an edge between \(u\) and \(v_1\) or \(v_{n-2}\) would result in a non-asymmetrical subdivided star with an isolated vertex. Additionally, if \(n\) is odd then adding an edge between \(u\) and the middle vertex of the path will result in a graph that is not asymmetric. Adding an edge incident to an isolated vertex and any vertex that is not \(v_1\), \(v_2\), \(v_{n-1}\), or \(v_{n-2}\) will result in a subdivided star where the pendant paths all have different lengths, which is asymmetric. ◻
When \(t=2\), Theorem 3 gives the number of ways the asymmetric index can be realized by adding one edge. However, in the case of \(t=1\) the added edge can either connect two vertices of the path, or connect the isolated vertex to a vertex on a path. Hence Lemma 1 and Theorem 3 can be combined to give the following result.
Theorem 4. Let \(n\geq6\). The number of labelled asymmetric graphs obtained by adding an edge to \(P_{n}\cup K_1\) is \[A_P(n,1)=\begin{cases} (n-4) + 2\left\lfloor \frac{\left( n-4\right) ^{2}}{4}\right\rfloor & \text{if $n$ is even,}\\ \\ (n-5) + 2\left\lfloor \frac{\left( n-4\right) ^{2}}{4}\right\rfloor & \text{if $n$ is odd.} \end{cases}\] ◻
We note that a graph consisting of a path and three or more isolated vertices has an asymmetric index of at least two. Hence we have the following result.
Corollary 1. Let \(n\geq6\). Then \(ai( P_{n}+tK_{1}) =1\) if and only if \(t\leq 2\).
It was shown in Brewer et al. [2] that the asymmetric index of a cycle on at least six vertices is 2. We will consider cycles with at least six vertices as the asymmetric index is not defined for cycles with fewer than six vertices [1]. The cycle \(C_n\) with \(n\geq 6\) can be turned into an asymmetric graph by adding two edges. This can be achieved in three different ways. If \(C_n\) is considered to be a regular \(n\)-gon embedded in the unit circle, then two edges can be added to the \(n\)-gon. These chords either meet at a vertex, are totally disjoint, or cross in the interior of the \(n\)-gon. The conditions for which two chords can be added to \(C_n\) was determined in [2]. Now we count the total number of labelled asymmetric graphs obtained from \(C_{n}\) by adding two edges case-by-case.
Lemma 2. For \(n\geq 6\), the number of labelled asymmetric graphs obtained from \(C_n\) by adding two chords that meet at a vertex is \[A_1(n)=\begin{cases} \frac{n}{2}(n-4)^2, & \text{if $n$ is even,}\\ \frac{n}{2}(n-3)(n-5), & \text{if $n$ is odd}. \end{cases}\]
Proof. Let \(S_1(n)\) be the number of labelled non-asymmetric graphs obtained from \(C_n\) by adding two chords that meet at a vertex. We show that \[S_1(n)=\begin{cases} n(\frac{n-4}{2}), &\text{if $n$ even,}\\ n(\frac{n-3}{2}), &\text{if $n$ odd}. \end{cases}\]
Label the vertices of \(C_n\) cyclically with \(\{0,\ldots,n-1\}\), and consider adding two chords incident with \(0\). There are \(n-3\) vertices \(i\) for which we can add the edge \(\{0,i\}\), so there are \({n-3 \choose 2}\) graphs formed by adding two chords incident with \(0\).
Suppose we add chords \(\{0,i\}\) and \(\{0,j\}\). The resulting graph has a non-trivial automorphism if and only if \(i\equiv_n -j\), so we get one non-asymmetric graph for each \(2\leq i\leq \lfloor(n-1)/2\rfloor\). Performing the same count for each vertex \(1,\ldots,n-1\) gives the above formulas for \(S_1(n)\).
Thus the total number of asymmetric labelled graphs obtained this way is \(n{n-3\choose 2}-S_1(n)\). This gives the stated formulas for \(A_1(n)\). ◻
Lemma 3. For \(n\geq 8\), the number of labelled asymmetric graphs obtained from \(C_n\) by adding two chords that do not intersect is \[A_2(n)=\begin{cases} \frac{n}{2}{n-4 \choose 3}, & \text{if $n$ is even,}\\ \frac{n}{12}(n-3)(n-5)(n-7), & \text{if $n$ is odd}. \end{cases}\]
Proof. As in the proof of Lemma 2, we count the non-asymmetric graphs directly, and obtain the number of asymmetric configurations by taking the complement. We show that the total number of non-asymmetric labelled graphs with two non-intersecting chords is given by \[S_2(n)=\begin{cases} \frac{n}{2}{n-4\choose 2}, &\text{if $n$ is even,}\\ \frac{n}{4}((n-4)^{2}-1), &\text{if $n$ is odd.} \end{cases}\]
Again, label the vertices of \(C_n\) cyclically with \(\{0,\ldots,n-1\}\). Consider adding chords \(\{0,i\}\) and \(\{j,k\}\) where \(0,i,j,k\) occur in cyclic order. In order to add edges \(\{0,i\}\) and \(\{j,k\}\) we must have at least one vertex between \(0\) and \(i\), and between \(j\) and \(k\) in cyclic order. If we suppress an arbitrary vertex between each, then we have \(0\) and three vertices chosen on \(C_{n-2}\). Likewise, choosing three vertices \(i',j',k'\) in cyclic order on \(C_{n-2}\), then inserting a vertex between each of the pairs \(0, i'\) and \(j', k'\), we end up with vertices \(0,i,j,k\) on \(C_n\) so that \(\{0,i\}\) and \(\{j,k\}\) can be added to form non-intersecting chords. Thus the total number of configurations anchored at \(0\) is \({n-3\choose 3}\).
The non-asymmetric graphs with two non-intersecting chords anchored at \(0\) fall into three categories. We count the total number of each in turn.
First, consider the case where the cycle that uses the path along \(C_n\) from \(0\) to \(i\) and the edge \(\{0,i\}\) has the same length as the cycle that uses the path along \(C_n\) from \(j\) to \(k\) and the edge \(\{j,k\}\). This occurs when \(i-0=k-j\), or equivalently when \(i+j=k\). So if we choose \(i\), then \(k\) must be \(i+j\), and we have \(n-2i-1\) choices for \(j\). Thus the total number of non-asymmetric graphs of this type is \[f(n)=\sum_{i=2}^{\lfloor n/2\rfloor-1}(n-2i-1)=\begin{cases} (n/2-2)^2, & \text{if $n$ is even,}\\ n^2/4-2n+15/4, & \text{if $n$ is odd.} \end{cases}\]
The second type of non-asymmetric graph occurs when the paths along \(C_n\) from \(i\) to \(j\), and from \(k\) to \(0\) have the same length. These graphs are exactly the same as graphs of the first type, except we want the equal cycle segments to appear clockwise instead of counterclockwise. So the number of graphs of this type is also \(f(n)\).
Finally, the third category of non-asymmetric graph comprises graphs that fall into both the first type, and the second type. That is, the paths along \(C_n\) from \(0\) to \(i\) and from \(j\) to \(k\) have the same length, and the paths along \(C_n\) from \(i\) to \(j\) and from \(k\) to \(0\) have the same length. In our counting above, we have double-counted these. This can only occur when \(n\) is even, and choosing \(i\) fixes both \(j\) and \(k\). Since \(2\leq i\leq n/2-1\), there are \(n/2-2\) of these graphs.
We have counted the graphs anchored at \(0\). So to recover the total number of graphs we multiply by \(n\) to account for the \(n\) choices of anchor, and divide by \(2\) as each graph appears twice, anchored at different vertices. Thus we obtain the stated formulas for \(S_2(n)\).
This implies that the total number of asymmetric labelled graphs is \((n/2){n-3\choose 3}-S_2(n)\), and gives the stated formulas for \(A_2(n)\). ◻
Lemma 4. For \(n\geq 7\), the number of labelled asymmetric graphs obtained from \(C_n\) by adding two crossing chords is \[A_3(n)=\begin{cases} \frac{n^2}{24}(n-4)(n-5), & \text{if $n\equiv_4 0$,}\\ \frac{n}{24}(n-1)(n-2)(n-6), & \text{if $n\equiv_4 2$,}\\ \frac{n}{24}(n-1)(n-3)(n-5), & \text{if $n\equiv_4 1,3$.} \end{cases}\]
Proof. As in the proofs of the preceding lemmas, we count the non-asymmetric graphs directly. We show that the total number of non-asymmetric labelled graphs with two crossing chords is given by \[S_3(n)=\begin{cases} \frac{n}{2}(\frac{n-1}{2})(\frac{n-2}{2})-\frac{n}{2},& n\equiv_4 0,\\ \frac{n}{2}(\frac{n-1}{2})(\frac{n-2}{2}), & n\equiv_4 2,\\ \frac{n}{2}(\frac{n-1}{2})(\frac{n-3}{2}), & n\equiv_4 1,3. \end{cases}\]
Label the vertices of \(C_n\) cyclically with \(\{0,\ldots,n-1\}\). Note that every choice of \(4\) vertices corresponds to a graph with two intersecting chords. So the total number of graphs is \({n\choose 4}\). We count the non-asymmetric graphs by choosing \(0\), and additional vertices \(i,j,k\) that appear in cyclic order. These vertices separate \(C_n\) into paths with \(a,b,c,d\) edges respectively. The graph obtained by adding the crossing edges is symmetric when exactly one of the following holds:
\(a=b\) and \(c=d\);
\(a=d\) and \(b=c\);
\(a=c\) or \(b=d\).
We begin by counting the non-asymmetric graphs of type (3). More specifically, we count the symmetries where \(a=c\). Assume \(n\) is odd. If \(i\) is fixed, then \(a\) is determined, and choosing \(j\) forces \(k=j+a\). So for all \(1\leq i\leq (n-1)/2\) we have \(n-2i-1\) choices for \(j\), and so there are \(2{(n-1)/2\choose 2}\) such graphs. Now since \(n\) is odd, \(b\neq d\) and all of the non-asymmetric graphs arise in this way. As we let the anchor range from \(0\) to \(n-1\) we count every such configuration twice, so we have \(n(n-1)(n-3)/8\) in total.
If \(n\) is even, then we can apply the same logic as in the previous paragraph. Take \(a=c\) and as \(i\) varies from \(1\) to \(n/2-1\) the same calculation gives \(n(n-2)(n-4)/8\) type (3) graphs. These account from all graphs that arise when \(a=c\) or \(b=d\), but not both. When \(a=c\) and \(b=d\), then the two intersecting chords both bisect \(C_n\). There are \(n/2\) such chords, so there are an additional \({n/2\choose 2}\) graphs when \(n\) is even.
For the non-asymmetric graphs of types (1) and (2), we see that \(n\) must be even. Moreover, these cases are rotationally equivalent. So it suffices to count those of type (1). If \(a=b\), and \(c=d\), then \(a+d=b+c\) and \(\{i,k\}\) bisects \(C_n\). So we can count these graphs by fixing a bisector of \(C_n\), and counting all of the “perpendicular bisectors” of this chord. There are \(n/2-1\) of these, so we have \((n/2)(n/2-1)\) non-asymmetric graphs of type (1).
Finally, when \(n\) is even we need to pay attention to overcounting. If \(n\) is divisible by \(4\), then it is possible that \(a=b=c=d\). In this case, our non-asymmetric graph is counted \(3\) times (it appears once as type (3), and then twice as type (1)). Thus we need to subtract off \(2(n/4)=n/2\) to fix our overcounting. Putting everything together we find the total number of non-asymmetric labelled graphs is \(S_3(n)\) as given.
Now the total number of asymmetric labelled graphs is \({n\choose 4}-S_3(n)\), which gives the stated formulas for \(A_3(n)\). ◻
Putting together Lemmas 2, 3, and 4 we get the following formula for the total number of labelled asymmetric graphs.
Theorem 5. For \(n\geq 8\), the number of labelled asymmetric graphs that can be obtained from \(C_n\) by adding two edges is \[A_C(n)=A_1(n)+A_2(n)+A_3(n)=\begin{cases} \frac{n}{8}(n-1)(n-4)^2,& \text{if $n\equiv_4 0$,}\\ \frac{n}{8}(n-2)^2(n-5), & \text{if $n\equiv_4 2$,}\\ \frac{n}{8}(n-1)(n-3)(n-5), & \text{if $n\equiv_4 1,3$}. \end{cases}\] ◻
We can phrase this result in terms of the probability of creating an asymmetric graph by adding edges to a cycle. Given a cycle \(C_n\) with \(n\geq 8\), adding two edges at random results in an asymmetric graph with probability \(\operatorname{Pr}(n)=A_C(n)/T(n)\), where \[T(n)={ {n\choose 2}-n \choose 2}=\frac{n}{8}(n-3)(n^2-3n-2)\] is the total number of ways to add a pair of edges to \(C_n\). In each of the three cases, \(\operatorname{Pr}(n)\) converges quickly to \(1\). Extending Theorem 5, we consider the graph \(C_n\cup K_1\) for \(n\geq 6\). In fact, the asymmetric index of a cycle (with at least six vertices) with one or two isolated vertices is the same as the asymmetric index of a cycle.
Corollary 2. We have that \(ai(C_{n}\cup 2K_{1})=ai(C_{n}\cup K_{1})=ai(C_{n})=2\).
Proof. We consider the case of \(C_n\cup 2K_1\) (the graph obtained from \(C_n\) by adding two isolated vertices) for \(n\geq 5\). In this case we must add one edge joining one of the isolated vertices to the cycle, as well as an edge amongst the cycle vertices to break the reflection that fixes a vertex of degree 1 and a vertex on the original cycle. It is clear that \(ai(C_{n}\cup K_{1})\leq 2\) since the same two edges that could be added to \(C_n\) to create an asymmetric graph, could be added to \(C_n\cup K_1\) to create an asymmetric graph. To show the reverse inequality, we first note that adding a chord to the cycle will leave an automorphism that is a reflection that preserves that two vertices incident to the chord. We next note that adding an edge incident to the isolated vertex will leave a graph that has a reflection preserving the vertex (now of degree 1) and a vertex in the original cycle as a non-trivial automorphism, so \(ai(C_{n}\cup K_{1})\geq 2\). ◻
Theorem 6. The number of labelled asymmetric graphs that can be obtained from \(C_n\cup 2K_1\), when \(n\geq 5\), by adding two edges is \[A_C(n,2)=\begin{cases} n^2(n-4), & \text{for $n$ even,}\\ n(n-1)(n-3), & \text{for $n$ odd.} \end{cases}\]
Proof. Consider the cycle \(C_n\) with vertices labelled \(\{0,\ldots,n-1\}\) in cyclic order. Label the isolated vertices \(a\) and \(b\). Now suppose we add the edge \(\{0,a\}\) to \(C_n\cup 2K_1\). The resulting graph has a single non trivial automorphism \(\phi\) that can be described as a “reflection” about the vertex \(0\). That is, \(\phi\) fixes \(a\), \(b\), and \(0\) pointwise, and maps \(\phi(i)=n-i\) for all \(1\leq i\leq n-1\).
To break this symmetry, we add one edge to \(C_n\) so that \(\phi\) is no longer an automorphism, and no new automorphism is created. Suppose we add the edge \(\{i,j\}\) for some \(0\leq i,j\leq n-1\). Then \(\phi\) is no longer an automorphism unless \(j=n-i\), and no new automorphism is created. Thus there are \[A(n)=\begin{cases} n(n-4)/2, & \text{if $n$ is even,}\\ (n-1)(n-3)/2, & \text{if $n$ is odd,} \end{cases}\] edges that can be added to break the symmetry. Here the difference between the even and odd case is that when \(n\) is odd, \(i=0, (n-1)/2\), and \((n+1)/2\) have no invalid choice of \(j\).
Finally, we have \(A(n)\) sets of two edges for each “anchor” vertex \(i\) on \(C_n\), and two choices for which of \(a\) and \(b\) to connect \(i\) to. Thus the total number is \(2nA(n)\), which is the given formula. ◻
In this section our focus is on the graphs \(G(m,n)=P_m\Box P_n\). For rectangular grids, \(ai(G(m,n))=1\), and we let \(A_G(m,n)\) be the number of edges \(e\) so that \(G(m,n)-e\) is asymmetric. Note that \(A_G(m,n)\) is symmetric in its inputs. Throughout, we let \(P_n\) be labelled with the numbers \(\{0,\ldots,n-1\}\) in linear order, so the vertices of \(G(m,n)\) are labelled with the pairs \((i,j)\) for \(0\leq i\leq m-1\) and \(0\leq j\leq n-1\).
Theorem 7. For \(m\geq 2\) we have \[A_G(m,2)=A_G(2,m)=\begin{cases} 0, & m\in\{2,3\},\\ 4, & m=4,\\ 2m-6, & \text{$m\geq 5$ is odd,}\\ 2m-8, & \text{$m\geq 6$ is even.} \end{cases}\]
Proof. For \(m\leq 4\) the result is easily verified. Suppose \(m\geq 5\). Let \(\phi\) be the automorphism that maps \((i,0)\mapsto (i,1)\) and \((i,1)\mapsto (i,0)\). Then if \(e=\{(i,0),(i,1)\}\), \(\phi\) is an automorphism of \(G(m,2)-e\). So none of the edges of this type can be removed to create an asymmetric graph.
Given symmetry by \(\phi\), we consider the edges of the form \(e=\{(i,1),(i+1,1)\}\). Consider the graph \(G=G(m,2)-e\). When \(i=0\) or \(i=m-2\), the graph \(G\) is isomorphic to \(G(m-1,2)\) with a path of length 2 appended to one of its “corner” vertices. Since \(m-1\geq 6\) we see that the automorphisms of \(G(m-1,2)\) permute the corner vertices among themselves, and that the stabilizer of each is trivial. Thus \(G\) is asymmetric.
Now suppose \(1\leq i\leq m-3\). The graph \(G\) is isomorphic to \(G(i+1,2)\) and \(G(m-i-1,2)\) joined by a cut edge connecting two of their corner vertices. Call the vertices incident with the edge \(u\) and \(v\). Any automorphism of \(G\) either fixes \(u\) and \(v\), or swaps them. If \(u\) and \(v\) are swapped, then the automorphism swaps \(G(i+1,2)\) and \(G(m-i-1,2)\) which implies that \(i+1=m-i-1\). This is only possible when \(m\) is even and \(i=(m-2)/2\). If \(\phi\) is a non-trivial automorphism of \(G\) that fixes both \(u\) and \(v\), then \(\phi\) is a non-trivial automorphism on one of \(G(i+1,2)\) and \(G(m-i-1,2)\) that fixes a corner vertex. This is only possible if \(i+1=2\), or \(m-i-1=2\). Since \(m\geq 5\), we see that this gives two choices for \(i\) that result in a non-asymmetric graph \(G\).
Thus the total number of edges \(e\) for which \(G\) is asymmetric is \(2((m-1)-2)=2m-6\) when \(m\) is odd, and \(2((m-1)-1-2)=2m-8\) when \(m\) is even. ◻
Theorem 8. For \(m,n\geq 3\), \[A_G(m,n)=\begin{cases} 2(m-1)(n-1)-2, & \text{$m,n$ are both even,}\\ 2(m-1)(n-1)-1, & \text{exactly one of $m$ and $n$ is even,}\\ 2(m-1)(n-1), & \text{$m,n$ are both odd.} \end{cases}\]
Proof. Note that every automorphism of \(G(m,n)\) is determined by its action on the corner vertices. Since the corners are the only vertices of degree \(2\) in \(G(m,n)\), any automorphism \(\phi\) permutes the corners amongst themselves. Once we specify \(\phi\)’s action on the corner vertices, we have also determined the action of \(\phi\) on the paths between the corners along the boundary. This follows as the non-corner boundary vertices are the only vertices of degree \(3\). Thus their images under \(\phi\) are determined by their distances to the nearest corner vertices. This implies that the corners fix the action of \(\phi\) on the entire boundary cycle \(C\). Now consider \(G(m,n)-C\). This graph is isomorphic to \(G(m-2,n-2)\). Again on this smaller grid, the action of \(\phi\) on \(C\) determines the images of the corner vertices of \(G(m-2,n-2)\). This follows as each such corner is contained in a \(C_4\), the remaining vertices of which have already been mapped by \(\phi\). Now we simply iterate the previous argument. The images of the corners of \(G(m-2,n-2)\) are determined, thus its outer cycle is determined, we remove this cycle and consider the next smaller grid. Thus the action of \(\phi\) on the corners of \(G(m,n)\) determines \(\phi\) completely.
Now consider the graph \(G=G(m,n)-e\) for some edge \(e\) of \(G(m,n)\). We refer to \(e\) as a vertical edge if \(e=\{(i,j),(i,j+1)\}\), or a horizontal edge if \(e=\{(i,j),(i+1,j)\}\). Note that the argument in the previous paragraph implies that every automorphism of \(G(m,n)\) either maps every horizontal edge to a horizontal edge and every vertical edge to a vertical edge, or every horizontal edge to a vertical edge and vice versa. This implies that the automorphisms of \(G\) map horizontal edges to horizontal edges, and vertical edges to vertical edges. It also follows from our first argument that the automorphisms of \(G\) are also determined by their action on the corner vertices of \(G(m,n)\). Together this implies that the only possible non-identity automorphisms of \(G-e\) (for any edge \(e\)) are the maps \[\begin{array}{rl} \rho: & (i,j)\mapsto (m-1-i,j),\quad \text{and}\\ \tau: & (i,j)\mapsto (i,n-1-j). \end{array}\]
If \(e\) is a vertical edge, then \(\rho\) is only an automorphism if \(e=\{((m-1)/2,j),((m-1)/2,j+1)\}\), in which case \(m\) must be odd. Also, if \(e\) is vertical, then \(\tau\) is only an automorphism if \(e=\{(i,n/2-1),(i,n/2)\}\), in which case \(n\) is even. Similarly, if \(e\) is a horizontal edge, then \(\rho\) is only an automorphism if \(e=\{(m/2-1,j),(m/2,j)\}\), in which case \(m\) must be even; and \(\tau\) is only an automorphism if \(e=\{(i,(n-1)/2),(i+1,(n-1)/2)\}\), in which case \(n\) is odd. Now a simple count completes the proof. ◻
As for paths and cycles, we consider the graphs \(G(m,n)\cup tK_1\) for \(t\in\{1,2\}\). For \(G(m,n)\cup 2K_1\), there is always an automorphism swapping two isolated vertices, so this graph can no longer be made asymmetric by the deletion of an edge. We see that \(ai(G(m,n)\cup 2K_1)=ai(G(m,n))=1\), however now we must add an edge instead of deleting one.
Theorem 9. The number of labelled asymmetric graphs that can be created by adding an edge to \(G(m,n)\cup 2K_1\) is \[A_G(m,n,2)=\begin{cases} 0, & m=n=2,\\ 2m(n-1), & \text{$m\geq 3$ odd, $n\geq 3$ even,}\\ 2n(m-1), & \text{$m\geq 3$ even $n\geq 3$ odd,}\\ 2(mn-m-n+1), & \text{$m\geq 3$ odd, $n\geq 3$ odd, $m\neq n$,}\\ 2mn, & \text{$m\geq 3$ even, $n\geq 3$ even, $m\neq n$,}\\ 2(n-1)(n-3), & \text{$m=n\geq 3$ odd,}\\ 2n(n-2), & \text{$m=n\geq 3$ even.} \end{cases}\]
Proof. Let \(a\) and \(b\) be the isolated vertices added to \(G(m,n)\). Consider adding the edge \(e=\{a,(i,j)\}\) to \(G(m,n)\cup 2K_1\) to create the graph \(G'\). Note that \(G'\) has a non-trivial automorphism if and only if \((i,j)\) has a non-trivial stabilizer as a vertex of \(G(m,n)\). As was proved in the previous proof, the automorphisms of \(G(m,n)\) are determined by their action on the corner vertices. This implies that the only vertices with non-trivial stabilizers are: the vertices \(((m-1)/2,j)\) when \(m\) is odd; the vertices \((i,(n-1)/2)\) when \(n\) is odd; and, the vertices \((i,i)\) and the vertices \((i,n-1-i)\) when \(m=n\).
In the first case, we have \(m\) vertices for which the edge \(e\) results in a non-asymmetric graph. In the second, we have \(n\) such vertices; and, in the last we have \(2n\) when \(n\) is even and \(2n-1\) when \(n\) is odd (in the \(n=m\) odd case there is a centre vertex that is counted twice). Subtracting these from the total number of vertices \(mn\), and multiplying by \(2\) to account for both \(a\) and \(b\), gives the stated formulas. ◻
Note that Theorem 9 establishes part of the analogous result for \(G(m,n)\cup K_1\). For \(G(m,n)\cup K_1\), the asymmetric index can be realized by adding one edge. If the edge is added between a vertex of \(G(m,n)\) and the isolated vertex, then the number of asymmetric graphs that result is counted as \(A_G(m,n,2)/2\). However, for \(G(m,n)\cup K_1\) in addition to deleting an edge we can also add an edge to create an asymmetric graph.
Our results on \(G(m,n)\) suggest an extension to cylindrical grids, \(P_m\Box C_n\), and toroidal grids, \(C_m\Box C_n\). We know that \(ai(P_m\Box C_n)=1\). However, unlike \(G(m,n)\) these graphs have their asymmetric index realized by adding an edge, as opposed to removing an edge. For toroidal grids, \(ai(C_m\Box C_n)=2\), and this can be realized either by adding two edges, or subtracting two edges.
The enumeration problems for the graphs mentioned in the above two paragraphs are a natural direction for future research, and would make good problems for undergraduate research.
In this section we give a recursive construction that will result in an infinite families of minimally non-asymmetric graphs.
Theorem 10. There exists an infinite class of recursively-built minimally non-asymmetric graphs.
Proof. We start with the graph \(G\) on 9 vertices shown in Figure 1. We note that \(G\) has only one non-trivial automorphism (corresponding to a reflection of the picture in Figure 1 over the vertical line through vertex \(4\)). Since the removal of any edge will remove this symmetry, \(G\) is minimally non-asymmetric.
We then extend \(G\) by subdividing the edges \(\{2,3\}\) and \(\{6,7\}\) with vertices \(y\) and \(v\) respectively, and adding two additional vertices \(x\), attached to \(1\), \(3\), \(9\), and \(y\), and \(u\) attached to \(5\), \(6\), \(8\) and \(v\). This operation preserves the asymmetric index of the graph and the single automorphism (which corresponds to the reflection of the picture in Figure 1 over the vertical line through \(4\)). Hence the extended graph \(G'\) is also minimally non-asymmetric.
The construction of \(G'\) from \(G\) can be repeated as follows. In \(G'\) we have induced \(4\)-cycles \(\{7,8,u,v\}\) and \(\{2,9,x,y\}\). Add a new vertex in the middle of \(\{7,8,u,v\}\), and connect it to \(8\), \(u\), and \(v\), along with an additional vertex \(v'\) that bisects the edge \(\{7,v\}\). Perform the same operation to the cycle \(\{2,9,x,y\}\). This results in a minimally non-asymmetric graph \(G''\) that again has two induced \(4\)-cycles on its ends.
This extension procedure can be repeated to create an infinite family of minimally non-asymmetric graphs.
We leave verification that the graphs in Figure 1 and Figure 2 are minimally non-asymmetric to the reader.
Let \(G=G^{(k)}\) be the result of applying the construction shown between the graphs in Figure 1 and Figure 2 \(k\) times, for \(k\geq 2\). To show that \(G\) is minimally non-asymmetric, we reverse the recursive process by identifying a graph \(H=H(G)\) created by removing the two vertices \(\{u,x\}\), and merging vertex \(v\) with vertex \(7\) and vertex \(y\) with vertex \(2\). If it is the case that in \(G^{(k)}-e\) that \(e=(v,7)\) or \((y,2)\) then simply delete \(v\) or \(y\) from \(H\), in lieu of merging.
Now consider an automorphism \(\phi\) of \(G=G^{(k)}\). Due to the large degree of vertices \(8\) and \(9\), with adjacent vertices \(7\) and \(2\) each with small degree, \(\phi |_{\{2,9,x,y,7,8,u,v\}}\) is the identity or \(\phi |_{\{2,9,x,y,7,8,u,v\}}=(7,2)(8,9)(u,x)(y,v)\). Then \(\phi |_{V(G)-\{u,v,x,y\}}\) forms an automorphism of \(H\). If \(G=G^{(k)}\), then \(H=G^{(k-1)}\), so by induction, we can conclude that the only non-trivial automorphism of \(G^{(k)}\) is a horizontal reflection.
In a similar manner, let \(G^{\prime }=\) \(G^{(k)}-e\) and consider an automorphism \(\phi\). As long as \(e\) is not incident to either \(u\) or \(x\) then \(\phi |_{V(G)-\{u,v,x,z\}}\) would form an automorphism of \(H(G^{\prime })=G^{^{\prime }(k-1)}-e\) so by induction \(\phi\) is the trivial automorphism.
Finally if \(e\) is incident to either \(u\) or \(x\) then there is a common neighbor of either \(v\) and \(8\) or \(y=\phi (v)\) and \(9=\phi (8)\) but not both, which is a contradiction. If not then \(u\) and \(x\) are the common neighbors of \(v\) and \(8\), and \(y\) and \(9\), respectively, so \(\phi (u)=x\) and \(\phi (x)=u\). However since \(u\) and \(x\) have different degrees, we have a contradiction. ◻
Let \(\operatorname{Pr}_e(G)\) denote the probability that the removal of a randomly selected edge from \(G\) results in an asymmetric graph. We show that for any rational number \(0\leq \alpha\leq 1\) there exists a graph \(G\) where \(\operatorname{Pr}_e(G)=\alpha\).
Theorem 11. For any rational number \(0\leq \alpha\leq 1\) there exists a graph \(G\) such that \(\operatorname{Pr}_e(G)=\alpha\).
Proof. For a minimally non-asymmetric graph \(G\), \(\operatorname{Pr}_e(G)=1\), and \(\operatorname{Pr}_e(K_n)=0\). To construct a graph \(G_{\alpha}\) for which \(\operatorname{Pr}_e(G_{\alpha})=\alpha\) when \(0<\alpha<1\) is a rational number, we introduce the graph \(H\) shown in Figure 3. Note that \(H\) is minimally non-asymmetric.
Let \(H'\) be the graph shown in Figure 4. This graph is constructed from \(H\) by adding the edge \(e\) to \(H\). Note that removing any edge other than \(e\) from \(H'\) results in an asymmetric graph, but \(H'-e\) is not asymmetric. Thus \(\operatorname{Pr}_e(H')=12/13\).
Note that we can modify \(H'\) by replacing the induced \(6\)-cycle on the left side of the picture in Figure 4 by an arbitrarily large even cycle. Let \(H_t\) be the graph in Figure 5 where the \(6\)-cycle in \(H'\) is replaced with an even cycle of length \(2t\). In the generalization, the graph has only one non-trivial automorphism (refection over the horizontal midline). As a result the edge \(e\) is the only edge that is not changed under this automorphism. Hence for all \(t\geq 6\) we see that \(\operatorname{Pr}_e(H_t)=(2t+6)/(2t+7)\), and \(e\) is the only edge whose removal results in a non-asymmetric graph.
We also note that in \(H_t\) subdividing the edge \(e\) gives a graph in which the removal of any original edge gives an asymmetric graph, while the removal of any edge produced in the subdivision of \(e\) gives a non-asymmetric graph. Let \(H_t(c)\) be the graph obtained from \(H_t\) by subdividing the edge \(e\) to produce \(c\) edges.
Now suppose we are given \(\alpha=x/y\), a rational number \(0<\alpha<1\). Then we have \(x,y\) positive integers with \(x<y\). Without loss of generality we can assume that \(12<x<y\). Consider the graph \(H_t(c)\). The total number of edges in \(H_t(c)\) is \(2t+c+6\), and there are \(2t+6\) edges whose removal gives an asymmetric graph. We want \[\frac{x}{y}=\frac{2t+6}{2t+6+c},\] which implies \[c=(2t+6)\left(\frac{y-x}{x}\right).\] We can always choose \(t\) so that the right-hand side is a positive integer. This gives values of \(t\) and \(c\) so that \(\operatorname{Pr}_e(H_t(c))=x/y\). ◻
We would like to thank two anonymous referees whose careful reading and comments helped improve the presentation of this paper. In particular we are grateful to one referee for providing the outline for the proof of Theorem 16. This research was supported by the National Science Foundation Research for Undergraduates Award 1659075.
The authors declare no conflict of interest.