Research Article
BibTex RIS Cite

Two families of graphs that are Cayley on nonisomorphic groups

Year 2021, , 53 - 57, 15.01.2021
https://doi.org/10.13069/jacodesmath.867644

Abstract

A number of authors have studied the question of when a graph can be represented as a Cayley graph on more than one nonisomorphic group. The work to date has focussed on a few special situations: when the groups are $p$-groups; when the groups have order $pq$; when the Cayley graphs are normal; or when the groups are both abelian. In this paper, we construct two infinite families of graphs, each of which is Cayley on an abelian group and a nonabelian group. These families include the smallest examples of such graphs that had not appeared in other results.

References

  • [1] L. Babai, Isomorphism problem for a class of point-symmetric structures, Acta Math. Acad. Sci. Hungar. 29 (1977) 329–336.
  • [2] E. Dobson, Isomorphism problem for Cayley graphs of Z3 p, Discrete Math. 147 (1995) 87–94.
  • [3] E. Dobson, On the Cayley isomorphism problem, Discrete Math. 247(1-3) (2002) 107–116.
  • [4] E. Dobson, Automorphism groups of metacirculant graphs of order a product of two distinct primes, Combin. Probab. Comput. 15(1-2) (2006) 105–130.
  • [5] E. Dobson, J. Morris, Cayley graphs of more than one abelian group, arXiv:1505.05771.
  • [6] E. Dobson, D. Witte, Transitive permutation groups of prime-squared degree, J. Algebraic Combin. 16 (2002) 43–69.
  • [7] A. Joseph, The isomorphism problem for Cayley digraphs on groups of prime-squared order, Discrete Math. 141(1-3) (1995) 173–183.
  • [8] I. Kovács, M. Servatius, On Cayley digraphs on nonisomorphic 2-groups, J. Graph Theory 70(4) (2012) 435–448.
  • [9] C. H. Li, On isomorphisms of finite Cayley graphs–a survey, Discrete Math. 256(1-2) (2002), 301–334.
  • [10] C. H. Li, Z. P. Lu, P. Palfy, Further restrictions on the structure of finite CI-groups, J. Algebr. Comb. 26 (2007) 161–181.
  • [11] D. Marušic, J. Morris, Normal circulant graphs with noncyclic regular subgroups, J. Graph Theory 50(1) (2005) 13–24.
  • [12] L. Morgan, J. Morris, G. Verret, Digraphs with small automorphism groups that are Cayley on two nonisomorphic groups, The Art of Discrete and Applied Mathematics 3 (2020) #P1.01.
  • [13] J. Morris, Isomorphic Cayley graphs on different groups, Proceedings of the Twenty-seventh Southeastern International Conference on Combinatorics, Graph Theory and Computing (Baton Rouge, LA) 121 (1996) 93–96.
  • [14] J. Morris, Isomorphic Cayley graphs on nonisomorphic groups, J. Graph Theory 31(4) (1999) 345– 362.
  • [15] M. Muzychuk, On the isomorphism problem for cyclic combinatorial objects, Discrete Math. 197/198 (1999) 589–606.
  • [16] M. Muzychuk, A solution of the isomorphism problem for circulant graphs, Proc. London Math. Soc. 88 (2004) 1–41.
Year 2021, , 53 - 57, 15.01.2021
https://doi.org/10.13069/jacodesmath.867644

Abstract

References

  • [1] L. Babai, Isomorphism problem for a class of point-symmetric structures, Acta Math. Acad. Sci. Hungar. 29 (1977) 329–336.
  • [2] E. Dobson, Isomorphism problem for Cayley graphs of Z3 p, Discrete Math. 147 (1995) 87–94.
  • [3] E. Dobson, On the Cayley isomorphism problem, Discrete Math. 247(1-3) (2002) 107–116.
  • [4] E. Dobson, Automorphism groups of metacirculant graphs of order a product of two distinct primes, Combin. Probab. Comput. 15(1-2) (2006) 105–130.
  • [5] E. Dobson, J. Morris, Cayley graphs of more than one abelian group, arXiv:1505.05771.
  • [6] E. Dobson, D. Witte, Transitive permutation groups of prime-squared degree, J. Algebraic Combin. 16 (2002) 43–69.
  • [7] A. Joseph, The isomorphism problem for Cayley digraphs on groups of prime-squared order, Discrete Math. 141(1-3) (1995) 173–183.
  • [8] I. Kovács, M. Servatius, On Cayley digraphs on nonisomorphic 2-groups, J. Graph Theory 70(4) (2012) 435–448.
  • [9] C. H. Li, On isomorphisms of finite Cayley graphs–a survey, Discrete Math. 256(1-2) (2002), 301–334.
  • [10] C. H. Li, Z. P. Lu, P. Palfy, Further restrictions on the structure of finite CI-groups, J. Algebr. Comb. 26 (2007) 161–181.
  • [11] D. Marušic, J. Morris, Normal circulant graphs with noncyclic regular subgroups, J. Graph Theory 50(1) (2005) 13–24.
  • [12] L. Morgan, J. Morris, G. Verret, Digraphs with small automorphism groups that are Cayley on two nonisomorphic groups, The Art of Discrete and Applied Mathematics 3 (2020) #P1.01.
  • [13] J. Morris, Isomorphic Cayley graphs on different groups, Proceedings of the Twenty-seventh Southeastern International Conference on Combinatorics, Graph Theory and Computing (Baton Rouge, LA) 121 (1996) 93–96.
  • [14] J. Morris, Isomorphic Cayley graphs on nonisomorphic groups, J. Graph Theory 31(4) (1999) 345– 362.
  • [15] M. Muzychuk, On the isomorphism problem for cyclic combinatorial objects, Discrete Math. 197/198 (1999) 589–606.
  • [16] M. Muzychuk, A solution of the isomorphism problem for circulant graphs, Proc. London Math. Soc. 88 (2004) 1–41.
There are 16 citations in total.

Details

Primary Language English
Subjects Engineering
Journal Section Articles
Authors

Joy Morris This is me 0000-0003-2416-669X

Josip Smolcic This is me 0000-0002-7456-3100

Publication Date January 15, 2021
Published in Issue Year 2021

Cite

APA Morris, J., & Smolcic, J. (2021). Two families of graphs that are Cayley on nonisomorphic groups. Journal of Algebra Combinatorics Discrete Structures and Applications, 8(1), 53-57. https://doi.org/10.13069/jacodesmath.867644
AMA Morris J, Smolcic J. Two families of graphs that are Cayley on nonisomorphic groups. Journal of Algebra Combinatorics Discrete Structures and Applications. January 2021;8(1):53-57. doi:10.13069/jacodesmath.867644
Chicago Morris, Joy, and Josip Smolcic. “Two Families of Graphs That Are Cayley on Nonisomorphic Groups”. Journal of Algebra Combinatorics Discrete Structures and Applications 8, no. 1 (January 2021): 53-57. https://doi.org/10.13069/jacodesmath.867644.
EndNote Morris J, Smolcic J (January 1, 2021) Two families of graphs that are Cayley on nonisomorphic groups. Journal of Algebra Combinatorics Discrete Structures and Applications 8 1 53–57.
IEEE J. Morris and J. Smolcic, “Two families of graphs that are Cayley on nonisomorphic groups”, Journal of Algebra Combinatorics Discrete Structures and Applications, vol. 8, no. 1, pp. 53–57, 2021, doi: 10.13069/jacodesmath.867644.
ISNAD Morris, Joy - Smolcic, Josip. “Two Families of Graphs That Are Cayley on Nonisomorphic Groups”. Journal of Algebra Combinatorics Discrete Structures and Applications 8/1 (January 2021), 53-57. https://doi.org/10.13069/jacodesmath.867644.
JAMA Morris J, Smolcic J. Two families of graphs that are Cayley on nonisomorphic groups. Journal of Algebra Combinatorics Discrete Structures and Applications. 2021;8:53–57.
MLA Morris, Joy and Josip Smolcic. “Two Families of Graphs That Are Cayley on Nonisomorphic Groups”. Journal of Algebra Combinatorics Discrete Structures and Applications, vol. 8, no. 1, 2021, pp. 53-57, doi:10.13069/jacodesmath.867644.
Vancouver Morris J, Smolcic J. Two families of graphs that are Cayley on nonisomorphic groups. Journal of Algebra Combinatorics Discrete Structures and Applications. 2021;8(1):53-7.