The automorphism groups of some token graphs
DOI:
https://doi.org/10.22199/issn.0717-6279-5954Keywords:
token graphs, automorphism groups, Johnson graphsAbstract
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.
References
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., Graph theory, Combinatorics, Algorithms, and Applications, pp. 472-485. SIAM, Philadelphia, 1991.
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, 1993.
H. de Alba, W. Carballosa, J. Lea nos and L. M. Rivera, “Independence and matching numbers of some token graphs”, Australas. J. Combin, vol. 76, no. 3, pp. 387-403, 2020.
A. Alzaga, R. Iglesias, and R. Pignol, “Spectra of symmetric powers of graphs and the Weisfeiler-Lehman refinements”, J. Comb. Theory B, vol. 100, no. 6, pp. 671-682, 2010.
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 Mathematics, vol. 118, no. 23, pp. 343-351, 2018.
W. Carballosa, R. Fabila-Monroy, J. Leaños and L. M. Rivera, “Regularity and planarity of token graphs”, Discuss. Math. Graph Theory, vol. 37, no. 3, pp. 573-586, 2017.
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. 1, pp. 265-268, 2020.
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, 2012.
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 Appl. Math., vol. 247, pp. 327-340, 2018.
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, Art ID. 071901.
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.
Published
How to Cite
Issue
Section
Copyright (c) 2023 Sofía Ibarra, Luis Manuel Rivera
This work is licensed under a Creative Commons Attribution 4.0 International License.
-
Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.
