Fixing Numbers of Point-Block Incidence Graphs

Abstract

A vertex in a graph is referred to as fixed if it is mapped to itself under every automorphism of the vertices. The fixing number of a graph is the minimum number of vertices, when fixed, that fixes all of the vertices in the graph. Fixing numbers were first introduced by Laison and Gibbons, and independently by Erwin and Harary. Fixing numbers have also been referred to as determining numbers by Boutin. The main motivation is to remove all symmetries from a graph. A very simple application is in the creation of QR codes where the symbols must be fixed against any rotation. We determine the fixing number for several families of graphs, including those arising from combinatorial block designs. We also present several infinite families of graphs with an even stronger condition, where fixing any vertex in a graph fixes every vertex.

1. Introduction

We consider the problem of removing all non-trivial automorphisms from a graph by fixing a smallest set of vertices. The original motivation for this problem came from the following problem proposed by Frank Rubin [1] and referenced in [2]:

Professor X, who is visually impaired, keeps their keys on a circular key ring. Assume there are a variety of handle shapes available that can be distinguished by touch. We will assume that all keys are symmetrical, so that a rotation of the key ring about an axis in its plane cannot be detected from an examination of a single key. What is the minimum number of shapes that Professor X needs to use in order to keep n keys on the ring and still be able to select the proper key by touch?

An automorphism of a graph G, with vertex set $V\left(G\right)$ and edge set $E\left(G\right)$, is a bijection $f:V\left(G\right)\to V\left(G\right)$ where $uv\in E\left(G\right)\iff f\left(u\right)f\left(v\right)\in E\left(G\right)$. A vertex n in a graph G is referred to as fixed if it is mapped to itself (fixed) under every automorphism of G. The fixing number of a graph G is the minimum number of vertices, when fixed, that fixes all of the vertices in G. As a result, all nontrivial automorphisms of the graph are removed. The determination of fixing numbers is of interest, as it provides insight into the famous problem of determining the automorphism group of a given graph. Fixing numbers were first introduced by Gibbons and Laison [3], as well as independently by Erwin and Harary [4]. Fixing numbers have also been referred to as determining numbers by Boutin [5]. Fixing/determining numbers have been investigated for several families of graphs such as complete graphs, paths, and cycles [4], Cayley graphs and Frucht graphs [3], Cartesian products [6], and Kneser graphs [7]. Recently, fixing numbers were determined for cographs and unit interval graphs [8].

A simple application is in the creation of QR codes where the symbols must be fixed against any rotation. A QR code is an image that stores a URL or other information that can be read by a camera on a smartphone. An example is given in Figure 1. We note in Figure 1 there are symbols in each of the corners. A distinct symbol must be placed in the lower right corner which eliminates the possibility of the QR code being rotated. This way the camera on a smartphone can be held in any direction and will still be able to orient the image correctly.

With fixing numbers, we want to eliminate the possibilities of not just rotations, but also reflections. To do this, we place a blue vertex at the upper left corner and a red vertex at the upper right corner. The fixing of these two vertices fixes all vertices in the graph (Figure 2).

We next present another application of fixing numbers. The removal of nontrivial automorphisms from graphs is related to a problem in robotic manipulation. In this problem, the goal is to determine the orientation of a marked sphere from a single visual image [9].

In this paper, we investigate point-block incidence graphs which arise from combinatorial designs. We will use $fix\left(G\right)$ to denote the fixing number of a graph G. We refer to a vertex as distinguishable if it is fixed under every automorphism of G.

For any undefined notation, readers are referred to the text by West [10].

In this paper, we investigate fixing numbers for point-block incidence graphs. This includes identification of infinite families of graphs, where fixing any vertex fixes every vertex, thus removing all nontrivial automorphisms from the graph.

2. Methods

We recall a basic structure from combinatorial design theory. For a given a finite set P of n elements (called points) and integers k, r, $\lambda \ge 1$, a $(n,k,\lambda )$ balanced incomplete block design (BIBD) is a set of k-element subsets of P, called blocks, such that any x in X is contained in exactly r blocks, and any pair of distinct points x and y in X is contained in exactly $\lambda$ blocks. Here is an example of a $(7,3,1)$-BIBD: $[0,1,3],[1,2,4],[2,3,5],[3,4,6],[4,5,0],[5,6,1],[6,0,2]$.

A point-block incidence graph is a bipartite graph with a set of point vertices $P=\{p_1,p_2,\dots ,p_v\}$ and a set of block vertices $B=\{B_1,B_2,\dots ,B_s\}$ where s is a positive multiple of n and $p_i\in P$ is adjacent to $B_j\in B$ if and only if $p_i\in B_j$.

In this section, we will consider point-block incidence graphs where the blocks are size 3 and are generated by the cyclic shifts of a single block, with arithmetic performed modulo n. We will use $G_n[a_r,a_s,a_t]$ to denote the point-block incidence in a graph with $n=2v$ vertices with ‘starter’ block $[a_r,a_s,a_t]$, where the points are {$a_1,a_2,...,a_v\}$ and the blocks are

$$\{[\left(a_{r+i}\right)modk,\left(a_{s+i}\right)modk,\left(a_{t+i}\right)modv]:0\le i\le k-1\}.$$

Despite their straightforward construction, point-block incidence graphs can differ in both automorphism groups and fixing numbers.

Point-block incidence graphs generated with a single starter block were investigated in [11]. We restate the main results below.

In particular, these included circulant graphs. Recall that a circulant graph $C_n\left[A\right]$ is a graph with vertices $v_1,v_2,...,v_n$ where $v_i$ is adjacent to $v_{(i+j)modn}$ and $v_{\left(i-j\right)modn}$ for each j in a list A. In our next theorem, we restate a result from [11] showing that certain circulant graphs are in fact point-block incidence graphs.

Theorem 1

([11]). Let $k\ge 6$. Then $G_{4k+2}[0,1,2]\cong C_{4k+2}[1,2k+1]$.

In the next three theorems, we show isomorphisms between different families of point-block incidence graphs.

Theorem 2

([11]). Let $k\ge 6$. Then, we have the following.

1.

 $G_{2k}[0,a,b]\cong G_{2k}[i,a+i,b+i]$ for any $0\le i\le k-1$.

2.

 $G_n[0,a,b]\cong G_n[0,ta,tb]$ for all $1\le t\le k$ where $gcd(n,t)=1$.

where all computations are performed modulo k.

Theorem 3

([11]). For any $k\ge 6$, $G_{2k}[0,a,b]\cong G_{2k}[0,b-a,b]$ where computations are performed modulo k.

Theorem 4

([11]). Let $ms\ge 3$. Then, $G_{2ms}[0,ma,mb]\cong m{G}_{2s}[0,a,b]$.

We next present a class of point-block incidence graphs that all have a fixing number of 1.

Theorem 5

([11]). The point-block incidence graph generated with single block $[0,1,3]$ with computations done mod k, when k ≥ 9, has a fixing number of 1. Furthermore, the action of fixing any vertex fixes all other vertices.

3. Results

We next investigate the fixing number of point-block incidence graphs that arise from two blocks. These graphs are bi-regular with n point vertices of degree $2k$ and the block vertices (vertices corresponding to a block) each have degree k. We note that when working modulo k, a graph generated by two different starter blocks $B_1$ and $B_2$ is same as the union of the graph generated by $B_1$ and the graph generated by $B_2$.

In our next theorem, we extend the result from Theorem 5 and present a family of point-block incidence graphs generated from two different starter blocks that have a fixing number of 1.

Theorem 6.

Let $G_{n,k}$ be the point-block incidence graph generated by the starting blocks $[0,1,2]$ and $[0,1,k]$ modulo n where $3\le k\le n-2$. If $n\ge 6$, then

$$fix\left(G_{n,k}\right)=\left\{\begin{array}{cc}2\hfill & ifnisodd,andn=2k-1;\hfill \\ 1\hfill & else.\hfill \end{array}\right.$$

Proof. 

Let $P=\{0,1,\dots ,n-1\}$ be the set of points, $C_1$ be the set of cyclic shifts of the block $[0,1,2]$, and $C_2$ be the set of cyclic shifts of the block $[0,1,k]$. Now, $V\left(G_{n,k}\right)=P\cup C_1\cup C_2$. We begin by arguing that every automorphism of $G_{n,k}$ fixes P, $C_1$, and $C_2$ setwise. Since the blocks in $C_1$ and $C_2$ each contain threepoints, and each point is in six blocks, we see that every vertex in P has degree 6 while every vertex in $C_1$ or $C_2$ has degree 3. Thus, P is fixed setwise by every automorphism of $G_{n,k}$.

Note that the permutation that maps i to $(i+1)modn$ gives an automorphism $\varphi$ of $G_{n,k}$ defined as

$$\begin{array}{ccc}\hfill \varphi \left(i\right)& =& (i+1)modn\hfill \\ \hfill \varphi \left(\right[a,b,c\left]\right)& =& \left[\varphi \right(a),\varphi (b),\varphi (c\left)\right].\hfill \end{array}$$

Since $C_1$ and $C_2$ are defined as the set of cyclic shifts of $[0,1,2]$ and $[0,1,k]$, we see that $\varphi$ is a permutation on $C_1$, and on $C_2$. Moreover, i is adjacent to $[a,b,c]$ if and only if $i\in \{a,b,c\}$. This holds if and only if $(i+1)modn\in \left\{\right(a+1)modn,(b+1)modn,(c+1)modn\}$. Thus, $\varphi$ is an automorphism of $G_{n,k}$. Repeatedly applying $\varphi$ shows that any $i\in P$ can be mapped to any $j\in P$ by an automorphism of $G_{n,k}$. The same holds for the elements of $C_1$, and of $C_2$.

Now, consider the 4-cycles in $G_{n,k}$ containing the block $[a,b,c]$. The neighbors of $[a,b,c]$ are $\{a,b,c\}$. Therefore, every 4-cycle containing $[a,b,c]$ has the form

$$\begin{array}{ccc}& & [a,b,c],a,[a,b,x],b,[a,b,c];\hfill \\ & & [a,b,c],a,[a,c,x],c,[a,b,c];\mathrm{or}\hfill \\ & & [a,b,c],b,[b,c,x],c,[a,b,c]\hfill \end{array}$$

where $x\in P$. Of course, these 4-cycles only exist if there are values of x for which $[a,b,x]$, $[a,c,x]$, or $[b,c,x]$ are vertices of $G_{n,k}$. Now, consider the blocks in $C_1$. From our observation above, it suffices to consider the block $[0,1,2]$. We have blocks $[0,1,n-1]$ and $[1,2,3]$ in $C_1$ and blocks $[0,1,k]$ and $[1,2,k+1]$ in $C_2$. These give us four 4-cycles containing $[0,1,2]$. The only other possible blocks that form a 4-cycle with $[0,1,2]$ are blocks of the form $[0,2,x]$. Since $n\ge 6$, this block must be a cyclic shift of $[0,1,k]$. This means either $x=3$, and $k=n-2$, or $x=n-1$ and $k=3$, and these cases are disjoint. Thus, either every block in $C_1$ lies in exactly four 4-cycles, or every block in $C_1$ lies in exactly five 4-cycles (depending on the value of k).

For the blocks in $C_2$, it suffices to consider $[0,1,k]$. As above, we see $[0,1,2]$ and $[0,1,n-1]$ are both blocks in $C_1$, giving us two 4-cycles containing $[0,1,k]$. The block $[0,k,x]$ forms a 4-cycle with $[0,1,k]$ only if $x=k-1$ and $k=n-1$ (which is ruled out by our hypotheses) or $x=k+1$ and $n=2k$. The block $[1,k,x]$ forms a 4-cycle with $[0,1,k]$ only if $x=k-1$ and $n=2k-2$, or if $x=k+1$ and $n=2k-1$. Note that at most one of $n=2k$, $n=2k-1$, and $n=2k-2$ can be true. Thus, either every block in $C_2$ lies in exactly two 4-cycles, or every block in $C_2$ lies in exactly three 4-cycles (depending on the value of k).

Since each block in $C_1$ lies in at least four 4-cycles, and every block in $C_2$ lies in at most three 4-cycles, we see that no automorphism of $G_{n,k}$ maps any block in $C_1$ to any block in $C_2$ (and vice versa). Therefore P, $C_1$, and $C_2$ are fixed setwise by the automorphisms of $G_{n,k}$. With our previous observation about the automorphism $\varphi$, we showed that P, $C_1$, and $C_2$ are the orbits of the automorphism group of $G_{n,k}$ acting on $V\left(G_{n,k}\right)$. In particular, this means that $fix\left(G_{n,k}\right)\ge 1$.

Now, suppose we fix one of the vertices in P, without loss of generality, choose 0. Let

$$\begin{array}{ccc}\hfill N_1& =& \left\{\right[0,1,2],[0,1,n-1],[0,n-2,n-1\left]\right\}\hfill \\ \hfill N_2& =& \left\{\right[0,1,k],[0,k-1,n-1],[0,n-k,n-k-1\left]\right\}\hfill \end{array}$$

be the neighbors of 0 in $C_1$ and $C_2$, respectively. Since every automorphism of $G_{n,k}$ fixes $C_1$ and $C_2$ setwise, every automorphism of $G_{n,k}$ that fixes 0 fixes $N_1$ and $N_2$ setwise. Let $\psi$ be an automorphism of $G_{n,k}$ that fixes 0, and consider $\psi$ restricted to $N_1$. We see that $\psi$ fixes 0, 1, or 3 elements of $N_1$.

Case #1. $\psi$ fixes 0 elements of $N_1$.

In this case, $\psi$ either maps

$$\begin{array}{ccc}& & [0,1,2]\to [0,1,n-1]\to [0,n-2,n-1]\to [0,1,2],\mathrm{or}\hfill \\ & & [0,1,2]\to [0,n-2,n-1]\to [0,1,n-1]\to [0,1,2].\hfill \end{array}$$

In the first case, consider the vertex $n-1$. Since 0 is fixed, and $[0,1,n-1]\to [0,n-2,n-1]$ we have $\psi (n-1)\in \{n-2,n-1\}$. Likewise, since $[0,n-2,n-1]\to [0,1,2]$ we have $\psi (n-1)\in \{1,2\}$. However, since $n\ge 6$, $\{1,2\}\cap \{n-2,n-1\}=\varnothing$ and we have a contradiction. In the second case, we similarly observe that $\psi \left(1\right)\in \{1,2\}\cap \{n-2,n-1\}=\varnothing$ and we have a contradiction. Thus, $\psi$ cannot fix 0 elements in $N_1$.

Case #2: $\psi$ fixes exactly 1 element of $N_1$.

In this case, $\psi$ either maps

$$\begin{array}{ccc}& & [0,1,2]\to [0,1,2],\mathrm{and}[0,1,n-1]\leftrightarrow [0,n-2,n-1],\hfill \\ & & [0,n-2,n-1]\to [0,n-2,n-1],\mathrm{and}[0,1,2]\leftrightarrow [0,1,n-1],\mathrm{or}\hfill \\ & & [0,1,n-1]\to [0,1,n-1],\mathrm{and}[0,1,2]\leftrightarrow [0,n-2,n-1].\hfill \end{array}$$

In the first case, since $[0,1,2]$ and $[0,1,n-1]\to [0,n-2,n-1]$ we again see $\psi \left(1\right)\in \{1,2\}\cap \{n-2,n-1\}=\varnothing$, a contradiction. Similarly, in the second case, we see $\psi (n-1)\in \{1,2\}\cap \{n-2,n-1\}=\varnothing$, giving a contradiction. Thus, we must be in the third case.

Since $[0,1,n-1]\to [0,1,n-1]$ and $[0,n-2,n-1]\to [0,1,2]$ we have $\psi (n-1)\in \{1,n-1\}\cap \{1,2\}=\left\{1\right\}$. Thus, $\psi (n-1)=1$. This implies that $\psi \left(1\right)=n-1$. Considering 2 and $n-2$, we see that $\psi \left(2\right)=n-2$ and $\psi (n-2)=2$. Now, consider the blocks in $N_2$. Since 0 is fixed, and $1\leftrightarrow n-1$, we must have $[0,1,k]\leftrightarrow [0,k-1,n-1]$ and $k\leftrightarrow k-1$. This implies that $[0,n-k,n-k-1]$ is fixed. Therefore, $\psi (n-k)\in \{n-k-1,n-k\}$.

Now, consider the block $[1,2,3]$. We know that $\psi \left(1\right)=n-1$, and $\psi \left(2\right)=n-2$. Thus, $\psi \left([1,2,3]\right)=[n-2,n-1,x]\in C_1$. Therefore, $x\in \{0,n-3\}$. However, $\psi \left(0\right)=0$, so we must have $\psi \left(3\right)=n-3$, and $\psi (n-3)=3$. Continuing in this way (i.e., considering $[2,3,4]$, etc.), we see that $\psi \left(i\right)=(n-i)modn$ for all $i\in P$. Therefore, $\psi$ fixes $[0,1,n-1]$, and maps $\psi \left(\right[i,i+1,i+2\left]\right)=[n-i-2,n-i-1,n-i]$ for all other blocks in $C_1$. We conclude that $\psi$ is a non-trivial automorphism that fixes 0, provided $\psi$ maps the elements of $C_2$ to elements of $C_2$.

We know that $\psi$ fixes $N_2$ setwise. Since $1\leftrightarrow n-1$, this means that $k\leftrightarrow k-1$, and $[0,n-k,n-k+1]$ is fixed. This is only possible if $n=2k-1$. We also see that

$$\begin{array}{ccc}\hfill \psi \left(\right[i,i+1,k+i\left]\right)& =& [n-i,n-i-1,n-i-k]\hfill \\ & =& [1+(n-i-1),0+(n-i-1),k+(n-i-1\left)\right]\hfill \end{array}$$

where $n-i-k=k+(n-i-1)$ follows from $n=2k-1$. Thus, $\psi$ is a non-trivial automorphism of $G_{n,k}$ that fixes 0.

Case #3: $\psi$ fixes $[0,1,2]$, $[0,1,n-1]$, and $[0,n-2,n-1]$.

Here we see $\psi \left(1\right)\in \{1,2\}\cap \{1,n-1\}=\left\{1\right\}$. Therefore, $\psi \left(1\right)=1$, $\psi \left(2\right)=2$, and $\psi (n-1)=n-1$. It now follows that $\psi (n-2)=n-2$. Now, consider the block $[1,2,3]$. Since $\psi \left(1\right)=1$ and $\psi \left(2\right)=2$ it follows that $\psi \left(3\right)=3$. Continuing in this way, we see that $\psi \left(i\right)=i$ for all $i\in P$, and hence $\psi$ is the identity automorphism.

This finishes our analysis of the three possible cases for an automorphism $\psi$ of $G_{n,k}$ that fixes 0. We see that $\psi$ must be the identity automorphism unless $n=2k-1$. This establishes $fix\left(G_{n,k}\right)=1$ unless $n=2k-1$. Moreover, if $n=2k-1$ our argument establishes that there is exactly one non-identity automorphism that fixes 0. Fixing any other vertex of $G_{n,k}$ results in only the identity automorphism, so $fix\left(G_{n,k}\right)\le 2$ when $n=2k-1$. To complete the proof, we show that $fix\left(G_{n,k}\right)>1$ when $n=2k-1$.

Recall that the stabilizer of an automorpsism is the set of elements that are fixed. Let $n=2k-1$. We have shown that the stabilizer of 0 contains a non-trivial automorphism. Therefore, if $fix\left(G_{n,k}\right)=1$, then the stabilizer of a block in $C_1$ must be trivial, or the stabilizer of a block in $C_2$ must be trivial. Again, from our initial observation, it suffices to consider the blocks $[0,1,2]\in C_1$ and $[0,1,k]\in C_2$.

Suppose $\psi$ is an automorphism of $G_{n,k}$ that fixes $[0,1,2]$. Since $\psi$ fixes the neighbors of $[0,1,2]$ we see that $\{0,1,2\}$ is fixed setwise by $\psi$. We consider the elements of $\{0,1,2\}$ that are fixed by $\psi$. First, note that if $\psi \left(0\right)=0$, $\psi \left(1\right)=1$ and $\psi \left(2\right)=2$, then we have that $\psi$ is the identity automorphism.

If none of $\{0,1,2\}$ are fixed, then either

$$\begin{array}{ccc}& & 0\to 1,1\to 2,2\to 0,\mathrm{or}\hfill \\ & & 0\to 2,2\to 1,1\to 0.\hfill \end{array}$$

In the first case, $[1,2,3]\to [0,2,x]$ for some $x\ne 1$. This block is not in $C_1$ giving a contradiction. Likewise, in the second case, $[0,1,n-1]\to [0,2,x]$ for some $x\ne 1$. Again, we have a contradiction, as this block is not in $C_1$. Thus, $\psi$ fixes exactly one point in $\{0,1,2\}$.

Note that if $\psi \left(0\right)=0$, then we can reuse the argument above for automorphisms that fix 0. If $\psi$ is not the identity, then $\psi \left(i\right)=(n-i)modn$ for all $i\in P$. However, this means $\psi \left(1\right)\notin \{0,1,2\}$ giving an immediate contradiction. Likewise, if $\psi \left(2\right)=2$, then the same argument implies that $\psi \left(i\right)=(n-i+4)modn$ for all $i\in P$. Therefore, $\psi \left(0\right)\notin \{0,1,2\}$ and again we have a contradiction. Therefore, $\psi \left(0\right)=2$, $\psi \left(1\right)=1$, and $\psi \left(2\right)=0$. Again, our analysis of the automorphisms that fix 0 implies that $\psi$ is the automorphism that maps $\psi \left(i\right)=(n-i+2)modn$ for all $i\in P$. Therefore, $\psi$ is a non-trivial automorphism that fixes $[0,1,2]$. As before, fixing any additional element of P results in no non-trivial automorphisms.

Now, suppose $\psi$ is an automorphism of $G_{n,k}$ that fixes $[0,1,k]$. Here, the argument is the same as the argument above for $[0,1,2]$. Any non-identity automorphism $\psi$ that fixes $[0,1,k]$ must fix at least one of 0, 1, or k. Again, from our analysis of automorphisms that fix elements of P, we see that the only possible non-identity automorphism of $G_{n,k}$ that fixes $[0,1,k]$ is the automorphism $\psi$ that maps $\psi \left(i\right)=(n-i+1)modn$ for all $i\in P$.

Therefore, if $n=2k-1$, $fix\left(G_{n,k}\right)=2$ completing the proof. □

In our last theorem, we presented graphs with a fixing number of 1. In the next theorem, we present graphs where the fixing number is significantly larger being one-fourth the number of vertices in the graph.

Theorem 7.

(half steps) Let k be even and let G be a connected graph generated by one half step block $[0,a,\frac{k}{2}]$ or two different half step blocks, $[0,a,\frac{k}{2}]$ and $[0,b,\frac{k}{2}]$, where $1\le a,b<\frac{k}{2}$. G has fixing number $\frac{k}{2}$.

Proof. 

Suppose G is the connected graph generated from $[0,a,\frac{k}{2}]$ (or $[0,a,\frac{k}{2}]$ and $[0,b,\frac{k}{2}]$), where $1\le a,b<\frac{k}{2}$ and $k>4$. Break up the vertices into $\frac{k}{2}$ teams (sets of both points and related blocks) of 2 points and 2 blocks (or of 2 points and 4 blocks) consisting of points that are across from each other and the blocks in which those points are the middle number:

$\left\{p,p+\frac{k}{2},\left[p-a,p,p+\frac{k}{2}-a\right],\left[p+\frac{k}{2}-1,p+\frac{k}{2},p-a\right]\right\}$ or

$$\begin{gathered} \{p,p+\frac{k}{2},\left[p-a,p,p+\frac{k}{2}-a\right],\left[p+\frac{k}{2}-1,p+\frac{k}{2},p-a\right], \\ \left[p-b,p,p+\frac{k}{2}-b\right],\left[p+\frac{k}{2}-1,p+\frac{k}{2},p-b\right]\} \end{gathered}$$

For example, in mod 12 with $[0,1,6]$ we have $\{0,6,[11,0,5],[5,6,11\left]\right\}$,

$\{1,7,[0,1,6],[6,7,0\left]\right\}$, $\{2,8,[1,2,7],[7,8,1\left]\right\}$, $\{3,9,[2,3,8],[8,9,2\left]\right\}$,

$\{4,10,[3,4,9],[9,10,3\left]\right\}$, and $\{5,11,[4,5,10],[10,11,4\left]\right\}$.

We must fix at least one vertex from every set of two points and two blocks. If not, we can switch the points and switch the blocks in that set:

$p\to p+k/2\to p$

$\left[p-a,p,p+k/2-a\right]\to \left[p+k/2-a,p,p+k/2,p-a\right]\to \left[p-a,p,p+k/2-a\right]$

or

$p\to p+k/2\to p$

$\left[p-a,p,p+k/2-a\right]\to \left[p+k/2-a,p,p+k/2,p-a\right]\to \left[p-a,p,p+k/2-a\right]$

$\left[p-b,p,p+k/2-b\right]\to \left[p+k/2-b,p,p+k/2,p-b\right]\to \left[p-a,p,p+k/2-a\right]$

For example, in mod 12 with $[0,1,6]$, if the $\{0,6,[11,0,5],[5,6,11\left]\right\}$ team is free, we can switch $0\to 6\to 0$ and $[11,0,5]\to [5,6,11]\to [11,0,5]$.

The points we switched have two (or four) other block neighbors, $[p,p+a,p+\frac{k}{2}]$ and $[p+\frac{k}{2},p+\frac{k}{2}+a,p]$ (and $[p,p+b,p+\frac{k}{2}]$ and $[p+\frac{k}{2},p+\frac{k}{2}+b,p]$), but these blocks will not be affected by switching p and $p+\frac{k}{2}$ because they are each adjacent to both of these points. For example, in mod 12 we can switch 0 and 6 without affecting $[0,1,6]$ and $[6,7,0]$.

Similarly, the blocks we switched have two (or four) other point neighbors, $p-a$ and $p+k/2-a$ and (and $p-b$ and $p+k/2-b$), but these points will not be affected by switching $[p-a,p,p+k/2-a]$ and $[p+k/2-a,p+k/2,p-a]$ (and switching $[p-b,p,p+k/2-b]$ and $[p+k/2-b,p+k/2,p-b]$) because the first and third numbers in these blocks are the same. For example, in mod 12 we can switch $[11,0,5]$ and $[5,6,11]$ without affecting 5 and 11.

We can make this switch within one team without disturbing the rest of the graph, so the graph is not fixed. Then the fixing number is at least $k/2$. Next, we will will show the fixing number is at most $k/2$.

This approach works for point-block incidence graphs with one or two blocks. Suppose G is connected and generated from $[0,a,k/2]$ and $[0,b,k/2]$. Fix the points $0,1,2,\dots ,k/2-1$. Because of the $k/2$-step in both block shapes, every block has at least one number between 0 and $k/2-1$, so every block is adjacent to at least one of the fixed points.

Following a similar process as before, we will distinguish between neighbors of each fixed point. However, we will not fix every block neighbor at first.

Let $1\le p<\frac{k}{2}$. Then, p has four neighbors where p is in the first or second place and two neighbors where p is in the middle:

$[p,p+a,p+k/2],[p+k/2,p+k/2+a,p],[p-a,p,p+k/2-a],$

$[p,p+b,p+k/2],[p+k/2,p+k/2+b,p],[p-a,p,p+k/2-b]$

We next focus on the $[p-a,p,p+k/2-a]$ block from the first block design, with p in the middle. Since $p-a$ and $p$ + k/2$-a$ are $k/2$ apart, one of them must be between 0 and $k/2-1$, inclusive, so that number x is a fixed point. We can distinguish the block $[p-a,p,p+k/2-a]$ as the only vertex adjacent to both p and x. Do this for every $p=0,1,\dots ,k/2-1$. Then, we have these distinct $k/2$ blocks: $\left\{\left[i-a,i,i+k/2-a\right]|0\le i\le k/2-1\right\}$. The middle numbers range from 0 to $k/2$. The outside numbers (in the first or third places) also contain the numbers $0,1,2,\dots ,k/2-1$. This follows from the fact that we already know that each of these blocks has a number from $0,1,2,\dots ,k/2-1$ in the first or third place. We cannot have the same outside number in two different blocks. If two blocks had the same number in the first place, by the block shape they would be the same block. If two blocks had the same number one in the first place and one in the third place, i.e., $[p-a,p,p+k/2-a]$ and $[q-a,q,q+k/2-a]$ with $p-a=q+k/2-a$, then we would have $p-a=q+k/2-a$ and $p=q+k/2$. However, this is not possible because p and q are both between 0 and $k/2-1$, inclusive. Therefore, each of the distinct blocks has a different number from $0,1,2,...,k/2-1$ in the first or third place. Because of the $k/2$-step in this block shape, the first and third numbers in a block are $k/2$ apart. Therefore, each distinct block has a different number from $k/2,...,k-1$ in the first or third place.

Now, we can use the distinct blocks to distinguish the points $k/2,...,k-1$. Each of these blocks is distinct, and its two point neighbors that are between $0,1,2,...,k/2-1$, inclusive, are fixed, so we can distinguish its remaining point neighbor from $k/2,...,k-1$. Then all the points are fixed, so we can distinguish the remaining blocks by their unique set of point neighbors. The graph is fixed. □

Recall that when working $modk$ a half step block is a block with the form $[0,a,k/2]$. A double block is a block with the form $[0,a,2a]$.

Theorem 8.

(reflections) Let G be a connected graph generated from a non-double non-half step block and its reflection. Then fixing a point vertex admits a nontrivial automorphism.

Proof. 

Suppose G is the graph generated from $[0,a,b]$ and $[0,a-b,b]$ in mod k. Fix a point p. The following automorphism still exists: the points reflect across p,

$$\begin{array}{cc}\hfill p& \to p\hfill \\ \hfill p+1\to & p-1\to p+1\hfill \\ \hfill p+2\to & p-2\to p+2\hfill \\ \hfill p+3\to & p-3\to p+3\hfill \\ \hfill & ⋮\hfill \\ \hfill p+\frac{k-1}{2}\to p& +\frac{k+1}{2}\to p+\frac{k-1}{2},\mathrm{if}k\mathrm{is}\mathrm{odd}\hfill \\ \hfill p+\frac{k}{2}& \to p+\frac{k}{2},\mathrm{if}k\mathrm{is}\mathrm{even}\hfill \end{array}$$

and the blocks map accordingly,

$$\begin{array}{cc}\hfill [q,r,s]\to [2p-q,2& p-r,2p-s]\to [q,r,s].\hfill \end{array}$$

No block will map to itself, or to another block in its family. Each block maps to a block in the other family. Therefore, the graph is not fixed. □

The above theorem only addresses the point vertices. It is harder to determine how many block vertices need to be fixed to remove all non-trivial automorphisms. For the graph generated by the starter blocks $[0,1,3]$ and $[0,2,3]$ with computations done mod k, it appears that an analagous result would hold when $n=7,8$ and $n\ge 11$. We have found that when $n=7$ the fixing number is 2 where any two vertices can be fixed. When $n=8$ the fixing number is 2. When $n=9$ or 10 the fixing number is 1. When $n\ge 11$ the fixing number is at least 3.

4. Discussion

This problem could be extended to investigate fixing numbers for point block incidence graphs with more than two blocks, and blocks of different sizes. However, it would be an ambitious problem to determine just the fixing numbers for all $G_{2k}\left([a,b,c],[x,y,z]\right)$. This would require determining the currently unknown necessary and sufficient conditions for when $G_{2k}[a,b,c]\cong G_{2k}[x,y,z]$ since $G_{2k}[a,b,c]\cong G_{2k}[x,y,z]$⇔$G_{2k}\left([a,b,c],[x,y,z]\right)\cong G_{2k}[a,b,c]$.