Sucharita Biswas, Angsuman Das^∗

Department of Mathematics, Presidency University, Kolkata, India

sucharita.rs@presiuniv.ac.in, angsuman.maths@presiuniv.ac.in

In this paper, we introduce a new family of cubic graphs Γ(m), called Generalized Pappus graphs, where m ≥ 3. We compute the automorphism group of Γ(m) and characterize when it is a Cayley graph.

Keywords: Cayley graph, automorphism group Mathematics Subject Classification: 05C25, 05E18

DOI: 10.5614/ejgta.2022.10.1.25

1. Introduction

The study of different families of graphs with respect to their group of symmetries is an important aspect of modern algebraic graph theory. Among them the cubic families are one of the most important class of graphs. Various important families of cubic graphs which are extensively studied are Generalized Petersen graphs [2], Double Generalized Petersen graphs [5], Zhou-Ghasemi graphs [8], Zhou-Li graphs [9], Devilliers et.al. graphs [1], [4] etc. In this paper, we construct another infinite family of cubic graphs starting from the well-known Pappus graph and study its automorphism group and structural properties.

Pappus graph is a bipartite cubic graph with 18 vertices and 27 edges, formed as the Levi graph of the Pappus configuration. It is named after Pappus of Alexandria who is believed to have discovered the "hexagon theorem" describing the Pappus configuration. Recently, [7] proposed a group theoretic generalization of Pappus configuration from a projective geometric viewpoint. Our

Received: 6 October 2020, Revised: 16 April 2022, Accepted: 19 April 2022.

^∗Corresponding author

goal is to generalize it from a graph theoretic viewpoint. To begin with, we define the Genralized Pappus graph next. For other definitions and terminologies, readers are referred to [3].

Definition 1.1. Let \(m \geq 3\) be a positive integer and set n = 2m. The generalized Pappus graph \(\Gamma(m)\) is defined on the vertex set \(V = \{x_i, y_i, z_i : i \in \mathbb{Z}_n\}\), where \(x_i\)'s, \(y_i\)'s and \(z_i\)'s are called the outer vertices, middle vertices and inner vertices respectively. There are four types of edges between these vertices, namely outer edges of the form \(x_i \sim x_{i+1}\), spoke edges of the form \(x_i \sim y_i\), middle edges of the form \(y_i \sim z_{i+1}\) and \(y_i \sim z_{i-1}\) and inner edges of the form \(z_i \sim z_{i+m}\). (Here \(u \sim v\) means u and v are adjacent.)

Figure 1. Generalized Pappus Graphs, \(\Gamma(3)\) and \(\Gamma(4)\).

It is obvious that \(\Gamma(m)\) is a cubic graph of order 6m and \(\Gamma(3)\) is the Pappus graph (See Figure 1). We denote the set of outer, spoke, middle and inner edges by \(\Omega, \Sigma, \mathcal{M}\) and \(\mathcal{I}\) respectively, and the set of vertices \(x_i, y_i\) and \(z_i\) by X, Y and Z respectively.

2. Automorphism Group of \(\Gamma(m)\)

We start by noting some automorphisms of \(\Gamma(m)\). It can be easily checked that \(\rho:\Gamma(m)\to\Gamma(m)\) and \(\tau:\Gamma(m)\to\Gamma(m)\) defined by

\[\rho: x_i \mapsto x_{i+1} \qquad \tau: x_i \mapsto x_{-i}\] \[y_i \mapsto y_{i+1} \qquad y_i \mapsto y_{-i}\] \[z_i \mapsto z_{i+1} \qquad z_i \mapsto z_{-i}\]

are automorphisms of \(\Gamma(m)\) and \(\circ(\rho) = n\); \(\circ(\tau) = 2\) and \(\tau \rho \tau = \rho^{-1}\). Thus \(H = \langle \rho, \tau \rangle \cong D_n\), the dihedral group of order 2n. Moreover, if m is odd, it can be shown that \(\sigma : \Gamma(m) \to \Gamma(m)\) given

by

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

is an automorphism of Γ(m) which does not belong to H. Also we have ◦(σ) = 3, σρσ = ρ and στ = τ σ.

Theorem 2.1. If m is odd, then Γ(m) is a Cayley graph.

Proof. We prove the theorem by showing that K = ⟨ρ, σ⟩ acts regularly on Γ(m). As |K| = 3n = |Γ(m)|, it is enough to show that K acts transitively on the vertices of Γ(m).

Let us start with x0. Note that x⁰ can be mapped to any xⁱ by applying suitable powers of ρ. As σ(x0) = ym, we can map x⁰ to any yⁱ by applying suitable powers of ρ on σ(x0). And, as σρ(x0) = zm+1, we can map x⁰ to any zⁱ by applying suitable powers of ρ on σρ(x0). Thus, we can map x⁰ to any vertex of Γ(m) and vice-versa using the elements of K. Now, if we start with two arbitrary vertices, we can map one to the other via x0. Hence, K acts transitively on the vertices of Γ(m).

Lemma 2.1. Let φ ∈ Aut(Γ(m)), if φ(X) = X then φ ∈ H.

Proof. Let φ(x0) = xa, then φ(x1) = xa+1 or xa−¹ (since φ(x1) ∼ φ(x0) = xa). Let φ(x1) = xa+1. As φ(X) = X we have φ(x2) = xa+2, φ(x3) = xa+3, · · · , φ(xn−1) = xa+n−1. Now as xⁱ ∼ yⁱ , φ(xi) = xa+ⁱ ∼ φ(yi) so we have φ(yi) = ya+ⁱ for all i. Again as φ(yi−1) = ya+i−¹ and φ(yi+1) = ya+i+1, we have φ(zi) = za+ⁱ for all i. Hence, φ = ρ ^a ∈ H. Let φ(x1) = xa−1. As φ(X) = X then φ(x2) = xa−2, φ(x3) = xa−3, · · · , φ(xn−1) = xa−(n−1). Now as xⁱ ∼ yⁱ , φ(xi) = xa−ⁱ ∼ φ(yi) so we have φ(yi) = ya−ⁱ for all i. Again, as φ(yi−1) = ya−(i−1) and φ(yi+1) = ya−(i+1), we have φ(zi) = za−ⁱ for all i. Hence we have, φ = ρ a τ ∈ H.

Lemma 2.2. Let φ ∈ Aut(Γ(m)) and m ̸= 3. If φ(xi) = x^j and φ(yi) = y^j for some i, j, then φ ∈ H.

Proof. As φ(xi) = x^j and φ(yi) = y^j then φ(xi+1), φ(xi−1) ∈ {xj+1, xj−1}. Let φ(xi+1) = xj+1 and φ(xi−1) = xj−1, then φ(xi+2) = xj+2 or yj+1. If φ(xi+2) = yj+1, consider the cycle C : yⁱ ∼ xⁱ ∼ xi+1 ∼ xi+2 ∼ yi+2 ∼ zi+1 ∼ yⁱ , then φ(C) : y^j ∼ x^j ∼ xj+1 ∼ yj+1 ∼ φ(yi+2) ∼ φ(zi+1) ∼ y^j . For m ̸= 3, there exists a unique path P of length 3, namely y^j ∼ x^j ∼ xj+1 ∼ yj+1 between y^j and yj+1. Thus φ(C) is not a cycle, which is a contradiction. Hence φ(xi+2) = xj+2. Similarly, it can be shown that φ(xi+k) = xj+^k for all k, i.e., φ(X) = X. Then by Lemma 2.1, we have φ ∈ H. Similarly if φ(xi+1) = xj−¹ we can show φ ∈ H.

It is to be noted that if m = 3, there exists another path P ′ : y^j ∼ zj−¹ ∼ zj+2 ∼ yj+1 joining y^j and yj+1.

Lemma 2.3. Let φ ∈ Aut(Γ(m)) \ H. Then φ can not map consecutive spokes into Σ.

Proof. Let φ([xⁱ , yⁱ ]) ∈ Σ. We will show φ([xi+1, yi+1]) ∈/ Σ. Let m ̸= 3. As φ /∈ H, then by Lemma 2.2, we have (φ(xi), φ(yi)) ̸= (x^j , y^j ) for all j. However, as φ([xⁱ , yⁱ ]) ∈ Σ, the orientation of the spoke [xⁱ , yⁱ ] is changed by φ. Thus, we assume that φ(xi) = y^k and φ(yi) = x^k for some k. Now as φ(xi) ∼ φ(xi+1), we must have φ(xi+1) = zk−¹ or zk+1, hence φ([xi+1, yi+1]) ∈/ Σ.

Now let m = 3 and φ([xⁱ , yⁱ ]) ∈ Σ. If φ(xi) = y^k and φ(yi) = x^k for some k, then as φ(xi) ∼ φ(xi+1) we have φ(xi+1) = zk−¹ or zk+1 and hence φ([xi+1, yi+1]) ∈/ Σ. So, we assume that φ(xi) = x^k and φ(yi) = yk. Then φ(xi+1), φ(xi−1) ∈ {xk+1, xk−1}.

Let φ(xi+1) = xk+1, then φ(xi+2), φ(yi+1) ∈ {xk+2, yk+1}. If φ(yi+1) = xk+2 and φ(xi+2) = yk+1 then φ([xi+1, yi+1]) = [xk+1, xk+2] ∈/ Σ. If φ(yi+1) = yk+1 and φ(xi+2) = xk+2, consider the cycle C¹ : xi+1 ∼ yi+1 ∼ zi+2 ∼ zi+5 ∼ yⁱ ∼ xⁱ ∼ xi+1. Then φ(C1) : xk+1 ∼ yk+1 ∼ φ(zi+2) ∼ φ(zi+5) ∼ y^k ∼ x^k ∼ xk+1. As φ(C1) is a cycle then we have φ(zi+2) = zk+2 and φ(zi+5) = zk+5 (See Figure 1(Left)). Now consider the cycle C² : yi+1 ∼ xi+1 ∼ xi+2 ∼ xi+3 ∼ yi+3 ∼ zi+2 ∼ yi+1, then φ(C2) : yk+1 ∼ xk+1 ∼ xk+2 ∼ φ(xi+3) ∼ φ(yi+3) ∼ zk+2 ∼ yk+1. As φ(C2) is a cycle then we have φ(xi+3) = xk+3 and φ(yi+3) = yk+3. Proceeding this way, we get φ(X) = X and φ(Y ) = Y . Then by Lemma 2.1, we have φ ∈ H, which is a contradiction, hence φ(yi+1) ̸= yk+1, i.e., φ([xi+1, yi+1]) ∈/ Σ. Similarly we can proof this if φ(xi+1) = xk−1. This completes the proof.

Corollary 2.1. Stab(Σ) = H.

Proof. It is clear that H stabilize Σ setwise, i.e., H ⊆ Stab(Σ). Let φ ∈ Stab(Σ). Then φ([xⁱ , yⁱ ]), φ([xi+1, yi+1]) ∈ Σ for all i, and thus by Lemma 2.3, we have φ ∈ H, i.e., Stab(Σ) ⊆ H.

Lemma 2.4. Let φ ∈ Aut(Γ(m)) \ H and m ̸= 3. If φ([xⁱ , yⁱ ]) ∈ Σ, then φ([xi+2, yi+2]) ∈ Σ.

Proof. Let φ(xi) = x^j and φ(yi) = y^j , then by Lemma 2.2, we have φ ∈ H, which is a contradiction. So we assume that φ(xi) = y^j and φ(yi) = x^j . Then φ(xi+1), φ(xi−1) ∈ {zj+1, zj−1}.

Let φ(xi+1) = zj+1 and φ(xi−1) = zj−1. As φ(xi+2) ∼ φ(xi+1) and φ(xi) = y^j then φ(xi+2) = yj+2 or zj+1+m. We claim that φ(xi+2) = yj+2. If possible, let φ(xi+2) = zj+1+m. As φ(yi+1) ∼ φ(xi+1) = zj+1, φ(xi) = y^j and φ(xi+2) = zj+1+m, we have φ(yi+1) = yj+2. Now consider the cycle C : yⁱ ∼ xⁱ ∼ xi+1 ∼ xi+2 ∼ yi+2 ∼ zi+1 ∼ yⁱ . Then φ(C) : x^j ∼ y^j ∼ zj+1 ∼ zj+1+^m ∼ φ(yi+2) ∼ φ(zi+1) ∼ x^j . As there exists unique path x^j ∼ y^j ∼ zj+1 ∼ zj+1+^m of length 3 between x^j and zj+1+^m for m ̸= 3, we get φ(C) is not a cycle, which is a contradiction. Therefore φ(xi+2) = yj+2.

Now as φ(yi+2) ∼ φ(xi+2) = yj+2 and φ(xi+1) = zj+1, we have φ(yi+2) = zj+3 or xj+2. We claim that φ(yi+2) = xj+2. If possible let φ(yi+2) = zj+3. Consider the cycle C : yⁱ ∼ xⁱ ∼ xi+1 ∼ xi+2 ∼ yi+2 ∼ zi+1 ∼ yⁱ , then φ(C) : x^j ∼ y^j ∼ zj+1 ∼ yj+2 ∼ zj+3 ∼ φ(zi+1) ∼ x^j . As there does not exist any path of length 2 between x^j and zj+3, φ(C) is not a cycle, which is a contradiction. Therefore φ(yi+2) = xj+2. Therefore φ([xⁱ , yⁱ ]) = [y^j , x^j ] implies φ([xi+2, yi+2]) = [yj+2, xj+2] ∈ Σ.

Similarly we can proof this if φ(xi+1) = zj−¹ and φ(xi−1) = zj+1. This completes the proof.

From Theorem 2.1, we have if φ /∈ H, then either ∅ ̸= φ(Σ) ∩ Σ ⊊ Σ or φ(Σ) ∩ Σ = ∅. We will show in Theorem 2.2 that ∅ ̸= φ(Σ) ∩ Σ ⊊ Σ is possible only if m is odd. If φ /∈ H and m ̸= 3, then from Lemma 2.4, we have φ([xⁱ , yⁱ ]) = [y^j , x^j ] ⇒ φ([xi+2k, yi+2k]) = [yj+2k, xj+2k] for all k. At first for m ̸= 3 we consider the case when any one even spoke is mapped to an odd spoke, then by Lemma 2.4 we have all even spokes are mapped to all odd spokes and we will show that case appears only if m is odd.

Lemma 2.5. Let φ ∈ Aut(Γ(m)) \ H and m ̸= 3. If set of all even spokes are mapped to set of all odd spokes via φ, then m is odd.

Proof. Let [xe, ye] be an even spoke and [xod, yod] be an odd spoke such that φ([xe, ye]) = [xod, yod]. If φ(xe) = xod and φ(ye) = yod then by Lemma 2.2 we have φ ∈ H, which is a contradiction. So φ(xe) = yod and φ(ye) = xod. Then φ(xe+1), φ(xe−1) ∈ {zod+1, zod−1}.

Case 1. Let φ(xe+1) = zod+1 and φ(xe−1) = zod−1. As [xe+2, ye+2] is an even spoke, let φ(xe+2) = yod2, where od2 is an odd index. As x^e ∼ xe+1 ∼ xe+2, applying φ we have yod ∼ zod+1 ∼ yod2, and hence yod² = yod+2. Again, as [xe+4, ye+4] is an even spoke, let φ(xe+2) = yod3. Since the distance between xe+2 and xe+4 is 2, the distance between yod+2 and yod³ is also 2, and hence φ(xe+4) = yod+4 and so φ(ye+4) = xod+4. Proceeding this way, we have φ(xe+2k) = yod+2^k and φ(ye+2k) = xod+2^k for k = 0, . . . , m − 1. Now as xe+2^k ∼ xe+2k+1 ∼ xe+2k+2, applying φ, we have yod+2^k ∼ φ(xe+2k+1) ∼ yod+2k+2. Hence φ(xe+2k+1) = zod+2k+1 for k = 0, · · · , m − 1. Again as φ(ye+2k+1) ∼ φ(xe+2k+1) = zod+2k+1 and φ(xe+2k) = yod+2k, we have φ(ye+2k+1) = zod+(2k+1)+m. Now as ye+2k−¹ ∼ ze+2^k ∼ ye+2k+1, applying φ we have zod+(2k−1)+^m ∼ φ(ze+2k) ∼ zod+(2k+1)+m. Thus φ(ze+2k) = yod+2k+^m for k = 0, · · · , m − 1. Note that if m is even then od + 2k + m is an odd integer and so φ(ze+2k) ̸= yod+2k+^m as all even spokes are mapped to all odd spokes. Hence φ is not a graph automorphism when m is even and so m must be odd.

Case 2. Let φ(xe+1) = zod−¹ and φ(xe−1) = zod+1. Proceeding as in the previous case, it can be shown that φ(xe+2k) = yod−2k, φ(ye+2k) = xod−2^k and φ(xe−2k) = yod+2k, φ(ye−2k) = xod+2^k for k = 0, · · · , m − 1. Now as xe+2^k ∼ xe+2k+1 ∼ xe+2k+2, applying φ we have, yod−2^k ∼ φ(xe+2k+1) ∼ yod−2k−2, hence φ(xe+2k+1) = zod−(2k+1) and similarly φ(xe−(2k+1)) = zod+(2k+1) for k = 0, · · · , m − 1. As φ(ye+2k+1) ∼ φ(xe+2k+1) = zod−(2k+1) and φ(xe+2k) = yod−2k, we get φ(ye+2k+1) = zod−(2k+1)+m. Similarly φ(ye−(2k+1)) = zod+(2k+1)+m. Again, as ye+2k−¹ ∼ ze+2^k ∼ ye+2k+1, applying φ we have zod−(2k−1)+^m ∼ φ(ze+2k) ∼ zod−(2k+1)+m, and hence φ(ze+2k) = yod−2k+^m for k = 0, · · · , m − 1. Note that if m is even then od − 2k + m is an odd integer, and so φ(ze+2k) ̸= yod−2k+^m as all even spokes are mapped to all odd spokes. Hence φ is not a graph automorphism when m is even and so m must be odd.

Similarly, it can be proved that:

Lemma 2.6. Let φ ∈ Aut(Γ(m)) \ H and m ̸= 3.

• If set of all even spokes are mapped to set of all even spokes via φ, then m is odd.
• If set of all odd spokes are mapped to set of all odd spokes via φ, then m is odd.
• If set of all odd spokes are mapped to set of all even spokes via φ, then m is odd.

Theorem 2.2. Let φ ∈ Aut(Γ(m)) \ H. If ∅ ̸= φ(Σ) ∩ Σ ⊊ Σ, then m is odd.

Proof. If m = 3, then there is nothing to prove. So, we assume that m ̸= 3. As φ(Σ) ∩ Σ ̸= ∅, there exists some i such that φ([xⁱ , yⁱ ]) ∈ Σ. Then, by Lemma 2.4, we have φ([xi+2k, yi+2k]) ∈ Σ for all k. Now, depending on whether i is odd or even and depending on whether φ([xⁱ , yⁱ ]) is an even spoke or an odd spoke, we can apply Lemma 2.5 or Lemma 2.6, to prove that m is odd.

Corollary 2.2. If m is even and φ ∈ Aut(Γ(m)) \ H, then φ(Σ) ∩ Σ = ∅.

Proof. This is the contrapositive form of Theorem 2.2.

Lemma 2.7. If φ ∈ Aut(Γ(m)) \ H, then φ(Σ) ⊈ M.

Proof. If possible, let φ(Σ) ⊆ M. Then φ([x0, y0]) ∈ M. Now, two cases may arise. Either φ([x0, y0]) = [yⁱ , zi+1] or φ([x0, y0]) = [yⁱ , zi−1] for some i.

Case 1. Let φ([x0, y0]) = [yⁱ , zi+1]. If φ(x0) = yⁱ , φ(y0) = zi+1, then as φ(x1), φ(x⁻1) are adjacent to φ(x0), we have φ(x1), φ(x⁻1) ∈ {xⁱ , zi−1}. Let φ(x1) = xⁱ and φ(x⁻1) = zi−1. Then φ(y1) = xi+1 or xi−1, hence φ(x1, y1) ∈ Ω, which is a contradiction. Hence φ(x1) ̸= xⁱ or φ(x⁻1) ̸= zi−1. Similarly we get a contradiction for φ(x⁻1) = xⁱ and φ(x1) = zi−1. Thus we have φ(x0) ̸= yⁱ or φ(y0) ̸= zi+1.

If φ(x0) = zi+1 and φ(y0) = yⁱ , then as φ(x1), φ(x⁻1) are adjacent to φ(x0), we have φ(x1), φ(x⁻1) ∈ {yi+2, zi+1+m}. Let φ(x1) = yi+2 and φ(x⁻1) = zi+1+m. Then φ(x2), φ(y1) ∈ {zi+3, xi+2}. As φ(Σ) ⊂ M, we have φ(y1) = zi+3 and φ(x2) = xi+2. Then φ(y2) ∈ {xi+1, xi+3} and hence φ([x2, y2]) ∈ Ω, which is a contradiction. Hence φ(x1) ̸= yi+2 or φ(x⁻1) ̸= zi+1+m. Similarly we arrive at a contradiction for φ(x⁻1) = yi+2 and φ(x1) = zi+1+^m and then we have φ(x0) ̸= zi+1 or φ(y0) ̸= yⁱ . Therefore φ([x0, y0]) ̸= [yⁱ , zi+1].

Case 2. Let φ([x0, y0]) = [yⁱ , zi−1]. The proof is similar to that in the previous case. Combining two cases, we get the lemma.

Lemma 2.8. If m is even and φ ∈ Aut(Γ(m)) \ H, then φ(Σ) ∩ Ω = ∅.

Proof. If possible let φ(Σ) ∩ Ω ̸= ∅ and let φ([xa, ya]) ∈ Ω. Without loss of generality, we can assume that φ([xa, ya]) = [x0, x1] such that φ(xa) = x⁰ and φ(ya) = x1.

Let us first explain the rationale behind such an assumption. As φ([xa, ya]) ∈ Ω, we have φ([xa, ya]) = [x^j , xj+1] for some j. Then ρ ^−jφ([xa, ya]) = [x0, x1]. Now, ρ ^−jφ(Σ) ∩ Ω = ∅ if and only if φ(Σ) ∩ ρ j (Ω) = φ(Σ) ∩ Ω = ∅ . Thus, without loss of generality, we can assume that φ([xa, ya]) = [x0, x1]. Now, if φ(xa) = x¹ and φ(ya) = x0, we can work with ρτ in the same manner as ρτ (Ω) = Ω. Thus, the assumption is justified and we start with φ(xa) = x⁰ and φ(ya) = x1. Then φ(xa+1), φ(xa−1) ∈ {x⁻1, y0}.

Case 1. Let φ(xa+1) = y⁰ and φ(xa−1) = x⁻1. As xa−¹ ∼ ya−1, we have φ(ya−1) = x⁻² or y⁻1. If φ(ya−1) = y⁻1, then we have φ([xa−1, ya−1]) = [x⁻1, y⁻1] ∈ Σ. But this contradicts Corollary 2.2. Thus φ(ya−1) = x⁻2.

Consider the cycle C⁰ : ya−¹ ∼ xa−¹ ∼ x^a ∼ xa+1 ∼ ya+1 ∼ z^a ∼ ya−1. Then φ(C0) : x⁻² ∼ x⁻¹ ∼ x⁰ ∼ y⁰ ∼ φ(ya+1) ∼ φ(za) ∼ x⁻2. As φ(C0) is a cycle, we have φ(ya+1) = z⁻¹ and φ(za) = y⁻2.

Again, consider the cycle C¹ : y^a ∼ x^a ∼ xa+1 ∼ xa+2 ∼ ya+2 ∼ za+1 ∼ ya. Then φ(C1) : x¹ ∼ x⁰ ∼ y⁰ ∼ φ(xa+2) ∼ φ(ya+2) ∼ φ(za+1) ∼ x1. As φ(C1) is a cycle, we have φ(xa+2) = z1, φ(ya+2) = y² and φ(za+1) = x2.

Proceeding in this way and considering the cycles Cⁱ : ya+i−¹ ∼ xa+i−¹ ∼ xa+ⁱ ∼ xa+i+1 ∼ ya+i+1 ∼ za+ⁱ ∼ ya+i−1, for i = 2, · · · , n−1, we get φ(Ci) : φ(ya+i−1) ∼ φ(xa+i−1) ∼ φ(xa+i) ∼ φ(xa+i+1) ∼ φ(ya+i+1) ∼ φ(za+i) ∼ φ(ya+i−1). Hence, we have

φ(xa+12k) = x6k φ(ya+12k) = x6k+1 φ(za+12k) = y6k−2
φ(xa+12k+1) = y6k φ(ya+12k+1) = z6k−1 φ(za+12k+1) = x6k+2
φ(xa+12k+2) = z6k+1 φ(ya+12k+2) = y6k+2 φ(za+12k+2) = z6k−1+m
φ(xa+12k+3) = z6k+1+m φ(ya+12k+3) = y6k+m φ(za+12k+3) = z6k+3
φ(xa+12k+4) = y6k+2+m φ(ya+12k+4) = z6k+3+m φ(za+12k+4) = x6k+m
φ(xa+12k+5) = x6k+2+m φ(ya+12k+5) = x6k+1+m φ(za+12k+5) = y6k+4+m
φ(xa+12k+6) = x6k+3+m φ(ya+12k+6) = x6k+4+m φ(za+12k+6) = y6k+1+m
φ(xa+12k+7) = y6k+3+m φ(ya+12k+7) = z6k+2+m φ(za+12k+7) = x6k+5+m
φ(xa+12k+8) = z6k+4+m φ(ya+12k+8) = y6k+5+m φ(za+12k+8) = z6k+2
φ(xa+12k+9) = z6k+4 φ(ya+12k+9) = y6k+3 φ(za+12k+9) = z6k+6+m
φ(xa+12k+10) = y6k+5 φ(ya+12k+10) = z6k+6 φ(za+12k+10) = x6k+3
φ(xa+12k+11) = x6k+5 φ(ya+12k+11) = x6k+4 φ(za+12k+11) = y6k+7

As m is even, m is either 6k or 6k + 2 or 6k + 4. Hence n = 12k or 12k + 4 or 12k + 8.

Let m = 6k and k = 2i. Then φ(za+1+m) = φ(za+1+12i) = x6i+2. As φ(za+1) ∼ φ(za+1+m), we have x² ∼ x6i+2, i.e., 6i + 2 = 3, i.e., 3k = 1, i.e., m = 2. However, we considered m ≥ 3. Hence, a contradiction. Again, let m = 6k and k = 2i + 1, then φ(za+1+m) = φ(za+7+12i) = x6i+5+m. As φ(za+1) ∼ φ(za+1+m), we have x² ∼ x6i+5+m, i.e., hence 6i + 5 + m = 3, i.e., 3m = 2, i.e., m = 2. a contradiction. So m ̸= 6k.

Similarly, it can be shown that m ̸= 6k + 2, 6k + 4. Then φ(xa+1) ̸= y⁰ or φ(xa−1) ̸= x⁻1.

Case 2. Let φ(xa+1) = x⁻¹ and φ(xa−1) = y0. A similar technique as that in the previous case leads to a contradiction and hence we have φ([xa, ya]) ̸= [x0, x1].

Therefore, the lemma holds.

Lemma 2.9. If m is even and φ ∈ Aut(Γ(m)) \ H, then φ(Σ) ∩ I = ∅.

Proof. As m is even, by Theorem 2.2, we have φ(Σ) ∩ Σ = ∅. If possible, let φ(Σ) ∩ I ̸= ∅ and let [xⁱ , yⁱ ] be a spoke edge which is mapped into I by φ. Without loss of generality, we can assume that φ([xⁱ , yⁱ ]) = [z0, zm] with φ(xi) = z⁰ and φ(yi) = zm. (We can do so, because if φ([xⁱ , yⁱ ]) = [z^j , zj+m], then ρ ^−jφ([xⁱ , yⁱ ]) = [z0, zm]. Now, if ρ ^−jφ(Σ) ∩ I = ∅, then we also have φ(Σ) ∩ ρ j (I) = φ(Σ) ∩ I = ∅. Similarly, if φ([xⁱ , yⁱ ]) = [zj+m, z^j ], then we need to work with τ ρ^−j instead of ρ −j .) Therefore φ(xi+1), φ(xi−1) ∈ {y1, y⁻1}.

Let φ(xi+1) = y¹ and φ(xi−1) = y⁻1. Then φ(yi+1) ∈ {z2, x1} and φ(yi−1) ∈ {z⁻2, x⁻1}. As φ(Σ) ∩ Σ = ∅ then φ(yi+1) = z² and φ(yi−1) = z⁻2. Now consider the cycle C : yi−¹ ∼ xi−¹ ∼ xⁱ ∼ xi+1 ∼ yi+1 ∼ zⁱ ∼ yi−1. Then φ(C) : z⁻² ∼ y⁻¹ ∼ z⁰ ∼ y¹ ∼ z² ∼ φ(zi) ∼ z⁻2. As φ(zi) is the common neighbour of z² and z⁻2, then φ(z0) = y^j , for some j. This implies

j ≡ 2 + 1 ≡ −2 − 1 (mod 2m), i.e, m = 3, which is a contradiction as m is even. Hence, we have φ(xi+1) ̸= y¹ or φ(xi−1) ̸= y⁻1.

Similarly we can also prove that φ(xi+1) = y⁻¹ and φ(xi−1) = y¹ does not hold. Hence, the lemma holds.

Theorem 2.3. If m is even, then Aut(Γ(m)) = H = ⟨ρ, τ ⟩.

Proof. It is known that H is a subgroup of Aut(Γ(m)). If possible, let Aut(Γ(m)) \ H ̸= ∅ and φ ∈ Aut(Γ(m)) \ H. Then by Corollary 2.2, Lemma 2.8 and Lemma 2.9, we have φ(Σ) ∩ (Σ ∪ Ω ∪ I) = ∅. However, as the edge set of Γ(m) is the union of Σ, Ω,M and I, it follows that φ(Σ) ⊆ M. But this contradicts Lemma 2.7. Thus Aut(Γ(m)) = H = ⟨ρ, τ ⟩.

Lemma 2.10. If m is odd and m ̸= 3, 9, then |Stab(x0) ∩ Stab(x1)| = 1.

Proof. Let φ ∈ Stab(x0) ∩ Stab(x1). Then φ(x0) = x⁰ and φ(x1) = x1. As φ(y0), φ(x⁻1) are adjacent to φ(x0); and φ(y1), φ(x2) are adjacent to φ(x1), we have φ(y0), φ(x⁻1) ∈ {y0, x⁻1} and φ(y1), φ(x2) ∈ {y1, x2}.

Case 1. Let φ(y0) = x⁻¹ and φ(y1) = x2, and hence φ(x⁻1) = y⁰ and φ(x2) = y1.

Consider the cycle C⁰ : y⁻¹ ∼ x⁻¹ ∼ x⁰ ∼ x¹ ∼ y¹ ∼ z⁰ ∼ y⁻1. Then φ(C0) : φ(y⁻1) ∼ φ(x⁻1) ∼ x⁰ ∼ x¹ ∼ x² ∼ φ(z0) ∼ φ(y⁻1). As φ(C0) is a cycle, we have φ(x⁻1) = y0, φ(y⁻1) = z¹ and φ(z0) = y2.

Now consider the cycle C¹ : y⁰ ∼ x⁰ ∼ x¹ ∼ x² ∼ y² ∼ z¹ ∼ y0. Then φ(C1) : x⁻¹ ∼ x⁰ ∼ x¹ ∼ φ(x2) ∼ φ(y2) ∼ φ(z1) ∼ x⁻1. As φ(C1) is a cycle, we have φ(x2) = y1, φ(y2) = z⁰ and φ(z1) = y⁻1.

Proceeding in this way and considering the cycles Cⁱ : yi−¹ ∼ xi−¹ ∼ xⁱ ∼ xi+1 ∼ yi+1 ∼ zⁱ ∼ yi−1, for i = 2, · · · , n − 1, we get φ(Ci) : φ(yi−1) ∼ φ(xi−1) ∼ φ(xi) ∼ φ(xi+1) ∼ φ(yi+1) ∼ φ(zi) ∼ φ(yi−1). Thus, we have

φ(x12k) = x6k φ(y12k) = x6k−1 φ(z12k) = y6k+2
φ(x12k+1) = x6k+1 φ(y12k+1) = x6k+2 φ(z12k+1) = y6k−1
φ(x12k+2) = y6k+1 φ(y12k+2) = z6k φ(z12k+2) = x6k+3
φ(x12k+3) = z6k+2 φ(y12k+3) = y6k+3 φ(z12k+3) = z6k+m
φ(x12k+4) = z6k+2+m φ(y12k+4) = y6k+1+m φ(z12k+4) = z6k+4
φ(x12k+5) = y6k+3+m φ(y12k+5) = z6k+4+m φ(z12k+5) = x6k+1+m
φ(x12k+6) = x6k+3+m φ(y12k+6) = x6k+2+m φ(z12k+6) = y6k+5+m
φ(x12k+7) = x6k+4+m φ(y12k+7) = x6k+5+m φ(z12k+7) = y6k+2+m
φ(x12k+8) = y6k+4+m φ(y12k+8) = z6k+3+m φ(z12k+8) = x6k+6+m
φ(x12k+9) = z6k+5+m φ(y12k+9) = y6k+6+m φ(z12k+9) = z6k+3
φ(x12k+10) = z6k+5 φ(y12k+10) = y6k+4 φ(z12k+10) = z6k+7+m
φ(x12k+11) = y6k+6 φ(y12k+11) = z6k+7 φ(z12k+11) = x6k+4

As m is odd, m is either 6k + 1 or 6k + 3 or 6k + 5. Hence n = 12k + 2 or 12k + 6 or 12k + 10. If m = 6k + 1 then φ(x12k+2) = φ(x0), i.e., y6k+1 = x0, which is a contradiction. Thus φ(y0) ̸= x⁻¹ or φ(y1) ̸= x2.

If m = 6k + 5 then φ(x12k+10) = φ(x0), i.e., z6k+5 = x0, which is a contradiction. Thus φ(y0) ̸= x⁻¹ or φ(y1) ̸= x2.

Now let m = 6k + 3, consider y² ∼ z¹ ∼ z1+^m then φ(y2) = z⁰ ∼ φ(z1) = y⁻¹ ∼ φ(z1+m). If k = 2i is even, then z1+^m = z6k+4 = z12i+4 and hence φ(z1+m) = z6i+4. Therefore when k is even, we get 6i + 4 ≡ −2 (mod n), i.e., 6i + 6 ≡ 0 (mod n), i.e, 3k + 6 ≡ 0 (mod 12k + 6). This happens only when k = 0, i.e., m = 3.

On the other hand, if k = 2i + 1 is odd, then z1+^m = z12i+10 = z6i+7+m, hence φ(z1+m) = z6i+7+m. Thus when k is odd, we have 6i+7+m ≡ −2 (mod n), i.e, 9(k+1) ≡ 0 (mod 12k+6). This happens only when k = 1, i.e., m = 9.

Therefore we have if m is odd and m ̸= 3, 9, then there does not exists φ ∈ Stab(x0)∩Stab(x1) such that Case 1 holds.

Case 2. Let φ(y0) = y⁰ and φ(y1) = x2. As φ([x0, y0]) = [x0, y0], by Lemma 2.2, we have for m ̸= 3, φ ∈ H, i.e., φ = id.

Case 3. Let φ(y0) = x⁻¹ and φ(y1) = y1. As φ([x1, y1]) = [x1, y1], by Lemma 2.2, we have for m ̸= 3, φ ∈ H, i.e., φ = id.

Case 4. Let φ(y0) = y⁰ and φ(y1) = y1. Then φ maps consecutive spokes [x0, y0], [x1, y1] into Σ. Then by Lemma 2.3, we have φ ∈ H, i.e., φ = id.

Therefore combining all the 4 cases, we have the lemma.

Lemma 2.11. Let m is odd and m ̸= 3, 9, then

\[|\{\varphi \in Aut(\Gamma(m)) : \varphi(x_0) = x_0, \varphi(x_1) = x_{-1}\}| = 1.\]

Proof. The proof is similar to that of Lemma 2.10.

Lemma 2.12. Let m is odd and m ̸= 3, 9, then there does not exist any φ ∈ Aut(Γ(m)) such that φ(x0) = x⁰ and φ(x1) = y0.

Proof. Let φ(x0) = x⁰ and φ(x1) = y0. As φ(y0), φ(x⁻1) are adjacent to φ(x0); and φ(y1), φ(x2) are adjacent to φ(x1), then we have φ(y0), φ(x⁻1) ∈ {x1, x⁻1} and φ(y1), φ(x2) ∈ {z1, z⁻1}.

Case 1. Let φ(y0) = x¹ and φ(y1) = z1, then φ(x2) = z⁻1. Now consider the cycle C : y⁰ ∼ x⁰ ∼ x¹ ∼ x² ∼ y² ∼ z¹ ∼ y0. Then φ(C) : x¹ ∼ x⁰ ∼ y⁰ ∼ z⁻¹ ∼ φ(y2) ∼ φ(z1) ∼ x1. As φ(C) is a cycle, for m = 3 we have φ(y2) = z² and φ(z1) = y1, but for m ̸= 3, φ(C) is not a cycle, which is a contradiction.

Case 2. Let φ(y0) = x⁻¹ and φ(y1) = z⁻1, then φ(x2) = z1. This leads to a contradiction, as in previous case.

Case 3. Let φ(y0) = x¹ and φ(y1) = z⁻1. Then φ(x2) = z1. Consider the cycle C⁰ : y⁻¹ ∼ x⁻¹ ∼ x⁰ ∼ x¹ ∼ y¹ ∼ z⁰ ∼ y⁻1. Then φ(C0) : φ(y⁻1) ∼ φ(x⁻1) ∼ x⁰ ∼ y⁰ ∼ z⁻¹ ∼ φ(z0) ∼ φ(y⁻1). As φ(C0) is a cycle, we have φ(x⁻1) = x⁻1, φ(y⁻1) = x⁻² and φ(z0) = y⁻2.

Again consider the cycle C¹ : y⁰ ∼ x⁰ ∼ x¹ ∼ x² ∼ y² ∼ z¹ ∼ y0. Then φ(C1) : x¹ ∼ x⁰ ∼ y⁰ ∼ z¹ ∼ φ(y2) ∼ φ(z1) ∼ x1. As φ(C1) is a cycle, we have φ(y2) = y² and φ(z1) = x2.

Proceeding in this way and considering the cycles Cⁱ : yi−¹ ∼ xi−¹ ∼ xⁱ ∼ xi+1 ∼ yi+1 ∼ zⁱ ∼ yi−1, for i = 2, · · · , n − 1, we have φ(Ci) : φ(yi−1) ∼ φ(xi−1) ∼ φ(xi) ∼ φ(xi+1) ∼ φ(yi+1) ∼ φ(zi) ∼ φ(yi−1). Hence we get

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

As m is odd, m is either 6k + 1 or 6k + 3 or 6k + 5 and hence n = 12k + 2 or 12k + 6 or 12k + 10. If m = 6k + 1 then φ(x12k+2) = φ(x0), i.e., z6k+1 = x0, which is a contradiction. If m = 6k + 5 then φ(x12k+10) = φ(x0), i.e., y6k+5 = x0, which is a contradiction.

Now let m = 6k + 3. Consider z¹ ∼ z1+^m ∼ y2+m. Then applying φ, we get x² ∼ φ(z1+m) ∼ φ(y2+m).

If k = 2i is even, then y2+^m = y6k+5 = y12i+5 and z1+^m = z6k+4 = z12i+4. Hence φ(y2+m) = x6i+1+^m and φ(z1+m) = x6i+m. Therefore when k is even, x² ∼ x6i+^m ∼ x6i+1+m. Hence we have 6i+m ≡ 3 (mod n), i.e, 3k + 6k + 3 ≡ 3 (mod n), i.e., 9k ≡ 0 (mod 12k + 6). This happens only when k = 0, i.e., m = 3.

On the other hand, if k = 2i + 1 is odd, then y2+^m = y12i+11 and z1+^m = z12i+10. Hence φ(y2+m) = x6i+4 and φ(z1+m) = x6i+3. Thus when k is odd, we have x² ∼ x6i+3 ∼ x6i+4. This implies 6i + 3 ≡ 3 (mod n), i.e, 6i = 3(k − 1) ≡ 0 (mod 12k + 6). This happens only when k = 1, i.e., m = 9.

Therefore we have if m is odd and m ̸= 3, 9, then φ as in Case 3 does not exist.

Case 4. Let φ(y0) = x⁻¹ and φ(y1) = z1. In this case also, it can be shown, similarly as in Case 3, that such a φ does not exist.

Therefore combining all 4 cases, the lemma follows.

Theorem 2.4. If m is odd and m ̸= 3, 9, then Aut(Γ(m)) = ⟨ρ, τ, σ⟩.

Proof. It was already noted that ⟨ρ, τ, σ⟩ is a subgroup of Aut(Γ(m)) of order 6n. Moreover, as m is odd by the Lemma 2.1, we have Γ(m) is Cayley and hence vertex-transitive. Thus, by orbit-stabilizer theorem, we have

\[\frac{|Aut(\Gamma(m))|}{|\mathsf{Stab}(x_0)|} = |\Gamma(m)| = 3n, \text{ i.e., } |Aut(\Gamma(m))| = 3n \cdot |\mathsf{Stab}(x_0)|.\]

Thus, to prove the theorem, it suffices to show that |Stab(x0)| = 2.

It is clear that id, τ ∈ Stab(x0). Let φ ∈ Stab(x0). As x⁰ ∼ x1, therefore φ(x1) = x¹ or x⁻¹ or y0. If φ(x1) = x1, by Lemma 2.10, φ = id. If φ(x1) = x⁻1, then by Lemma 2.11, φ = τ . And finally, Lemma 2.12 shows that no φ exists such that φ(x1) = y0. Hence, Stab(x0) = {id, τ} and the theorem follows.

We now note a few automorphisms which occurs only when m = 3 or 9. Define

\[\eta=(x_4,y_5)(z_1,z_5)(x_2,y_1)(y_3,z_3)(y_4,z_4)(x_3,z_0)(y_2,z_2)\] and

\[\varepsilon_i = (x_{6i+3}, z_{6i+4}, z_{6i-4})(x_{6i+2}, y_{6i-1}, z_{6i-1})(x_{6i-2}, y_{6i+1}, z_{6i+1})(x_{6i+1}, x_{6i-1}, y_{6i})(y_{6i+2}, y_{6i-2}, z_{6i}).\]

It can be shown that η, ε⁰ ∈ Aut(Γ(3)) and ζ = ε0ε1ε² · (z3, z9, z15) · (y3, y9, y15) ∈ Aut(Γ(9)). Moreover, it was checked using SageMath [6] that

\[Aut(\Gamma(3)) = \langle \rho, \tau, \sigma, \eta, \varepsilon_0 \rangle\] and \(Aut(\Gamma(3)) = \langle \rho, \tau, \sigma, \zeta \rangle\).

Thus, summarizing all the cases, i.e., Theorem 2.3, Theorem 2.4 and the above discussion, we get the following theorem.

Theorem 2.5. Let m ≥ 3 and Γ(m) be the Generalized Pappus graph. Then

\[Aut(\Gamma(m)) = \begin{cases} \langle \rho, \tau \rangle, & \text{if $m$ is even,} \\ \langle \rho, \tau, \sigma \rangle, & \text{if $m$ is odd and $m \neq 3,9$,} \\ \langle \rho, \tau, \sigma, \zeta \rangle, & \text{if $m = 9$,} \\ \langle \rho, \tau, \sigma, \eta, \varepsilon_0 \rangle, & \text{if $m = 3$.} \end{cases}\]

Corollary 2.3. The following are true:

• 1. Γ(3) and Γ(9) are arc-transitive.
• 2. For m ̸= 3, 9, Γ(m) is not edge-transitive.
• 3. Γ(m) is Cayley if and only if m is odd.

Proof. The arc-transitivity of Γ(3) and Γ(9) can be easily checked in SageMath [6]. As Γ(m) has 9m edges, in order that Γ(m) is edge-transitive, the order of Aut(Γ(m)) must be a multiple of 9m. However, if m ̸= 3, 9, the order of Aut(Γ(m)) is either 4m or 12m depending upon whether m is even or odd. Thus the second statement holds.

For the last statement, the sufficiency is proved in Theorem 2.1. For the necessity, the order of a vertex-transitive graph should divide the order of its automorphism group. However, if m is even, then |Γ(m)| = 6m < 4m = |Aut(Γ(m))|.

3. Open Issues

Another thing which is very much related to graphs with large symmetry groups, is its hamiltonicity, viz, Lovasz' conjecture. Our observation based on first few values of m, made us to strongly believe that Γ(m) is Hamiltonian for all value of m ≥ 3. This can be an interesting topic for further research.

Acknowledgement

The first author is supported by the PhD fellowship of CSIR (File no. 08/155(0086)/2020 − EMR − I), Govt. of India. The second author acknowledges the funding of DST grants no. SRG/2019/000475 and SR/F ST/MS − I/2019/41, Govt. of India.

References

• [1] A. Devillers, M. Giudici, C.H. Li, and C.E. Praeger, An infinite family of biquasiprimitive 2-arc transitive cubic graphs, Journal of Algebraic Combinatorics, 35 (2021), 173–192.
• [2] R. Frucht, J.E. Graver, and M.E. Watkins, The groups of the generalized Petersen graphs, Proceedings of the Cambridge Philosophical Society, 70 (2) (1971), 211–218.
• [3] C. Godsil, and G.F. Royle, Algebraic Graph Theory, Graduate Texts in Mathematics, 207, Springer-Verlag, 2001.
• [4] D. Koreas, Some bound of the edge chromatic surplus of certain cubic graphs, Electron. J. Graph Theory Appl., 6 (2) (2018), 310–316.
• [5] K. Kutnar and P. Petecki, On automorphisms and structural properties of double generalized Petersen graphs, Discrete Math., 339 (2016), 2861–2870.
• [6] W. Stein and others, Sage Mathematics Software (Version 7.3), Release Date: 04.08.2016, http://www.sagemath.org.
• [7] M.J. Stroppel, Generalizing the Pappus and Reye configurations, Australas. J. Combin., 72 (2) (2018), 249–272.
• [8] J.X. Zhou and M. Ghasemi, Automorphisms of a family of cubic graphs, Algebra Colloquium, 20 (3) (2013), 495–506.
• [9] J.X. Zhou and Yan-Tao Li, Cubic non-normal Cayley graphs of order 4p 2 , Discrete Math. 312 (2012), 1940–1946, doi:10.1016/j.disc.2012.03.012.