The automorphism groups of some token graphs

• Ibarra, Sofía ^[2] ; Rivera, Luis Manuel ^[1]
  1. [1] Universidad Autónoma de Zacatecas

     Universidad Autónoma de Zacatecas

     México

     
  2. [2] Unidad Académica de Matemáticas.
• Localización: Proyecciones: Journal of Mathematics, ISSN 0716-0917, ISSN-e 0717-6279, Vol. 42, Nº. 6, 2023, págs. 1627-1651
• Idioma: inglés
• DOI: 10.22199/issn.0717-6279-5954
• Enlaces
  • Texto completo
• Resumen

  • The token graphs of graphs have been studied at least from the 80’s with different names and by different authors. The Johnson graph J(n, k) is isomorphic to the k-token graph of the complete graph Kn. To our knowledge, the unique results about the automorphism groups of token graphs are for the case of the Johnson graphs. In this paper we begin the study of the automorphism groups of token graphs of another graphs. In particular we obtain the automorphism group of the k-token graph of the path graph Pn, for n 6≠ 2k. Also, we obtain the automorphism group of the 2-token graph of the following graphs: cycle, star, fan and wheel graphs.

• Referencias bibliográficas
  • Y. Alavi, M. Behzad, P. Erdös, and D. R. Lick. “Double vertex graphs”. J. Combin. Inform. System Sci., vol. 16, no. 1, pp. 37-50, 1991.
  • Y. Alavi, M. Behzad, and J. E. Simpson, “Planarity of double vertex graphs”. In Y. Alavi, F.R. K. Chung, R. L. Graham, and D. Frank Hsu, Eds.,...
  • Y. Alavi, D. R. Lick and J. Liu. “Survey of double vertex graphs”, Graphs Combin., vol. 18, no, 4, pp. 709-715, 2002.
  • Y. Alavi, D. R. Lick and J. Liu, “Hamiltonian cycles in double vertex graphs of bipartite graphs”, Congr. Numerantium, vol. 93, pp. 65-72,...
  • H. de Alba, W. Carballosa, J. Lea nos and L. M. Rivera, “Independence and matching numbers of some token graphs”, Australas. J. Combin, vol....
  • A. Alzaga, R. Iglesias, and R. Pignol, “Spectra of symmetric powers of graphs and the Weisfeiler-Lehman refinements”, J. Comb. Theory B, vol....
  • K. Audenaert, C. Godsil, G. Royle, and T. Rudolph, “Symmetric squares of graphs”, J. Comb. Theory B, vol. 97, pp. 74-90, 2007.
  • A. R. Barghi and I. Ponomarenko, “Non-isomorphic graphs with cospectral symmetric powers”. Electr. J. Comb., vol. 16, no. 1, 2009.
  • C. Beaula, O. Venugopal and N. Padmapriya, “Graph distance of vertices in double vertex graphs”, International Journal of Pure and Applied...
  • W. Carballosa, R. Fabila-Monroy, J. Leaños and L. M. Rivera, “Regularity and planarity of token graphs”, Discuss. Math. Graph Theory, vol....
  • J. Deepalakshmi and G. Marimuthu, “Characterization of token graphs”, J. Eng. Technol., vol. 6, pp. 310-317, 2017.
  • J. Deepalakshmi, G. Marimuthu, A. Somasundaram and S. Arumugam, “On the 2-token graph of a graph”, AKCE Int. J. Graphs Comb., vol. 17, no....
  • M. M. Deza and E. Deza. Encyclopedia of distances, 2a ed., Springer, 2013.
  • R. Fabila-Monroy, D. Flores-Peñaloza, C. Huemer, F. Hurtado, J. Urrutia and D. R. Wood, “Token graphs”, Graphs Comb., Vol. 28 (3), pp. 365-380,...
  • C. Fischbacher and G. Stolz, “Droplet states in quantum XXZ spin systems on general graphs”, J. Math. Phys., vol. 59, no. 5, 2018.
  • J. M. Gómez Soto, J. Leaños, L. M. Ríos-Castro and L. M. Rivera, “The packing number of the double vertex graph of the path graph”, Discrete...
  • W. Heisenberg. “Zur Theorie des Ferromagnetismus”. Zeitschrift fur Physik, Vol. 49, pp. 619-636, 1928.
  • P. Jiménez-Sepúlveda and L. M. Rivera, “Independence numbers of some double vertex graphs and pair graphs”, arXiv: 1810.06354, 2018-
  • G. L. Johns, Generalized distance in graphs, Ph.D. Dissertation, Western Michigan University, 1988.
  • S. M. Johnson, “A new upper bound for error-correcting codes”, IRE Trans. Inform. Theory, vol. 8, no. 3, pp. 203-207, 1962.
  • G. A. Jones, “Automorphisms and regular embeddings of merged Johnson graphs”, European J. Combin., vol. 26, pp. 417-435, 2005.
  • J. Leaños and A. L. Trujillo-Negrete, “The connectivity of token graphs”, Graphs Comb., vol. 32, no. 4, pp. 777-790, 2018.
  • S. M. Mirafzal, “The automorphism group of the bipartite Kneser graph”, Proc. Math. Sci., vol. 129, no. 34 2019.
  • S. M. Mirafzal and A. Zafari, “Some algebraic properties of bipartite Kneser graphs”, Ars Comb., vol. 153, pp. 3-14, 2020.
  • S. Mirafzal and M. Ziaee, “Some algebraic aspects of enhanced Johnson graphs”, Acta Math. Univ. Comenianae, vol. 88, no. 2, pp. 257-266, 2019.
  • Y. Ouyang, “Computing spectral bounds of the Heisenberg ferromagnet from geometric considerations”, J. Math. Phys., vol. 60, no. 7, 2019,...
  • M. Ramras and E. Donovan, “The automorphism group of a Johnson graph”, SIAM J. Discrete Math., vol. 25, no. 1, pp. 267-273, 2011.
  • L. M. Rivera and A. L. Trujillo-Negrete, “Hamiltonicity of token graphs of fan graphs”, Art Discr. Appl. Math., vol. 1, no. 1, #P07, 2018.
  • T. Rudolph, “Constructing physically intuitive graph invariants”, arXiv: quant-ph/0206068, 2002.
  • N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, http://oeis.org.
  • B. Zhu, J. Liu, D. R. Lick, Y. Alavi, “n-Tuple vertex graphs”, Congr. Numerantium, vol. 89, pp. 97-106, 1992.