Perfect matching transitivity of circulant graphs

Isaac A. Reiter, Ju Zhou

Kutztown University of Pennsylvania, Kutztown, PA

ireit426@live.kutztown.edu, zhou@kutztown.edu

A graph G is perfect matching transitive, shortly PM-transitive, if for any two perfect matchings M¹ and M² of G, there is an automorphism f : V (G) 7→ V (G) such that fe(M1) = M2, where fe(uv) = f(u)f(v). In this paper, the authors completely characterize the perfect matching transitivity of circulant graphs of order less than or equal to 10.

Keywords: automorphism, vertex-transitive, edge-transitive, perfect matching, perfect matching transitivity, PM-transitive, circulant graph.

Mathematics Subject Classification: 05C60

DOI: 10.5614/ejgta.2022.10.2.14

1. Introduction

An automorphism of a graph is a form of symmetry in which the graph is mapped onto itself while preserving the edge-vertex connectivity. Formally, an automorphism of a graph G = (V (G), E(G)) is a permutation f of the vertex set V (G) such that the pair of vertices uv is an edge of G if and only if f(u)f(v) is also an edge of G. In other words, it is a graph isomorphism from G to itself. Every graph automorphism f induces a mapping f^e : E(G) 7→ E(G) such that fe(uv) = f(u)f(v). For any vertex set X ⊆ V (G) and edge set M ⊆ E(G), denote f(X) = {f(v) : v ∈ X} and fe(M) = {fe(uv) : uv ∈ M}.

A graph G is vertex-transitive [11] if for any two given vertices v¹ and v² of G, there is an automorphism f : V (G) 7→ V (G) such that f(v1) = v2. In other words, a graph is vertextransitive if its automorphism group acts transitively upon its vertices. A graph is vertex-transitive if and only if its complement graph is vertex-transitive (since the group actions are identical). For example, the finite Cayley graphs, the Petersen graph, and Cn×K² with n ≥ 3 are vertex-transitive.

Received: 1 April 2022, Revised: 17 June 2022, Accepted: 26 September 2022.

A graph G is edge-transitive if for any two given edges e¹ and e² of G, there is an automorphism of G that maps e¹ to e2. In other words, a graph is edge-transitive if its automorphism group acts transitively upon its edges. The complete bipartite graph Km,n, the Petersen graph, and the cubical graph Cⁿ × K² with n = 4 are edge-transitive.

A graph G is symmetric or arc-transitive if for any two pairs of adjacent vertices u1v¹ and u2v² of G, there is an automorphism f : V (G) 7→ V (G) such that f(u1) = u² and f(v1) = v2. In other words, a graph is symmetric if its automorphism group acts transitively upon ordered pairs of adjacent vertices, that is, upon edges considered as having a direction. The cubical graph Cⁿ × K² with n = 4 and Petersen graph are symmetric graphs.

Every connected symmetric graph must be both vertex-transitive and edge-transitive, and the converse is true for graphs of odd degree [2]. However, for graphs of even degree, there exist connected graphs which are vertex-transitive and edge-transitive, but not symmetric [3]. Every symmetric graph without isolated vertices is vertex-transitive, and every vertex-transitive graph is regular. However, not all vertex-transitive graphs are symmetric (for example, the edges of the truncated tetrahedron), and not all regular graphs are vertex-transitive (for example, the Frucht graph and Tietze's graph).

A lot of work has been done about the relationship between vertex-transitive graphs and edgetransitive graphs. Some of the related results can be found in [3]-[17]. In general, edge-transitive graphs need not be vertex-transitive. The Gray graph is an example of a graph which is edgetransitive but not vertex-transitive. Conversely, vertex-transitive graphs need not be edge-transitive. The graph Cⁿ × K2, where n ≥ 5 is vertex-transitive but not edge-transitive.

A graph G is perfect matching transitive, shortly PM-transitive, if for any two perfect matchings M¹ and M² of G, there is an automorphism f : V (G) 7→ V (G) such that fe(M1) = M2, where f^e is the mapping induced by f.

In [18], the author (Zhou) verified that some well known symmetric graphs such as C2n, K2n, Kn,n, and the Petersen graph are PM-transitive, constructed several families of PM-transitive graphs which are neither vertex-transitive nor edge-transitive, discussed some methods to generate new PM-transitive graphs, and proved that all the generated Petersen graphs except the Petersen graph are non-perfect matching transitive.

A circulant graph is a graph of n vertices v1, v2, . . . , vⁿ in which the ith vertex is adjacent to the (i+j)th and (i−j)th vertices for each j in a list l, where the addition and subtraction are taken by modulo n. In Section 2, the authors prove a collection of general results about the PM-transitivity of connected circulant graphs of even order n ≥ 4. In Section 3, the authors characterize the PM-transitivity of connected circulant graphs of order 6. In Section 4, the authors characterize the PM-transitivity of connected circulant graphs of order 8. In Section 5, the authors characterize the PM-transitivity of connected circulant graphs of order 10.

2. PM-transitivity of Connected Circulant Graphs of Order 2n

For any integer n ≥ 2, the circulant graph Ci2n(1, 2, . . . , n) gives the complete graph K2n, the circulant graph Ci2n(1) gives the cyclic graph C2n, and the circulant graph Ci2n(1, 3, 5, . . . , m), where m represents the largest odd integer less than or equal to n, gives the complete bipartite graph Kn,n. The following Theorem 2.1 is proven in [18].

Theorem 2.1. For any integer n ≥ 2, the circulant graphs Ci2n(1, 2, ..., n) ∼= K2n, Ci2n(1) ∼= C2n, and Ci2n(1, 3, 5, . . . , m) ∼= Kn,n, where m represents the largest odd integer that is less than or equal to n, are PM-transitive.

Theorem 2.2. For any integer n ≥ 4, the circulant graph Ci2n(1, 2) is not PM-transitive.

Proof. Let M¹ = {v1v3, v2v2n, v4v5, v6v7, v8v9, . . . , v2n−2v2n−1} and M² = {v1v2, v3v4, v5v6, . . . , v2n−1v2n}. Then M¹ and M² are two perfect matchings of G such that G − M¹ has 3-cycles (v2v3v4v² being one such 3-cycle) while G − M² ∼= Cⁿ × K² doesn't have 3-cycles. Therefore, G is not PM-transitive.

Theorem 2.3. For any integer n ≥ 4, the circulant graph Ci2n(1, n) is not PM-transitive.

Proof. Let M¹ = {v1vn+1, v2vn+2, . . . , vnv2n}. If n = 4, then let M² = {v8v1, v2v3, v4v5, v6v7}. Otherwise, let M² = {v2nv1, v2v3, vnvn+1, vn+2vn+3, v4vn+4, v5vn+5, . . . , vn−1v2n−1}. Then M¹ and M² are two perfect matchings of G such that G − M¹ is a 2n-cycle and G − M² is a union of a 4-cycle v1v2vn+2vn+1v¹ and a (2n − 4)-cycle v3v4v⁵ · · · vnv2nv2n−1v2n−² · · · vn+3v3. Therefore, Ci2n(1, n) is not PM-transitive.

In this paper's proofs, the authors shall frequently use the phrase "without loss of generality, let f(v1) = v1." The following lemma justifies why we can make this assumption. We will define a perfect matching M of a circulant graph G to be vertex-perfect-matching transitive if for any two given vertices vⁱ and v^j of G, there is an automorphism f : V (G) 7→ V (G) such that f(vi) = v^j and fe(M) = M.

Lemma 2.1. Let G be a circulant graph of order 2n, n ≥ 2. Let M¹ and M² be two perfect matchings of G such that either M¹ or M² is vertex-perfect-matching transitive. If f is an automorphism f : V (G) 7→ V (G) such that fe(M1) = M2, then we may assume without loss of generality that f(v1) = v1.

Proof. Let f : V (G) 7→ V (G) be an automorphism of G such that fe(M1) = M2.

If M¹ is vertex-perfect-matching transitive, let vⁱ be the vertex such that f(vi) = v1. Since M¹ is vertex-perfect-matching transitive, there exists an automorphism g : V (G) 7→ V (G) such that g(v1) = vⁱ and ge(M1) = M1. Now, we define h = f ◦ g, implying that h is an automorphism such that h(v1) = v¹ and he(M1) = M2.

If M² is vertex-perfect-matching transitive, let vⁱ be the vertex such that f(v1) = vⁱ . Since M² is vertex-perfect-matching transitive, there exists an automorphism g : V (G) 7→ V (G) such that g(vi) = v¹ and ge(M2) = M2. Now, we define h = g ◦ f, implying that h is an automorphism such that h(v1) = v¹ and he(M1) = M2.

In other words, any automorphism f : V (G) 7→ V (G) such that fe(M1) = M² induces an automorphism h : V (G) 7→ V (G) such that h(v1) = v¹ and he(M1) = M2. Thus, we may assume without loss of generality that f(v1) = v1.

Lemma 2.2. Let G be a circulant graph of order 2n, n ≥ 2.

• (1) If G contains the perfect matching M¹ = {v1vn+1, v2vn+2, v3vn+3, . . . , vnv2n}, then M¹ is vertex-perfect-matching transitive.
• (2) If G contains the perfect matching M² = {v1v2, v3v4, v5v6, . . . , v2n−1v2n}, then M² is vertex-perfect-matching transitive.

Proof. First, consider G with M1. Let vⁱ , v^j ∈ V (G), and define δ¹ = j−i. Let f : V (G) 7→ V (G) such that f(vm) = vm+δ¹ for all 1 ≤ m ≤ 2n. Then f is a rotation of G, and f is an automorphism such that f(vi) = v^j and fe(M) = M. Thus, M¹ is vertex-perfect-matching transitive, and (1) is proven.

Second, consider G with M2. Let vⁱ , v^j ∈ V (G), and define δ² = j − i. If δ² is even, then let g : V (G) 7→ V (G) such that g(vm) = vm+δ² for all 1 ≤ m ≤ 2n. Then g is a rotation of G. It is the case that g is an automorphism such that g(vi) = v^j and ge(M) = M.

If δ² is odd, then let h¹ : V (G) 7→ V (G) such that h1(vp) = v2n+1−^p for all 1 ≤ p ≤ 2n. Then h¹ is a reflection of G, and h¹ is an automorphism. Also, h¹ maps odd-indexed vertices to evenindexed vertices and even-indexed vertices to odd-indexed vertices. Let v^k = h1(vi) and define δ³ = j − k. Since h¹ switches the parity of all vertices, δ³ is even. Let h² : V (G) 7→ V (G) such that h2(vp) = vp+δ³ for all 1 ≤ p ≤ 2n. Then h² is a rotation of G, and h² is an automorphism. Let h : V (G) 7→ V (G) such that h = h² ◦ h1. Then h is an automorphism such that h(vi) = v^j . Furthermore, let vxvx+1 ∈ M. Then h maps this edge to v2n+1−x+δ³ v2n+1−x−1+δ³ . Since δ³ is even and x is odd, 2n + 1 − x − 1 + δ³ is odd. Thus, v2n+1−x+δ³ v2n+1−x−1+δ³ ∈ M. Since h is bijective, it maps each edge in M to a unique edge in M. This implies that he(M) = M. Thus, M² is vertex-perfect-matching transitive, and (2) is proven.

The condition of Lemma 2.1 is that one of the perfect matchings is vertex-perfect-matching transitive. Thus, whenever Lemma 2.1 is invoked, one of the perfect matchings in Lemma 2.2 will be present.

Theorem 2.4. For any odd integer n ≥ 5, the circulant graph Ci2n(1, 2, 3, . . . , n − 1) is not PM-transitive.

Proof. If n is odd, let M¹ = {v1v2, v3v4, v5v6, . . . , v2n−1v2n} and M² = {vn+1vn+2, vnvn+3} ∪ (M1\{vnvn+1, vn+2vn+3}). M¹ and M² are two perfect matchings of G. Suppose f is an automorphism f : V (G) 7→ V (G) such that fe(M1) = M2. By Lemma 2.1, we can assume, without loss of generality, that f(v1) = v1. Since v1v² ∈ M2, this implies that f(v2) = v2. Since v1vn+1 ∈/ E(G), f(v1)f(vn+1) = v1f(vn+1) ∈/ E(G). Since vn+1 is the only vertex not adjacent to v1, f(vn+1) = vn+1. Similarly, v2vn+2 ∈/ E(G) implies that f(v2)f(vn+2) = v2f(vn+2) ∈/ E(G). Since vn+2 is the only vertex not adjacent to v2, f(vn+2) = vn+2. Notice that vn+1vn+2 ∈/ M¹ but f(vn+1)f(vn+2) = vn+1vn+2 ∈ M2, contradicting fe(M1) = M2. Thus, G is not PMtransitive.

3. PM-transitivity of Connected Circulant Graphs of Order 6

In this section, we characterize the PM-transitivity of connected circulant graphs of order 6. The circulant graphs of order 6 include Ci6(1), Ci6(2), Ci6(3), Ci6(1, 2), Ci6(1, 3), Ci6(2, 3), and Ci6(1, 2, 3), where Ci6(2) and Ci6(3) are disconnected.

Theorem 3.1. If G is a connected PM-transitive circulant graph of order 6, then G is congruent to Ci6(1), Ci6(1, 2), Ci6(1, 3), or Ci6(1, 2, 3).

Proof. If \(G \cong Ci_6(1) = C_6\), \(G \cong Ci_6(1,3) = K_{3,3}\), or \(G \cong Ci_6(1,2,3) = K_6\), then G is PM-transitive by Theorem 2.1. We just need to consider the following two cases.

Case 1. \(G \cong Ci_6(1,2)\) is PM-transitive.

Define \(\{v_1v_2, v_2v_3, v_3v_4, v_4v_5, v_5v_6, v_6v_1\}\) to be the outer edges and all other edges to be the inner edges. Let M be a perfect matching of G. Notice that the six inner edges form two \(C_3\) subgraphs. If M contains three inner edges, then one of these subgraphs will have two edges in M. This results in one vertex being covered twice, a contradiction. Thus, M must contain at least one outer edge.

Without loss of generality, let \(v_5v_6 \in M\). To cover the remaining vertices, either \(v_1v_2, v_3v_4 \in M\) or \(v_1v_3, v_2v_4 \in M\). Let \(M_1 = \{v_1v_2, v_3v_4, v_5v_6\}\) and \(M_2 = \{v_1v_3, v_2v_4, v_5v_6\}\).

Now, it simply remains to find an automorphism that maps \(M_1\) to \(M_2\). Let \(f:V(G)\to V(G)\) such that \(f(v_1)=v_1\), \(f(v_2)=v_3\), \(f(v_3)=v_2\), \(f(v_4)=v_4\), \(f(v_5)=v_6\), and \(f(v_6)=v_5\). Then f is an automorphism such that \(f_e(M_1)=M_2\). Thus, G is PM-transitive.

Case 2. \(G \cong Ci_6(2,3)\) is not PM-transitive.

Let \(M_1 = \{v_1v_4, v_2v_5, v_3v_6\}\) and \(M_2 = \{v_1v_5, v_2v_4, v_3v_6\}\). Then \(M_1\) and \(M_2\) are two perfect matchings of G such that \(G - M_1\) is a union of two 3-cycles while \(G - M_2\) is a 6-cycle. Therefore, G is not PM-transitive.

In summary, the connected PM-transitive circulant graphs of order 6 are congruent to \(Ci_6(1)\), \(Ci_6(1,2)\), \(Ci_6(1,3)\), or \(Ci_6(1,2,3)\). In other words, they are congruent to \(C_6\), \(K_{2,2,2}\), \(K_{3,3}\), or \(K_6\).

4. PM-transitivity of Connected Circulant Graphs of Order 8

In this section, we characterize the PM-transitivity of connected circulant graphs of order 8. The circulant graphs of order 8 include \(Ci_8(1)\), \(Ci_8(2)\), \(Ci_8(3)\), \(Ci_8(4)\), \(Ci_8(1,2)\), \(Ci_8(1,3)\), \(Ci_8(1,4)\), \(Ci_8(2,3)\), \(Ci_8(2,4)\), \(Ci_8(3,4)\), \(Ci_8(1,2,3)\), \(Ci_8(1,2,4)\), \(Ci_8(1,3,4)\), \(Ci_8(2,3,4)\), and \(Ci_8(1,2,3,4)\), where \(Ci_8(2)\), \(Ci_8(4)\) and \(Ci_8(2,4)\) are disconnected. Furthermore, Theorem 4.1 contains 4 statements of congruence that reduce the number of cases needed to prove Theorem 4.2.

Theorem 4.1. For the connected circulant graph or order 8, the following congruence statements hold.

• (1) \(Ci_8(1) \cong Ci_8(3)\)
• (2) \(Ci_8(1,2) \cong Ci_8(2,3)\)
• (3) \(Ci_8(1,4) \cong Ci_8(3,4)\)
• (4) \(Ci_8(1,2,4) \cong Ci_8(2,3,4)\)

Proof. To prove each congruence statement, it is sufficient to define an automorphism f from the vertices of the first graph to the vertices of the second graph.

Let f be defined such that \(f(v_1) = v_1\), \(f(v_2) = v_4\), \(f(v_3) = v_7\), \(f(v_4) = v_2\), \(f(v_5) = v_5\), \(f(v_6) = v_8\), \(f(v_7) = v_3\), and \(f(v_8) = v_6\). For each of the 4 congruence statements, f is an automorphism that maps the vertices of the graph on the left side to the vertices of the graph on the right side.

Theorem 4.2. If G is a connected PM-transitive circulant graph of order 8, then G is congruent to \(Ci_8(1)\), \(Ci_8(1,3)\), or \(Ci_8(1,2,3,4)\).

Proof. If \(G \cong Ci_8(1) \cong C_8\), \(G \cong Ci_8(1,3) \cong K_{4,4}\) or \(G \cong Ci_8(1,2,3,4) \cong K_8\), then G is PM-transitive by Theorem 2.1. If \(G \cong Ci_8(1,2)\), then G is not PM-transitive by Theorem 2.2. If \(G \cong Ci_8(1,4) \cong Ci_8(3,4)\), then G is not PM-transitive by Theorem 2.3. We just need to consider the following three cases.

Case 1. \(C \cong Ci_8(1,2,3)\) is not PM-transitive.

Let \(M_1 = \{v_1v_2, v_3v_4, v_5v_6, v_7v_8\}\) and \(M_2 = \{v_1v_2, v_3v_4, v_5v_8, v_6v_7\}\). Then \(M_1\) and \(M_2\) are two perfect matchings of G. Suppose that f is an automorphism \(f: V(G) \to V(G)\) such that \(f_e(M_1) = M_2\). Without loss of generality, let \(f(v_1) = v_1\). This forces \(f(v_2) = v_2\).

Consider \(v_8\). Since \(v_8\) is adjacent to \(v_1\) and \(v_2\), \(f(v_8)\) cannot be \(v_5\) or \(v_6\). If \(f(v_8) = v_3\), then this forces \(f(v_5) = v_4\). Now \(v_1v_5 \notin E(G)\) and \(v_1v_4 \in E(G)\), contradicting the supposition that f is an automorphism. If \(f(v_8) = v_4\), then this forces \(f(v_5) = v_3\). Now \(v_1v_5 \notin E(G)\) and \(v_1v_3 \in E(G)\), a contradiction. If \(f(v_8) = v_7\), then this forces \(f(v_5) = v_8\). Now \(v_1v_5 \notin E(G)\) and \(v_1v_8 \in E(G)\), a contradiction. If \(f(v_8) = v_8\), then this forces \(f(v_5) = v_7\). Now \(v_1v_5 \notin E(G)\) and \(v_1v_7 \in E(G)\), a contradiction. Therefore, G is not PM-transitive.

Case 2. \(G \cong Ci_8(1,2,4)\) is not PM-transitive.

Let \(M_1 = \{v_1v_3, v_2v_8, v_4v_6, v_5v_7\}\) and \(M_2 = \{v_1v_5, v_2v_6, v_3v_7, v_4v_8\}\). Then \(M_1\) and \(M_2\) are two perfect matchings of G such that \(G - M_1\) has four 3-cycles while \(G - M_2 \cong Ci_8(1,2)\) has eight 3-cycles. Therefore, G is not PM-transitive.

Case 3. \(G \cong Ci_8(1,3,4)\) is not PM-transitive.

Let \(M_1 = \{v_1v_2, v_3v_4, v_5v_6, v_7v_8\}\) and \(M_2 = \{v_1v_5, v_2v_6, v_3v_7, v_4v_8\}\). Then \(M_1\) and \(M_2\) are two perfect matchings of G such that \(G - M_1\) has 3-cycles while \(G - M_2 \cong Ci_8(1,3) \cong K_{4,4}\) doesn't have 3-cycles. Therefore, G is not PM-transitive.

In summary, the connected PM-transitive circulant graphs of order 8 are congruent to \(Ci_8(1)\), \(Ci_8(1,3)\), or \(Ci_8(1,2,3,4)\). In other words, the connected PM-transitive circulant graphs of order 8 are congruent to \(C_8\), \(K_{4,4}\), or \(K_8\).

5. PM-transitivity of Connected Circulant Graphs of Order 10

In this section, we characterize the PM-transitivity of connected circulant graphs of order 10. The circulant graphs of order 10 include \(Ci_{10}(1)\), \(Ci_{10}(2)\), \(Ci_{10}(3)\), \(Ci_{10}(4)\), \(Ci_{10}(5)\), \(Ci_{10}(1,2)\), \(Ci_{10}(1,3)\), \(Ci_{10}(1,4)\), \(Ci_{10}(1,5)\), \(Ci_{10}(2,3)\), \(Ci_{10}(2,4)\), \(Ci_{10}(2,5)\), \(Ci_{10}(3,4)\), \(Ci_{10}(3,5)\), \(Ci_{10}(4,5)\), \(Ci_{10}(1,2,3)\), \(Ci_{10}(1,2,4)\), \(Ci_{10}(1,2,5)\), \(Ci_{10}(1,3,4)\), \(Ci_{10}(1,3,5)\), \(Ci_{10}(1,4,5)\), \(Ci_{10}(2,3,4)\), \(Ci_{10}(2,3,5)\), \(Ci_{10}(2,4,5)\), \(Ci_{10}(3,4,5)\), \(Ci_{10}(1,2,3,4)\), \(Ci_{10}(1,2,3,5)\), \(Ci_{10}(1,2,4,5)\), \(Ci_{10}(1,3,4,5)\), \(Ci_{10}(2,3,4,5)\), and \(Ci_{10}(1,2,3,4,5)\), where \(Ci_{10}(2)\), \(Ci_{10}(4)\), \(Ci_{10}(2,4)\), \(Ci_{10}(5)\) are disconnected. Furthermore, Theorem 5.1 contains 10 statements of congruence that reduce the number of cases needed to prove Theorem 5.2.

Theorem 5.1. For the connected circulant graph of order 10, the following congruence statements hold.

• (1) \(Ci_{10}(1,2) \cong Ci_{10}(3,4)\)
• (2) \(Ci_{10}(1,4) \cong Ci_{10}(2,3)\)
• (3) \(Ci_{10}(2,5) \cong Ci_{10}(4,5)\)
• (4) \(Ci_{10}(1,5) \cong Ci_{10}(3,5)\)

\((5) Ci_{10}(1,2,3) \cong Ci_{10}(1,3,4)\) \((6) Ci_{10}(1,2,4) \cong Ci_{10}(2,3,4)\) \((7) Ci_{10}(1,2,5) \cong Ci_{10}(3,4,5)\) \((8) Ci_{10}(1,4,5) \cong Ci_{10}(2,3,5)\) \((9) Ci_{10}(1,2,4,5) \cong Ci_{10}(2,3,4,5)\) \((10) Ci_{10}(1,2,3,5) \cong Ci_{10}(1,3,4,5).\)

Proof. To prove each congruence statement, it is sufficient to define an automorphism f from the vertices of the first graph to the vertices of the second graph.

Let f be defined such that \(f(v_1) = v_1\), \(f(v_2) = v_4\), \(f(v_3) = v_7\), \(f(v_4) = v_{10}\), \(f(v_5) = v_3\), \(f(v_6) = v_6\), \(f(v_7) = v_9\), \(f(v_8) = v_2\), \(f(v_9) = v_5\), and \(f(v_{10}) = v_8\). For each of the 10 congruence statements, f is an automorphism that maps the vertices of the graph on the left side to the vertices of the graph on the right side.

Theorem 5.2. If G is a connected PM-transitive circulant graph of order 10, then G is congruent to \(Ci_{10}(1)\), \(Ci_{10}(1,4)\), \(Ci_{10}(1,3,5)\), or \(Ci_{10}(1,2,3,4,5)\).

Proof. If \(G \cong Ci_{10}(1) \cong Ci_{10}(3) \cong C_{10}\), \(G \cong Ci_{10}(1,3,5) \cong K_{5,5}\), or \(G \cong Ci_{10}(1,2,3,4,5) \cong K_{10}\), then G is PM-transitive by Theorem 2.1. If \(G \cong Ci_{10}(1,2)\), then G is not PM-transitive by Theorem 2.2. If \(G \cong Ci_{10}(1,5) \cong Ci_{10}(3,5)\), then G is not PM-transitive by Theorem 2.3. If \(G \cong Ci_{10}(1,2,3,4) \cong K_{2,2,2,2,2}\), then G is not PM-transitive by Theorem 2.4. We just need to distinguish the following ten cases.

Case 1. \(G \cong Ci_{10}(1,3)\) is not PM-transitive.

Let \(M_1 = \{v_1v_2, v_3v_4, v_5v_6, v_7v_8, v_9v_{10}\}\) and \(M_2 = \{v_1v_2, v_3v_{10}, v_4v_7, v_5v_8, v_6v_9\}\). Then \(M_1\) and \(M_2\) are two perfect matchings of G.

Let \(G_1\) be the graph formed by identifying the vertices in each edge of \(M_1\). In other words, \(G_1\) is the graph formed by identifying \(v_1\) with \(v_2\), \(v_3\) with \(v_4\), \(v_5\) with \(v_6\), \(v_7\) with \(v_8\), and \(v_9\) with \(v_{10}\). Similarly, let \(G_2\) be the graph formed by identifying the vertices in each edge of \(M_2\). Notice that \(G_1\) is \(K_5\) and that \(G_2\) is \(K_5\) minus an edge. Therefore, \(G_1\) is not PM-transitive.

Case 2. \(G \cong Ci_{10}(1,4)\) is PM-transitive.

Consider the following four perfect matchings: \(M_1 = \{v_1v_2, v_3v_4, v_5v_6, v_7v_8, v_9v_{10}\}\), \(M_2 = \{v_1v_2, v_5v_6, v_8v_9, v_3v_7, v_4v_{10}\}\), \(M_3 = \{v_1v_2, v_5v_6, v_7v_8, v_3v_9, v_4v_{10}\}\), and \(M_4 = \{v_1v_2, v_3v_7, v_4v_8, v_5v_9, v_6v_{10}\}\). We shall show that every perfect matching M of G is automorphic to one of these perfect matchings. To show this, we shall define \(\{v_{10}v_1, v_1v_2, v_2v_3, v_3v_4, v_4v_5, v_5v_6, v_6v_7, v_7v_8, v_8v_9, v_9v_{10}\}\) to be the outer edges and all other edges to be the inner edges.

If M contains no inner edges, then \(M = M_1\) or \(M = \{v_{10}v_1, v_2v_3, v_4v_5, v_6v_7, v_8v_9\}\). It is easy to see that M is automorphic to \(M_1\).

In the following, we assume that M contains at least one inner edge. Without loss of generality, let \(v_4v_{10} \in M\). Notice that \(v_1\), \(v_2\), and \(v_3\) cannot be covered by only using outer edges in M. Thus, M has at least two inner edges.

If M has exactly two inner edges, then not all of \(v_1, v_2, v_3\) can be covered by inner edges. Without loss of generality, let \(v_1v_2 \in M\). To cover \(v_3\), either \(v_3v_7 \in M\) or \(v_3v_9 \in M\). If the former is true, then \(v_8v_9, v_5v_6 \in M\). Now, M is automorphic to \(M_2\). If the latter is true, then \(v_7v_8, v_5v_6 \in M\). Now, M is automorphic to \(M_3\).

Suppose that M has exactly three inner edges. If neither v1v² nor v2v³ are in M, then three more inner edges are needed to cover {v1, v2, v3}, a contradiction. Thus, without loss of generality let v1v² ∈ M. To cover v5, either v5v⁶ ∈ M or v5v⁹ ∈ M. If the former is true, then {v3, v7, v8, v9} cannot be covered by two inner edges in M. If the latter is true, then v3v⁷ ∈ M in order to cover v3. Now, v⁶ and v⁸ cannot be covered by an outer edge in M, a contradiction. Thus, M cannot have three inner edges.

If M has exactly four inner edges, then consider the following. Suppose that the single outer edge in M is v1v2. Now, there is no inner edge that can cover v8. Thus, by symmetry v1v² ∈/ M and v2v³ ∈/ M. If the single outer edge in M is v8v9, then v3v⁷ ∈ M to cover v3. To cover v2, v2v⁶ ∈ M. To cover v1, v1v⁵ ∈ M. Now, M is automorphic to M4. By symmetry, if the single outer edge in M is v5v⁶ then M is automorphic to M4. If the single outer edge is v7v8, then v3v⁹ ∈ M to cover v3. To cover v2, v2v⁶ ∈ M. To cover v1, v1v⁵ ∈ M. Now, M is automorphic to M4. By symmetry, if the single outer edge in M is v6v⁷ then M is automorphic to M4.

Suppose M has five inner edges. To cover v3, either v3v⁷ ∈ M or v3v⁹ ∈ M. If the former is true, then v5v⁹ ∈ M to cover v9. To cover v8, v2v⁸ ∈ M. No edge covers both v¹ and v6, a contradiction. If the latter is true, then v2v⁸ ∈ M to cover v8. To cover v7, v1v⁷ ∈ M. Now, v⁵ and v⁶ cannot be covered by an inner edge, a contradiction. Thus, M cannot have five inner edges.

Table 1. f, g, and h are automorphisms

Now we prove that M¹ is automorphic to M2, M3, and M4, respectively. For M¹ and M2, we define f : V (G) → V (G) such that f(vi) = vⁱ if i = 1, 2, 5, 6, 7, 10, f(v3) = v8, f(v4) = v9,

f(v8) = v3, and f(v9) = v4. To prove that f is an automorphism, Table 1 shows that f preserves all 20 edges (the edges in the second column form E(G)). Also, f maps M¹ to M2, that is, fe(M1) = M2.

For M¹ and M3, we define g : V (G) → V (G) such that g(vi) = vⁱ if i = 1, 2, 3, 5, 6, 7, 8, 10, g(v4) = v9, and g(v9) = v4. To prove that g is an automorphism, Table 1 shows that g preserves all 20 edges (the edges in the third column form E(G)). Also, g maps M¹ to M3, that is, ge(M1) = M3.

For M¹ and M4, we define h : V (G) → V (G) such that h(vi) = vⁱ if i = 1, 2, 4, 6, 7, 9, h(v3) = v8, h(v5) = v10, h(v8) = v3, and h(v10) = v5. To prove that h is an automorphism, Table 1 shows that h preserves all 20 edges (the edges in the third column form E(G)). Also, h maps M¹ to M4, that is, he(M1) = M4.

Therefore, G is PM-transitive.

Case 3. G ∼= Ci10(2, 5) is not PM-transitive.

Let M¹ = {v1v6, v2v7, v3v8, v4v9, v5v10} and M² = {v1v3, v5v7, v4v9, v2v10, v6v8}. Then M¹ and M² are two perfect matchings of G such that G−M¹ is a union of two 5-cycles while G−M² is a union of a 4-cycle and a 6-cycle. Therefore, G is not PM-transitive.

Case 4. G ∼= Ci10(1, 2, 3) is not PM-transitive.

Let M¹ = {v1v2, v3v4, v5v6, v7v8, v9v10} and M² = {v1v4, v7v10, v3v6, v9v2, v5v8}. Then M¹ and M² are two perfect matchings of G. Suppose that f is an automorphism f : V (G) → V (G) such that fe(M1) = M2. Without loss of generality, let f(v1) = v1. This forces f(v2) = v4.

Consider v10. If f(v10) = v2, then this forces f(v9) = v9. Now v2v⁹ ∈ E(G) and v4v⁹ ∈/ E(G), contradicting the supposition that f is an automorphism. If f(v10) = v3, then this forces f(v9) = v6. Now v1v⁹ ∈ E(G) and v1v⁶ ∈/ E(G), a contradiction. If f(v10) = v5, then v1v¹⁰ ∈ E(G) and v1v⁵ ∈/ E(G), a contradiction. If f(v10) = v6, then v1v¹⁰ ∈ E(G) and v1v⁶ ∈/ E(G), a contradiction. If f(v10) = v7, then v1v¹⁰ ∈ E(G) and v1v⁷ ∈/ E(G), a contradiction. If f(v10) = v8, then v2v¹⁰ ∈ E(G) and v4v⁸ ∈/ E(G), a contradiction. If f(v10) = v9, then v2v¹⁰ ∈ E(G) and v4v⁹ ∈/ E(G), a contradiction. If f(v10) = v10, then v2v¹⁰ ∈ E(G) and v4v¹⁰ ∈/ E(G), a contradiction. Therefore, G is not PM-transitive.

Case 5. G ∼= Ci10(1, 2, 4) is not PM-transitive.

Let M¹ = {v1v5, v2v8, v3v9, v4v10, v6v7} and M² = {v1v2, v3v4, v5v6, v7v8, v9v10}. Then M¹ and M² are two perfect matchings of G. Suppose that f is an automorphism f : V (G) → V (G) such that fe(M1) = M2. Without loss of generality, let f(v1) = v1. This forces f(v5) = v2.

Consider v7. Since v1v7, v5v⁷ ∈ E(G), it is the case that f(v1)f(v7) = v1f(v7) ∈ E(G) and f(v5)f(v7) = v2f(v7) ∈ E(G). Since v³ and v¹⁰ are the only vertices adjacent to both v¹ and v2, the image of v⁷ is either v³ or v10.

If f(v7) = v3, then this forces f(v6) = v4. Now, any proposed preimage of v¹⁰ will contradict the fact that f is an automorphism. Specifically, if f(v2) = v10, then v2v⁵ ∈/ E(G) contradicts v10v² ∈ E(G). If f(v3) = v10, then v3v⁶ ∈/ E(G) contradicts v10v⁴ ∈ E(G). If f(v4) = v10, then v4v¹ ∈/ E(G) contradicts v10v¹ ∈ E(G). If f(v8) = v10, then v8v⁵ ∈/ E(G) contradicts v10v² ∈ E(G). If f(v9) = v10, then v9v⁶ ∈/ E(G) contradicts v10v⁴ ∈ E(G). If f(v10) = v10, then v10v⁵ ∈/ E(G) contradicts v10v² ∈ E(G).

If f(v7) = v10, then this forces f(v6) = v9. Now, any proposed preimage of v³ will contradict the fact that f is an automorphism. Specifically, if f(v2) = v3, then v5v² ∈/ E(G) contradicts v2v³ ∈ E(G). If f(v3) = v3, then v7v³ ∈ E(G) contradicts v10v³ ∈/ E(G). If f(v4) = v3, then

v1v⁴ ∈/ E(G) contradicts v1v³ ∈ E(G). If f(v8) = v3, then v1v⁸ ∈/ E(G) contradicts v1v³ ∈ E(G). If f(v9) = v3, then v7v⁹ ∈ E(G) contradicts v10v³ ∈/ E(G). If f(v10) = v3, then v5v¹⁰ ∈/ E(G) contradicts v2v³ ∈ E(G). Therefore, G is not PM-transitive.

Case 6. G ∼= Ci10(1, 2, 5) is not PM-transitive.

Let M¹ = {v1v6, v2v7, v3v8, v4v9, v5v10} and M² = {v1v2, v3v4, v5v6, v7v8, v9v10}. Then M¹ and M² are two perfect matchings of G. Suppose that f is an automorphism f : V (G) → V (G) such that fe(M1) = M2. Without loss of generality, let f(v1) = v1. This forces f(v6) = v2.

Now, any proposed preimage of v¹⁰ will contradict the fact that f is an automorphism. Specifically, if f(v2) = v10, then v2v⁶ ∈/ E(G) contradicts v10v² ∈ E(G). If f(v3) = v10, then v3v⁶ ∈/ E(G) contradicts v10v² ∈ E(G). If f(v4) = v10, then v4v¹ ∈/ E(G) contradicts v10v¹ ∈ E(G). If f(v5) = v10, then v5v¹ ∈/ E(G) contradicts v10v¹ ∈ E(G). If f(v7) = v10, then v7v¹ ∈/ E(G) contradicts v10v¹ ∈ E(G). If f(v8) = v10, then v8v¹ ∈/ E(G) contradicts v10v¹ ∈ E(G). If f(v9) = v10, then v9v⁶ ∈/ E(G) contradicts v10v² ∈ E(G). If f(v10) = v10, then v10v⁶ ∈/ E(G) contradicts v10v² ∈ E(G). Therefore, G is not PM-transitive.

Case 7. G ∼= Ci10(1, 4, 5) is not PM-transitive.

Let M¹ = {v1v6, v2v7, v3v8, v4v9, v5v10} and M² = {v1v2, v3v4, v5v6, v7v8, v9v10}. Then M¹ and M² are two perfect matchings of G. Suppose that f is an automorphism f : V (G) → V (G) such that fe(M1) = M2. Without loss of generality, let f(v1) = v1. This forces f(v6) = v2.

Now, any proposed preimage of v¹⁰ will contradict the fact that f is an automorphism. Specifically, if f(v2) = v10, then v2v⁶ ∈ E(G) contradicts v10v² ∈/ E(G). If f(v3) = v10, then v3v¹ ∈/ E(G) contradicts v10v¹ ∈ E(G). If f(v4) = v10, then v4v¹ ∈/ E(G) contradicts v10v¹ ∈ E(G). If f(v5) = v10, then v5v⁶ ∈ E(G) contradicts v10v² ∈/ E(G). If f(v7) = v10, then v7v⁶ ∈ E(G) contradicts v10v² ∈/ E(G). If f(v8) = v10, then v8v¹ ∈/ E(G) contradicts v10v¹ ∈ E(G). If f(v9) = v10, then v9v¹ ∈/ E(G) contradicts v10v¹ ∈ E(G). If f(v10) = v10, then v10v⁶ ∈ E(G) contradicts v10v² ∈/ E(G). Therefore, G is not PM-transitive.

Case 8. G ∼= Ci10(2, 4, 5) is not PM-transitive.

Let M¹ = {v1v3, v2v7, v4v8, v5v9, v6v10} and M² = {v1v6, v2v7, v3v8, v4v9, v5v10}. Then M¹ and M² are two perfect matchings of G. Suppose that f is an automorphism f : V (G) → V (G) such that fe(M1) = M2. Without loss of generality, let f(v1) = v1. This forces f(v3) = v6.

Consider v7. Since v1v7, v3v⁷ ∈ E(G), it is the case that f(v1)f(v7) = v1f(v7) ∈ E(G) and f(v3)f(v7) = v6f(v7) ∈ E(G). Since there are no vertices adjacent to both v¹ and v6, this is a contradiction. Therefore, G is not PM-transitive.

Case 9. G ∼= Ci10(1, 2, 3, 5) is not PM-transitive.

Let M¹ = {v1v3, v2v4, v5v6, v7v8, v9v10} and M² = {v1v2, v3v4, v5v6, v7v8, v9v10}. Then M¹ and M² are two perfect matchings of G. Suppose that f is an automorphism f : V (G) → V (G) such that fe(M1) = M2. Without loss of generality, let f(v1) = v1. This forces f(v3) = v2.

Consider v7. Since v1v7, v3v⁷ ∈/ E(G), it is the case that f(v1)f(v7) = v1f(v7) ∈/ E(G) and f(v3)f(v7) = v2f(v7) ∈/ E(G). Since every vertex is adjacent to at least one of v¹ and v2, this is a contradiction. Therefore, G is not PM-transitive.

Case 10. G ∼= Ci10(1, 2, 4, 5) is not PM-transitive.

Let M¹ = {v1v5, v2v8, v3v9, v4v10, v6v7} and M² = {v1v2, v3v4, v5v6, v7v8, v9v10}. Then M¹ and M² are two perfect matchings of G. Suppose that f is an automorphism f : V (G) → V (G) such that fe(M1) = M2. Without loss of generality, let f(v1) = v1. This forces f(v5) = v2.

Consider \(v_7\). Since \(v_1v_7, v_5v_7 \in E(G)\), it is the case that \(f(v_1)f(v_7) = v_1f(v_7) \in E(G)\) and \(f(v_5)f(v_7) = v_2f(v_7) \in E(G)\). Since \(v_3, v_6, v_7\), and \(v_{10}\) are the only vertices adjacent to both \(v_1\) and \(v_2\), the image of \(v_7\) is either \(v_3, v_6, v_7\), or \(v_{10}\). If \(f(v_7) = v_3\), then this forces \(f(v_6) = v_4\). Now, \(v_1v_6 \in E(G)\) contradicts \(v_1v_4 \notin E(G)\). If \(f(v_7) = v_6\), then this forces \(f(v_6) = v_5\). Now, \(v_5v_6 \in E(G)\) contradicts \(v_2v_5 \notin E(G)\). If \(f(v_7) = v_7\), then this forces \(f(v_6) = v_8\). Now, \(v_1v_6 \in E(G)\) contradicts \(v_1v_8 \notin E(G)\). If \(f(v_7) = v_{10}\), then this forces \(f(v_6) = v_9\). Now, \(v_5v_6 \in E(G)\) contradicts \(v_2v_9 \notin E(G)\). Therefore, G is not PM-transitive.

In summary, the connected PM-transitive circulant graphs of order 10 are congruent to \(Ci_{10}(1)\), \(Ci_{10}(1,4) \cong Ci_{10}(2,3)\), \(Ci_{10}(1,3,5)\), or \(Ci_{10}(1,2,3,4,5)\). That is to say, the connected PM-transitive circulant graphs of order 10 are congruent to \(C_{10}\), \(Ci_{10}(1,4) \cong Ci_{10}(2,3)\), \(K_{5,5}\), or \(K_{10}\).

Acknowledgement

The authors are grateful for the support of the FPDC Grant in conducting this research.

References

• [1] B.R. Alspach, The classification of Hamiltonian generalized Petersen graphs, Journal of Combinatorial Theory, Series B 34 (1983), 293-312. https://www.sciencedirect.com/science/article/pii/0095895683900424
• [2] L. Babai, Automorphism groups, isomorphism, reconstruction, Handbook of Combinatorics (1996).
• [3] Z. Bouwer, Vertex and edge-transitive, but not 1-transitive graphs, Canadian Mathematical Bulletin 13 (1970), 231-237. <a href="https://www.cambridge.org/core/journals/canadian-mathematical-bulletin/article/vertex-and-edge-transitive-but-not-1transitive-graphs/A8D20CEBB3C8D150712B72040A422757">https://www.cambridge.org/core/journals/canadian-mathematical-bulletin/article/vertex-and-edge-transitive-but-not-1transitive-graphs/A8D20CEBB3C8D150712B72040A422757</a>
• [4] N. Biggs, Algebraic Graph Theory (2nd ed.), Cambridge: Cambridge University Press., (1993), 118. <a href="https://www.cambridge.org/core/books/algebraic-graph-theory/6C70471342F19680068C35">https://www.cambridge.org/core/books/algebraic-graph-theory/6C70471342F19680068C35</a> EF174075DC
• [5] M. Conder, Trivalent symmetric graphs on up to 768 vertices, Journal of Combinatorial Mathematics and Combinatorial Computing 20 (2000), 41-63. https://www.researchgate.net/publication/2617744_Trivalent_Symmetric_Graphs_On_Up_To__________________________________
• [6] R. Diestel and I. Leader, A conjecture concerning a limit of non-Cayley graphs, Journal of Algebraic Combinatorics 14(1) (2001), 17-25. https://link.springer.com/article/10.1023/A%3A1011257718029
• [7] A. Eskin, D. Fisher, and K. Whyte, Quasi-isometries and rigidity of solvable groups, 2005. https://arxiv.org/abs/math/0511647

• [8] R.M. Foster, Geometrical circuits of electrical networks, Transactions of the American Institute of Electrical Engineers 51 (1932), 309-317. https://ieeexplore.ieee.org/document/5056068
• [9] R.M. Foster, I.Z. Bouwer, W.W. Chernoff, B. Monson, and Z. Star, The Foster Census: R.M. Foster's Census of Connected Symmetric Trivalent Graphs, 1988. https://search.library.wisc.edu/catalog/999595788402121
• [10] R. Frucht, J.E. Graver, and M.E. Watkins, The groups of the generalized Petersen graphs, Proc. Cambridge Philos. Soc. 70 (1971), 211-218. https://www.cambridge.org/core/journals/mathematical-proceedings-of-the-cambridgephilosophical-society/article/abs/groups-of-the-generalized-petersen-graphs/33EC7C273E88 97088CEE71060A3659CD
• [11] C. Godsil and G. Royle, Algebraic Graph Theory, Graduate Texts in Mathematics, New York: Springer-Verlag (2001), 207. https://link.springer.com/book/10.1007/978-1-4613-0163-9
• [12] J.L. Gross and J. Yellen, Handbook of Graph Theory, CRC Press. (2004), 491. https://www.routledge.com/Handbook-of-Graph-Theory/Gross-Yellen-Zhang/p/book/ 9781439880180
• [13] D.F. Holt, A graph which is edge-transitive but not arc-transitive, Journal of Graph Theory 5(2) (1981), 201-204. https://onlinelibrary.wiley.com/doi/10.1002/jgt.3190050210
• [14] D.A. Holton and J. Sheehan, Generalized Petersen and permutation graphs, §9.13 in The Petersen Graph, Cambridge, England: Cambridge University Press (1993), 315-317. https://www.abebooks.com/9780521435949/Petersen-Graph-Australian-Mathematical-Society-0521435943/plp
• [15] J. Lauri and R. Scapellato, Topics in graph automorphisms and reconstruction, London Mathematical Society Lecture Note Series, Cambridge University Press (2003), 20-21. https://www.cambridge.org/core/books/topics-in-graph-automorphisms-and-reconstruction/ 3699EDC473353370EFA6FD93FA26A160
• [16] P. Potocnik, P. Spiga, and G. Verret, Cubic vertex-transitive graphs on up to 1280 vertices, ˇ Journal of Symbolic Computation 50 (2013), 465-477. https://www.sciencedirect.com/science/article/pii/S0747717112001563
• [17] Z. Ryja´cek, On a closure concept in claw-free graphs, ˘ Journal of Combinatorial Theory, Series B 70(2) (1997), 217-224. https://www.sciencedirect.com/science/article/pii/S0095895696917323
• [18] J. Zhou, Characterization of perfect matching transitive graphs, Electronic Journal of Graph Theory and Applications 6(2) (2018), 362-369. https://www.ejgta.org/index.php/ejgta/article/view/583