Perfect matching transitivity of circulant graphs.

Isaac Armando Reiter, Ju Zhou


A graph G is perfect matching transitive, shortly PM-transitive, if for any two perfect matchings M1 and M2 of G, there is an automorphism f : V(G)↦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.


automorphism; vertex-transitive; edge-transitive; perfect matching; perfect matching transitivity; PM-transitive; circulant graph

Full Text:




B.R. Alspach, The classification of Hamiltonian generalized Petersen graphs, Journal of Combinatorial Theory, Series B 34 (1983), 293-312.

L. Babai, Automorphism groups, isomorphism, reconstruction, Handbook of Combinatorics (1996).

Z. Bouwer, Vertex and edge-transitive, but not 1-transitive graphs, Canadian Mathematical Bulletin 13 (1970), 231-237.

N. Biggs, Algebraic Graph Theory (2nd ed.), Cambridge: Cambridge University Press., (1993), 118.

M. Conder, Trivalent symmetric graphs on up to 768 vertices, Journal of Combinatorial Mathematics and Combinatorial Computing 20 (2000), 41-63.

R. Diestel and I. Leader, A conjecture concerning a limit of non-Cayley graphs, Journal of Algebraic Combinatorics 14(1) (2001), 17-25.

A. Eskin, D. Fisher, and K. Whyte, Quasi-isometries and rigidity of solvable groups, 2005.

R.M. Foster, Geometrical circuits of electrical networks, Transactions of the American Institute of Electrical Engineers 51 (1932), 309-317.

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.

R. Frucht, J.E. Graver, and M.E. Watkins, The groups of the generalized Petersen graphs, Proc. Cambridge Philos. Soc. 70 (1971), 211-218.


  • There are currently no refbacks.

ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats