Realizing the Asymmetric Index of a Graph

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 $\varphi$ of $G$ so that $\varphi (\{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\}\ne \{u,v\}$ so that $G-\{x,y\}$ is asymmetric. 

Proof. Let the vertices of $P_n$ $v_0,v_1,\dots ,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. 

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{array}{ll}n(\frac{n-4}{2}),& \text{if }n\text{ even,}\\ n(\frac{n-3}{2}),& \text{if }n\text{ odd}.\end{array}$$

Label the vertices of $C_n$ cyclically with $\{0,\dots ,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 $(\genfrac{}{}{0ex}{}{n-3}{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\le i\le \lfloor (n-1)/2\rfloor$. Performing the same count for each vertex $1,\dots ,n-1$ gives the above formulas for $S_1(n)$.

Thus the total number of asymmetric labelled graphs obtained this way is $n(\genfrac{}{}{0ex}{}{n-3}{2})-S_1(n)$. This gives the stated formulas for $A_1(n)$. 

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{array}{ll}\frac{n}{2}(\genfrac{}{}{0ex}{}{n-4}{2}),& \text{if }n\text{ is even,}\\ \frac{n}{4}((n-4{)}^2-1),& \text{if }n\text{ is odd.}\end{array}$$

Again, label the vertices of $C_n$ cyclically with $\{0,\dots ,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^{\prime },j^{\prime },k^{\prime }$ in cyclic order on $C_{n-2}$, then inserting a vertex between each of the pairs $0,i^{\prime }$ and $j^{\prime },k^{\prime }$, 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 $(\genfrac{}{}{0ex}{}{n-3}{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{array}{ll}(n/2-2{)}^2,& \text{if }n\text{ is even,}\\ n^2/4-2n+15/4,& \text{if }n\text{ is odd.}\end{array}$$

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\le i\le 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)(\genfrac{}{}{0ex}{}{n-3}{3})-S_2(n)$, and gives the stated formulas for $A_2(n)$. 

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{array}{ll}\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{array}$$

Label the vertices of $C_n$ cyclically with $\{0,\dots ,n-1\}$. Note that every choice of $4$ vertices corresponds to a graph with two intersecting chords. So the total number of graphs is $(\genfrac{}{}{0ex}{}{n}{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:

1. $a=b$ and $c=d$;

2. $a=d$ and $b=c$;

3. $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\le i\le (n-1)/2$ we have $n-2i-1$ choices for $j$, and so there are $2(\genfrac{}{}{0ex}{}{(n-1)/2}{2})$ such graphs. Now since $n$ is odd, $b\ne 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 $(\genfrac{}{}{0ex}{}{n/2}{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 $(\genfrac{}{}{0ex}{}{n}{4})-S_3(n)$, which gives the stated formulas for $A_3(n)$. 

Proof. We consider the case of $C_n\cup 2K_1$ (the graph obtained from $C_n$ by adding two isolated vertices) for $n\ge 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)\le 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)\ge 2$. 

Proof. Consider the cycle $C_n$ with vertices labelled $\{0,\dots ,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 $\varphi$ that can be described as a “reflection” about the vertex $0$. That is, $\varphi$ fixes $a$, $b$, and $0$ pointwise, and maps $\varphi (i)=n-i$ for all $1\le i\le n-1$.

To break this symmetry, we add one edge to $C_n$ so that $\varphi$ is no longer an automorphism, and no new automorphism is created. Suppose we add the edge $\{i,j\}$ for some $0\le i,j\le n-1$. Then $\varphi$ is no longer an automorphism unless $j=n-i$, and no new automorphism is created. Thus there are $$A(n)=\{\begin{array}{ll}n(n-4)/2,& \text{if }n\text{ is even,}\\ (n-1)(n-3)/2,& \text{if }n\text{ is odd,}\end{array}$$ 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. 

Proof. For $m\le 4$ the result is easily verified. Suppose $m\ge 5$. Let $\varphi$ be the automorphism that maps $(i,0)\mapsto (i,1)$ and $(i,1)\mapsto (i,0)$. Then if $e=\{(i,0),(i,1)\}$, $\varphi$ 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 $\varphi$, 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\ge 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\le i\le 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 $\varphi$ is a non-trivial automorphism of $G$ that fixes both $u$ and $v$, then $\varphi$ 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\ge 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. 

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 $\varphi$ permutes the corners amongst themselves. Once we specify $\varphi$’s action on the corner vertices, we have also determined the action of $\varphi$ 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 $\varphi$ are determined by their distances to the nearest corner vertices. This implies that the corners fix the action of $\varphi$ 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 $\varphi$ 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 $\varphi$. 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 $\varphi$ on the corners of $G(m,n)$ determines $\varphi$ 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),\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. 

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^{\prime }$. Note that $G^{\prime }$ 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. 

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^{\prime }$ is also minimally non-asymmetric.

The construction of $G^{\prime }$ from $G$ can be repeated as follows. In $G^{\prime }$ 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^{\prime }$ 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\ge 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 $\varphi$ of $G=G^{(k)}$. Due to the large degree of vertices $8$ and $9$, with adjacent vertices $7$ and $2$ each with small degree, $\varphi {|}_{\{2,9,x,y,7,8,u,v\}}$ is the identity or $\varphi {|}_{\{2,9,x,y,7,8,u,v\}}=(7,2)(8,9)(u,x)(y,v)$. Then $\varphi {|}_{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^{\mathrm{\prime }}=$ $G^{(k)}-e$ and consider an automorphism $\varphi$. As long as $e$ is not incident to either $u$ or $x$ then $\varphi {|}_{V(G)-\{u,v,x,z\}}$ would form an automorphism of $H(G^{\mathrm{\prime }})=G^{{}^{\mathrm{\prime }}(k-1)}-e$ so by induction $\varphi$ 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=\varphi (v)$ and $9=\varphi (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 $\varphi (u)=x$ and $\varphi (x)=u$. However since $u$ and $x$ have different degrees, we have a contradiction. 

Proof. For a minimally non-asymmetric graph $G$, ${\mathrm{Pr}}_e(G)=1$, and ${\mathrm{Pr}}_e(K_n)=0$. To construct a graph $G_{\alpha }$ for which ${\mathrm{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^{\prime }$ 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^{\prime }$ results in an asymmetric graph, but $H^{\prime }-e$ is not asymmetric. Thus ${\mathrm{Pr}}_e(H^{\prime })=12/13$.

Note that we can modify $H^{\prime }$ 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^{\prime }$ 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\ge 6$ we see that ${\mathrm{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 ${\mathrm{Pr}}_e(H_t(c))=x/y$.