Ju Zhou

Department of Mathematics Kutztown University of Pennsylvania Kutztown, PA 19530, USA

zhou@kutztown.edu

A graph G is perfect matching transitive, shortly PM-transitive, if for any two perfect matchings M and N of G, there is an automorphism f : V (G) 7→ V (G) such that fe(M) = N, where fe(uv) = f(u)f(v). In this paper, the author proposed the definition of PM-transitive, verified PM-transitivity of some symmetric graphs, constructed several families of PM-transitive graphs which are neither vertex-transitive nor edge-transitive, and discussed PM-transitivity of generalized Petersen graphs.

Keywords: vertex-transitive, edge-transitive, symmetric, PM-transitive

Mathematics Subject Classification : 68R10, 05C60

DOI: 10.5614/ejgta.2018.6.2.15

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. That is, it is a graph isomorphism from G to itself. Every graph automorphism f induces a map 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

Received: 20 March 2018, Revised: 2 September 2018, Accepted: 27 September 2018.

fe(M) = {fe(uv) = f(u)f(v) : uv ∈ M}. In this paper, we also use f to denote the map induced by the automorphism f.

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 graph complement is vertex-transitive (since the group actions are identical). For example, the finite Cayley graphs, Petersen graph, and Cⁿ × K² with n ≥ 3, are vertex-transitive.

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, 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 u1|v¹ and u2|v² 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 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 N of G, there is an automorphism f : V (G) 7→ V (G) such that fe(M) = N, where f^e is the map induced by f.

Are there any PM-transitive graphs? What kind of properties do PM-transitive graphs have? What is the relationship between PM-transitive and edge-transitive? What is the relationship between PM-transitive and vertex-transitive? What is the relationship between PM-transitive and symmetric?

In section 2, the author verified that some well known symmetric graphs such as C2n, K2n, Kn,n and Petersen graph are PM-transitive, and constructed several families of PM-transitive graphs which are neither vertex-transitive nor edge-transitive. In section 3, the author discussed some methods to generate new PM-transitive graphs. In section 4, the author proved that all the generated Petersen graphs except the Petersen graph are non-perfect matching transitive. In section 5, the author provided some examples which have one or more properties of vertex-transitive, edgetransitive, or PM-transitive.

2. PM-Transitive Graphs

In this section, we characterize some PM-transitive graphs.

Theorem 2.1. Every even cycle G = C2ⁿ with n ≥ 2 is PM-transitive.

Proof. Let C2ⁿ = u1u² · · · u2nu¹ with n ≥ 2. Note that C2ⁿ has exactly two perfect matchings, denoted by M = {u1u2, u3u4, · · · , u2n−1u2n} and N = {u2u3, u4u5, · · · , u2nu1}, respectively. Define f : V (G) 7→ V (G) such that f(ui) = ui+1. Since for any edge uiui+1 ∈ E(C2n), f(uiui+1) = f(ui)f(ui+1) = ui+1ui+2 ∈ E(C2n), f is an automorphism of C2n. By the definition of M, N and f, fe(M) = N follows and G is PM-transitive.

Theorem 2.2. Every even complete graph G = K2ⁿ with n ≥ 2 is PM-transitive.

Proof. Let M and N be two perfect matchings of G. Let M4N denote the symmetric difference of M and N, and also the graph induced by M4N. Since every vertex of G is incident with exactly one edge in M and exactly one edge in N, M4N is a disjoint union of even cycles. Define f : V (G) 7→ V (G) such that f(u) = u if u ∈ V (M ∩N) and f(ui) = ui+1 if uⁱ ∈ V (C2s), where C2^s = u1u² · · · u2su¹ is an even cycle in M4N. Since G is a complete graph, f is an automorphism of G. Let uv ∈ M. If uv ∈ M ∩ N, then fe(uv) = f(u)f(v) = uv ∈ N. If uv ∈ M \ N, then uv is an edge of some even cycle of M4N. Let uv = uiui+1. Then fe(uv) = fe(uiui+1) = f(ui)f(ui+1) = ui+1ui+2 ∈ N. Therefore, fe(M) = N follows and G is PM-transitive.

Theorem 2.3. Every complete bipartite graph G = Kn,n is PM-transitive.

Proof. Let M and N be two perfect matchings of G. Then M4N is a disjoint union of even cycles. Define f such that f(u) = u if u ∈ V (M ∩ N), and f(u1) = u¹ and f(ui) = u2s+2−ⁱ for 2 ≤ i ≤ 2s, where C2^s = u1u² · · · u2su¹ is an even cycle in M4N. Let (X, Y ) be the bipartition of G. By the definition of f, f(X) = X and f(Y ) = Y . Since G is a complete bipartite graph, f is an automorphism of G. Let uv ∈ M. If uv ∈ M ∩ N, then fe(uv) = f(u)f(v) = uv ∈ N. If uv ∈ M \ N, then uv is an edge of some even cycle of M4N. Without loss of generality, suppose that uv = uiui+1. Then fe(uv) = fe(uiui+1) = f(ui)f(ui+1) = u2s+2−iu2s+2−(i+1) ∈ N. Therefore, fe(M) = N follows and G is PM-transitive.

Theorem 2.4. The Petersen graph is PM-transitive.

Proof. Let G be the graph obtained from the union of two cycles u1u2u3u4u5u¹ and v1v3v5v2v4v¹ by connecting uivⁱ , where i = 1, 2, · · · , 5. Then G is a Petersen graph. Let M be a perfect matching of G and let N = {u1v1, u2v2, u3v3, u4v4, u5v5}.

Claim: If M 6= N, then |M ∩ N| = 1. Suppose that M 6= N. Then G − V (M ∩ N) is an even cycle or unions of even cycles. Since the Petersen graph does not have 2-cycles, 4-cycles, or 6-cycles, |M ∩ N| 6= 4, 3, 2.

Without loss of generality, we assume that N = {u1v1, u2u3, u4u5, v2v4, v3v5}. Define f : V (G) 7→ V (G) such that f(v) = v if v ∈ {u1, u2, u5, v1}, f(u3) = v2, f(u4) = v5, f(v2) = u3, f(v3) = v4, f(v4) = v³ and f(v5) = v4. Then f is an automorphism of G such that fe(M) = N.

Theorem 2.5. Let G be the graph obtained from \(C_{2n+2} = u_0 u_1 u_2 \cdots u_n v_0 v_n v_{n-1} \cdots v_1 u_0\) with \(n \geq 2\) by connecting \(u_i v_{i+1}\) and \(v_i u_{i+1}\), where \(i = 1, 2, \cdots, n-1\). Then G is PM-transitive.

Proof. We prove this result by induction. When n=2, G has four different perfect matchings. Denote them by \(M_1 = \{u_0v_1, u_1v_2, u_2v_0\}\), \(M_2 = \{u_0u_1, v_1v_2, u_2v_0\}\), \(M_3 = \{u_0v_1, u_1u_2, v_0v_2\}\), and \(M_4 = \{u_0u_1, u_2v_1, v_0v_2\}\), respectively. To prove that G is perfect matching transitive, it suffices to prove that for \(M \in \{M_2, M_3, M_4\}\), there is an automorphism f of G such that \(f_e(M) = M_1\). Furthermore, we can restrict that \(v_0\) and \(u_0\) are fixed under f.

If \(M=M_2\), then define \(f_2:V(G)\mapsto V(G)\) such that \(f_2(u_1)=v_1\), \(f_2(v_1)=u_1\), and \(f_2(v)=v\) for \(v\in V(G)\setminus\{u_1,v_1\}\). Then \(f_2\) is an automorphism such that \(f_2(M_2)=M_1\), and \(v_0\) and \(u_0\) are fixed under \(f_2\).

If \(M=M_3\), then define \(f_3:V(G)\mapsto V(G)\) such that \(f_3(u_2)=v_2\), \(f_3(v_2)=u_2\) and \(f_3(v)=v\) for \(v\in V(G)\setminus\{u_2,v_2\}\). Then \(f_3\) is an automorphism such that \(f_3(M_3)=M\), and \(v_0\) and \(u_0\) are fixed under \(f_3\).

If \(M=M_4\), then define \(f_4:V(G)\mapsto V(G)\) such that \(f_4(u_1)=v_1\), \(f_4(v_1)=u_1\), \(f_4(u_2)=v_2\), \(f_4(v_2)=u_2\) and \(f_4(v)=v\) for \(v\in V(G)\setminus\{u_1,v_1,u_2,v_2\}\). Then \(f_4\) is an automorphism such that \(f_4(M_4)=M_1\), and \(v_0\) and \(u_0\) are fixed under \(f_4\).

Now assume the result is true for \(n=m\geq 2\). That is, for any two different perfect matchings M and N of G, there is an automorphism f of G such that \(f_e(M)=N\), and \(v_0\) and \(u_0\) are fixed under f.

We want to prove the result is true for n=m+1. Let M and N be two perfect matchings of G. Without loss of generality, assume that \(u_0u_1 \in M\).

Case 1. \(u_0u_1 \in N\). In this case, \(M_1 = M - \{u_0u_1\}\) and \(N_1 = N - \{u_0u_1\}\) are two perfect matchings of \(G_1 = G - \{u_0, u_1\}\). By the induction hypothesis, there is an automorphism \(f_1\) of \(G_1\) such that \(f_1(M_1) = N_1\), and \(v_0\) and \(v_1\) are fixed under \(f_1\). Define \(f: V(G) \mapsto V(G)\) such that \(f(u_0) = u_0\), \(f(u_1) = u_1\) and \(f(v) = f_1(v)\) if \(v \in V(G_1)\). Then f is an automorphism of G such that \(f_e(M) = N\).

Case 2. \(u_0u_1 \notin N\). In this case, \(u_0v_1 \in N\). Define \(f_1: V(G) \mapsto V(G)\) such that \(f_1(u_1) = v_1\), \(f_1(v_1) = u_1\) and \(f_1(v) = v\) for \(v \in V(G) \setminus \{u_1, v_1\}\). Let \(N_1 = f_1(N)\). Then \(u_0u_1 \in N_1\). By Case 1, there is an automorphism \(f_2\) of G such that \(f_2(M) = N_1\), and \(v_0\) and \(u_0\) are fixed under \(f_2\). Then \(f = f_1^{-1}f_2\) is an automorphism of G such that \(f_e(M) = N\).

Theorem 2.6. Let G be the graph obtained from \(C_{2n+2} = u_0 u_1 u_2 \cdots u_n v_0 v_n v_{n-1} \cdots v_1 u_0\) with \(n \geq 2\) by connecting \(u_i v_{i+1}\) and \(v_i u_{i+1}\) for \(i = 1, 2, \cdots, n-1\), and \(u_i v_i\) for \(i = 1, 2, \cdots, n\). Then G is PM-transitive.

Proof. Since \(u_i v_i\) is not contained in any perfect matching of G, where \(i = 1, 2, \dots, n\), following exactly the same argument to the proof of Theorem 4, we can prove that G is PM-transitive. \(\Box\)

Theorem 2.7. Let G be the graph obtained from \(K_{n+1,n+1}\) by removing one edge \(u_0v_0\). Then G is PM-transitive.

Proof. We prove this result by induction. Let (X,Y) be the bipartition of \(K_{n+1,n+1}\) and let \(X=\{u_0,u_1,u_2,\cdots,u_n\}\) and \(Y=\{v_0,v_1,v_2,\cdots,v_n\}\). When n=2, by Theorem 2.5, G is PM-transitive and furthermore, for any two different perfect matchings M and N of G, there is an automorphism f of G such that \(f_e(M)=N\), and \(v_0\) and \(u_0\) are fixed under f. Now assume the result is true for \(n=m\geq 2\). That is, for any two different perfect matchings M and N of G, there is an automorphism f of G such that \(f_e(M)=N\), and \(v_0\) and \(v_0\) are fixed under f.

We want to prove the result is true for n = m + 1. Let M and N be two perfect matchings of G. Without loss of generality, assume that \(u_0u_1, v_0v_1 \in M\).

Case 1: \(u_0v_1, v_0u_1 \in N\). Then, \(M_1 = M - \{u_0v_1, v_0u_1\}\) and \(N_1 = N - \{u_0v_1, v_0u_1\}\) are two perfect matchings of \(G_1 = G - \{u_0, u_1, v_0, v_1\} \cong K_{n-1,n-1}\). By Theorem 2.3, there is an automorphism \(f_1\) of \(G_1\) such that \(f_1(M_1) = N_1\), \(f_1(X \setminus \{u_0, u_1\}) = X \setminus \{u_0, u_1\}\) and \(f_1(Y \setminus \{v_0, v_1\}) = Y \setminus \{v_0, v_1\}\). Define \(f: V(G) \mapsto V(G)\) such that \(f(v) = f_1(v)\) if \(v \in V(G_1)\) and f(v) = v if \(v \in \{u_0, u_1, v_0, v_1\}\). Then f is an automorphism of G such that f(M) = N and, \(v_0\) and \(u_0\) are fixed under f.

Case 2: \(u_0v_1 \not\in N\) or \(v_0u_1 \not\in N\). Without loss of generality, we can assume that \(v_0u_i \in N\) and \(u_0v_j \in N\). Define \(f_1: V(G) \mapsto V(G)\) such that \(f_1(u_1) = u_i\), \(f_1(u_i) = u_1\), \(f_1(v_1) = v_j\), \(f_1(v_j) = v_1\) and \(f_1(v) = v\) if \(v \not\in \{u_1, u_i, v_1, v_j\}\). Let \(N_1 = f_1(N)\). Then \(u_0v_1, v_0u_1 \in N_1\). By Case 1, there is an automorphism \(f_2\) of G such that \(f_2(M) = N_1\), and \(v_0\) and \(u_0\) are fixed under \(f_2\). Then \(f = f_1^{-1}f_2\) is an automorphism of G such that \(f_e(M) = N\).

Theorem 2.8. Let G be the graph obtained from \(K_{2n+2}\) by removing one edge \(u_0v_0\). Then G is PM-transitive.

Proof. Let M and N be two perfect matchings of G. Without loss of generality, assume that \(u_0u_1, v_0v_1 \in M\).

Case 1: \(u_0u_1, v_0v_1 \in N\). Then, \(M_1 = M - \{u_0u_1, v_0v_1\}\) and \(N_1 = N - \{u_0u_1\}\) are two perfect matchings of \(G_1 = G - \{u_0, u_1, v_0, v_1\} \cong K_{2n-2}\). By Theorem 2.2, there is an automorphism \(f_1\) of \(G_1\) such that \(f_1(M_1) = N_1\). Define \(f: V(G) \mapsto V(G)\) such that \(f(v) = f_1(v)\) if \(v \in V(G_1)\) and f(v) = v if \(v \in \{u_0, u_1, v_0, v_1\}\). Then f is an automorphism of G such that f(M) = N.

Case 2: \(u_0u_1 \not\in N\) or \(v_0v_1 \not\in N\). Without loss of generality, we can assume that \(u_0u_i \in N\) and \(v_0v_j \in N\). Define \(f_1: V(G) \mapsto V(G)\) such that \(f_1(u_1) = u_i\), \(f_1(u_i) = u_1\), \(f_1(v_1) = v_j\), \(f_1(v_j) = v_1\) and \(f_1(v) = v\) if \(v \not\in \{u_1, u_i, v_1, v_j\}\). Let \(N_1 = f_1(N)\). Then \(u_0u_1, v_0v_1 \in N_1\). By Case 1, there is an automorphism \(f_2\) of G such that \(f_2(M) = N_1\). Then \(f = f_1^{-1}f_2\) is an automorphism of G such that \(f_2(M) = N\).

A wheel \(W_n\) is the graph obtained from a n-cycle by adding a new vertex and joining the new vertex to every vertex of the cycle.

Theorem 2.9. Let \(G = W_{2n+1}\). Then G is PM-transitive.

Proof. Without loss of generality, let G be the graph obtained from C2n+1 = v1v² · · · v2n+1v¹ by adding a new vertex v and joining v to every vertex of the cycle. Suppose that M and N are two perfect matchings of G. Without loss of generality, suppose that vvⁱ ∈ M and vv^j ∈ N. Define f : V (G) 7→ V (G) such that f(v) = v, f(vi) = v^j , and f(vi+k) = vj+k, where the subscripts are taken modular 2n + 1. Then f is an automorphism of G such that fe(M) = N.

Theorem 2.10. Let k be a positive even integer, W2n¹ , W2n² , · · · W2n^k be k wheels and v1, v2, · · · , v^k be the centers of the wheels, respectively. If G = W2n1∪W2n2∪· · ·∪W2nk+{v1v2, v2v3, · · · , vk−1vk}, then G is PM-transitive.

Proof. Let M and N be two perfect matchings of G. Then v1v2, v3v4, · · · , vk−1v^k ∈ M ∩ N. Furthermore, M¹ = M\{v1v2, v3v4, · · · , vk−1vk} and N¹ = N\{v1v2, v3v4, · · · , vk−1vk} are two perfect matchings of disjoint union of even cycles generated by G − {v1, v2, · · · , vk}. Then there is an automorphism f of G such that fe(M) = N.

3. Properties of PM-Transitive Graphs

In this section, we generate new PM-transitive graphs from existing PM-transitive graphs.

Theorem 3.1. If G¹ and G² are two perfect matching transitive graphs and V (G1) ∩ V (G2) = ∅, then G = G¹ ∪ G² is PM-transitive.

Proof. Let M and N be two perfect matchings of G. For i = 1, 2, let Mⁱ = M ∩ E(Gi) and Nⁱ = N ∩ E(Gi). Then Mⁱ and Nⁱ are two perfect matchings of Gⁱ . Since Gⁱ is PM-transitive, there is an automorphism fⁱ of Gⁱ such that fi(Mi) = Nⁱ . Define f : V (G) 7→ V (G) such that f(v) = f1(v) if v ∈ V (G1), and f(v) = f2(v) if v ∈ V (G2). Then f is an automorphism of G such that fe(M) = N.

Theorem 3.2. Let G¹ and G² be two PM-transitive graphs and H be a path of odd length. Suppose that G is the graph obtained from G1, G² and H by connecting one end vertex of H with every vertex of G¹ and the other end vertex of H with every vertex of G2. Then G is PM-transitive.

Proof. Let M and N be two perfect matchings of G. Then M ∩ E(H) = N ∩ E(H) and M¹ = M \ M ∩ E(H) and N¹ = M \ N ∩ E(H) are two perfect matchings of G⁰ = G¹ ∪ G2. By Theorem 4.2, there is an graph automorphism f ⁰ of G⁰ such that f 0 (M1) = N1. We can easily extend the graph automorphism f ⁰ of G⁰ to a graph automorphism f of G such that f(M) = N.

Corollary 3.1. Let G¹ be a perfect matching transitive graph and H be a path of odd length. Suppose that G is the graph obtained from G¹ and H by connecting an end vertex of H with every vertex of G. Then G is PM-transitive.

Corollary 3.2. Let W2n1+1, W2n2+2, · · · W2nk+1 be k wheels and v1, v2, · · · , v^k be the centers of the wheels, respectively. Let G be the graph obtained from W2n1+1 ∪ W2n2+1 ∪ · · · ∪ W2nk+1 + {v1v2, v2v3, · · · , vk−1vk, vkv1} by replacing vivi+1 with an odd path, where i = 1, 2, · · · , k and the addition is modular k. Then G is PM-transitive.

4. Non PM-Transitive Graphs

In this section, we characterize some non-perfect matching transitive graphs. The generalized Petersen graph GP(n, k) for n ≥ 3 and 1 ≤ k ≤ (n − 1)/2 is a graph consisting of an inner star polygon {n, k} (or circular graph) and an outer regular polygon {n} (or cycle graph Cn) with corresponding vertices in the inner and outer polygons connected with edges.

Theorem 4.1. ([4] and [10]) The generalized Petersen graph GP(n, k) is vertex-transitive if and only if k ² ≡ ±1 (mod n) or (n, k) = (10, 2), and symmetric only for the cases (n, k) = (4, 1),(5, 2),(8, 3),(10, 2),(10, 3),(12, 5), and (24, 5).

Theorem 4.2. ([1] and [14]) The generalized Petersen graph GP(n, k) is non-hamiltonian if and only if k = 2 and n ≡ 5 (mod 6).

Theorem 4.3. The generalized Petersen graph GP(n, k) is PM-transitive if and only if it is the Petersen graph.

Proof. Let G be a generalized graph GP(n, k), where k 6= 2 or n 6≡ 5 (mod 6). By Theorem 4.2, G is Hamiltonian. Let C be a hamiltonian cycle of G and M = G − C. Since G is a 3-regular graph, M is a perfect matching of G. Let N denote the perfect matching consisting of all the edges between the inner star polygon and the outer regular graph of GP(n, k). Note that G − M is a Hamiltonian cycle and G − N is the disjoint union of cycles. Therefore, there is no graph automorphism f of G such that f(M) = N.

Let G be a generalized graph GP(n, k), where k = 2 and n ≡ 5 (mod 6) and n 6= 5. In this case, the inner star polygon is an n-cycle. Denote the inner cycle by v1v3v⁵ · · · vnv2v⁴ · · · vn−1v¹ and the outer cycle by u1u2u³ · · · unu1. Let M = {u1v1} ∪ {u2u3, u4u5, · · · , un−1un} ∪ {v3v5, v7v9, · · · , vnv2, v4v6, · · · , vn−3vn−1} and N = {u1v1, u2v2, · · · , unvn}. Then M and N are two perfect matchings of G. Note that G − N is the disjoint union of two n-cycles. If n ≡ 3(mod 4), then G − N has a 14-cycle u1u2v2v4u4u3v3v1vn−1un−1un−2vn−2vnunu¹ and some 8-cycles. If n ≡ 1(mod 4), then G − N has a 5-cycle u1u2v2vnuuu¹ and a (2n − 5)-cycle. Therefore, there is no graph automorphism of G such that f(M) = N.

Coming the above discussion and Theorem 2.4 , the result follows.

5. Further Discussion

In this section, we give some examples which are PM-transitive, vertex-transitive, or edgetransitive.

Theorem 5.1. The generalized Petersen graph P G(n, 1) ∼= Cⁿ × K2, where n = 3 or n ≥ 5, is vertex-transitive, but not edge-transitive or PM-transitive.

Theorem 5.2. The cubical graph C⁴ ×K² ∼= P G(4, 1) is vertex-transitive and edge-transitive, but not PM-transitive.

Theorem 5.3. The graphs discussed in Theorem 2.1, Theorem 2.2, Theorem 2.3, and Theorem 2.4 are vertex-transitive, edge-transitive, and also PM-transitive.

Theorem 5.4. The graphs constructed in Theorem 2.5, Theorem 2.6, Theorem 2.7, Theorem 2.8, Theorem 2.9, and Theorem 2.10 are PM-transitive, but neither vertex-transitive nor edge-transitive.

References

• [1] B.R. Alspach, The classification of Hamiltonian generalized Petersen graphs, J. Combin. Theory Ser. B 34 (1983), 293–312.
• [2] L. Babai, Automorphism groups, isomorphism, reconstruction, Handbook of Combinatorics, 1996.
• [3] Z. Bouwer, Vertex and edge-transitive, but not 1-transitive graphs, Canad. Math. Bull. 13 (1970), 231–237.
• [4] N. Biggs, Algebraic Graph Theory, Second Edition, Cambridge England, Cambridge University Press, 1993.
• [5] M. Conder, Trivalent symmetric graphs on up to 768 vertices, J. Combin. Math. Combin. Comput. 20 (2000), 41–63.
• [6] R. Diestel, and I. Leader, A conjecture concerning a limit of non-Cayley graphs, J. Algebraic Combin. 14 (1) (2001), 17–25.
• [7] A. Eskin, D. Fisher, and K. Whyte, Quasi-isometries and rigidity of solvable groups, Proceedings of the International Congress of Mathematicians, Hyderabad, India 2010.
• [8] R.M. Foster, Geometrical circuits of electrical networks, Transactions of the American Institute of Electrical Engineers 51 (1932), 309–317.
• [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, Winnipeg, Canada, Charles Babbage Research Center, 1988.
• [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.
• [11] C. Godsil, and G. Royle, Algebraic Graph Theory, Graduate Texts in Mathematics 207, New York, Springer-Verlag, 2001.
• [12] J.L. Gross, J. Yellen, Handbook of Graph Theory, CRC Press, 2004.
• [13] D.F. Holt, A graph which is edge-transitive but not arc-transitive, J. Graph Theory 5 (2) (1981), 201–204.
• [14] D.A. Holton, and J. Sheehan, The Petersen Graph, Cambridge England, Cambridge University Press, 1993.
• [15] J. Lauri, and R. Scapellato, Topics in graph automorphisms and reconstruction, London Math. Soc. Stud. Texts 54, 1st Edition, Cambridge England, Cambridge University Press, 2003.

• [16] P. Potocnik, P. Spiga, and G. Verret, Cubic vertex-transitive graphs on up to 1280 vertices, ˇ J. Symbolic Comput. 50 (2013), 465–477.
• [17] Z. Ryja´cek, On a closure concept in claw-free graphs, ˘ J. Combin. Theory Ser. B 70 (2) (1997), 217–224.