On Cubic Nonsymmetric Cayley Graphs

Affiliation(s)

School of Mathematics and Statistics, Yunnan University, Kunming, China.

School of Mathematics and Information Sciences, Guangxi University, Nanning, China.

School of Mathematics and Statistics, Yunnan University, Kunming, China.

School of Mathematics and Information Sciences, Guangxi University, Nanning, China.

ABSTRACT

Let be a connected Cayley graph of group*G*, then Γ is called normal if the right regular representation of *G* is a normal subgroup of , the full automorphism group of Γ. For the case where *G* is a finite nonabelian simple group and Γ is symmetric cubic Cayley graph, Caiheng Li and Shangjin Xu proved that Γ is normal with only two exceptions. Since then, the normality of nonsymmetric cubic Cayley graph of nonabelian simple group aroused strong interest of people. So far such graphs which have been known are all normal. Then people conjecture that all of such graphs are either normal or the Cayley subset consists of involutions. In this paper we give an negative answer by two counterexamples. As far as we know these are the first examples for the non-normal cubic nonsymmetric Cayley graphs of finite nonabelian simple groups.

Let be a connected Cayley graph of group

Cite this paper

J. Li, B. Lou and R. Wang, "On Cubic Nonsymmetric Cayley Graphs,"*Open Journal of Discrete Mathematics*, Vol. 3 No. 1, 2013, pp. 39-42. doi: 10.4236/ojdm.2013.31008.

J. Li, B. Lou and R. Wang, "On Cubic Nonsymmetric Cayley Graphs,"

References

[1] N. Biggs, “Algebraic Graph Theory,” 2nd Edition, Cambridge University Press, New York, 1992.

[2] J. J. Li and Z. P. Lu, “Cubic s-Transitive Cayley Graphs,” Discrete Mathematics, Vol. 309, No. 28, 2009, pp. 6014-6025. doi:10.1016/j.disc.2009.05.002

[3] P. Lorimer, “Vertex-Transitive Graphs: Symmetric Graphs of Prime Valency,” Journal of Graph Theory, Vol. 8, No. 1, 1984, pp. 55-68. doi:10.1002/jgt.3190080107

[4] G. O. Sabidussi, “Vertex-Transitive Graphs,” Monatshefte für Mathematik, Vol. 68, No. 5, 1964, pp. 426-438. doi:10.1007/BF01304186

[5] W. T. Tutte, “A Family of Cubical Graphs,” Proceedings of the Cambridge Philosophical Society, Vol. 43, No. 4, 1947, pp. 459-474. doi:10.1017/S0305004100023720

[6] W. T. Tutte, “On the Symmetry of Cubic Graphs,” Canadian Journal of Mathematics, Vol. 11, No. 3, 1959, pp. 621-624. doi:10.4153/CJM-1959-057-2

[7] D. ?. Djokovic, “On Regular Graphs, II,” Journal of Combinatorial Theory, Series B, Vol. 12, No. 3, 1972, pp. 252-259. doi:10.1016/0095-8956(72)90039-1

[8] A. Gardiner, “Doubly-Primitive Vertex Stabilisers in Graphs,” Mathematische Zeitschrift, Vol. 135, No. 3, 1974, pp. 257-266. doi:10.1007/BF01215029

[9] A. Gardiner, “Arc-Transitivity in Graphs. II,” Quarterly Journal of Mathematics Oxford Series, Vol. 25, No. 2, 1974, pp. 163-167. doi:10.1093/qmath/25.1.163

[10] A. Gardiner, “Arc-Transitivity in Graphs. III,” Quarterly Journal of Mathematics Oxford Series, Vol. 27, No. 1, 1976, pp. 313-323. doi:10.1093/qmath/27.3.313

[11] D. ?. Djokovic and G. L. Miller, “Regular Graphs of Automorphisms of Cubic Graphs,” Journal of Combinatorial Theory, Series B, Vol. 29, No. 1, 1980, pp. 195-230. doi:10.1016/0095-8956(80)90081-7

[12] R. Weiss, “S-Transitive Graphs,” Algebraic Methods in Graph Theory, Vol. 25, No. 1, 1981, pp. 827-847.

[13] X. G. Fang, C. H. Li, J. Wang and M. Y. Xu, “On Cubic Normal Cayley Graphs of Finite Simple Groups,” Discrete Mathematics, Vol. 244, No. 1, 2002, pp. 67-75. doi:10.1016/S0012-365X(01)00075-9

[14] C. H. Li, “Isomorphisms of Finite Cayley Graphs,” Ph. D. Dissertation, Department of Mathematics of University of Western Australia, 1996.

[15] S. J. Xu, X. G. Fang, J. Wang and M. Y. Xu, “5-Arc Transitive Cubic Cayley Graphs on Finite Simple Groups,” European Journal of Combinatorics, Vol. 28, No. 3, 2007, pp. 1023-1036. doi:10.1016/j.ejc.2005.07.020

[16] J. D. Dixon and B. Mortimer, “Permutation Groups,” Springer-Verlag Press, New York, 1996.

[1] N. Biggs, “Algebraic Graph Theory,” 2nd Edition, Cambridge University Press, New York, 1992.

[2] J. J. Li and Z. P. Lu, “Cubic s-Transitive Cayley Graphs,” Discrete Mathematics, Vol. 309, No. 28, 2009, pp. 6014-6025. doi:10.1016/j.disc.2009.05.002

[3] P. Lorimer, “Vertex-Transitive Graphs: Symmetric Graphs of Prime Valency,” Journal of Graph Theory, Vol. 8, No. 1, 1984, pp. 55-68. doi:10.1002/jgt.3190080107

[4] G. O. Sabidussi, “Vertex-Transitive Graphs,” Monatshefte für Mathematik, Vol. 68, No. 5, 1964, pp. 426-438. doi:10.1007/BF01304186

[5] W. T. Tutte, “A Family of Cubical Graphs,” Proceedings of the Cambridge Philosophical Society, Vol. 43, No. 4, 1947, pp. 459-474. doi:10.1017/S0305004100023720

[6] W. T. Tutte, “On the Symmetry of Cubic Graphs,” Canadian Journal of Mathematics, Vol. 11, No. 3, 1959, pp. 621-624. doi:10.4153/CJM-1959-057-2

[7] D. ?. Djokovic, “On Regular Graphs, II,” Journal of Combinatorial Theory, Series B, Vol. 12, No. 3, 1972, pp. 252-259. doi:10.1016/0095-8956(72)90039-1

[8] A. Gardiner, “Doubly-Primitive Vertex Stabilisers in Graphs,” Mathematische Zeitschrift, Vol. 135, No. 3, 1974, pp. 257-266. doi:10.1007/BF01215029

[9] A. Gardiner, “Arc-Transitivity in Graphs. II,” Quarterly Journal of Mathematics Oxford Series, Vol. 25, No. 2, 1974, pp. 163-167. doi:10.1093/qmath/25.1.163

[10] A. Gardiner, “Arc-Transitivity in Graphs. III,” Quarterly Journal of Mathematics Oxford Series, Vol. 27, No. 1, 1976, pp. 313-323. doi:10.1093/qmath/27.3.313

[11] D. ?. Djokovic and G. L. Miller, “Regular Graphs of Automorphisms of Cubic Graphs,” Journal of Combinatorial Theory, Series B, Vol. 29, No. 1, 1980, pp. 195-230. doi:10.1016/0095-8956(80)90081-7

[12] R. Weiss, “S-Transitive Graphs,” Algebraic Methods in Graph Theory, Vol. 25, No. 1, 1981, pp. 827-847.

[13] X. G. Fang, C. H. Li, J. Wang and M. Y. Xu, “On Cubic Normal Cayley Graphs of Finite Simple Groups,” Discrete Mathematics, Vol. 244, No. 1, 2002, pp. 67-75. doi:10.1016/S0012-365X(01)00075-9

[14] C. H. Li, “Isomorphisms of Finite Cayley Graphs,” Ph. D. Dissertation, Department of Mathematics of University of Western Australia, 1996.

[15] S. J. Xu, X. G. Fang, J. Wang and M. Y. Xu, “5-Arc Transitive Cubic Cayley Graphs on Finite Simple Groups,” European Journal of Combinatorics, Vol. 28, No. 3, 2007, pp. 1023-1036. doi:10.1016/j.ejc.2005.07.020

[16] J. D. Dixon and B. Mortimer, “Permutation Groups,” Springer-Verlag Press, New York, 1996.