{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T21:22:34Z","timestamp":1773436954263,"version":"3.50.1"},"reference-count":32,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T00:00:00Z","timestamp":1623801600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>Let G be a simple graph of order n with vertex set V(G) and edge set E(G), and let k be an integer such that 1\u2264k\u2264n\u22121. The k-token graph G{k} of G is the graph whose vertices are the k-subsets of V(G), where two vertices A and B are adjacent in G{k} whenever their symmetric difference A\u25b5B, defined as (A\u2216B)\u222a(B\u2216A), is a pair {a,b} of adjacent vertices in G. In this paper we study the Hamiltonicity of the k-token graphs of some join graphs. We provide an infinite family of graphs, containing Hamiltonian and non-Hamiltonian graphs, for which their k-token graphs are Hamiltonian. Our result provides, to our knowledge, the first family of non-Hamiltonian graphs for which it is proven the Hamiltonicity of their k-token graphs, for any 2&lt;k&lt;n\u22122.<\/jats:p>","DOI":"10.3390\/sym13061076","type":"journal-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T21:58:32Z","timestamp":1623880712000},"page":"1076","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Hamiltonicity of Token Graphs of Some Join Graphs"],"prefix":"10.3390","volume":"13","author":[{"given":"Luis Enrique","family":"Adame","sequence":"first","affiliation":[{"name":"Unidad Acad\u00e9mica de Matem\u00e1ticas, Universidad Aut\u00f3noma de Zacatecas, Zacatecas 98066, Mexico"}]},{"given":"Luis Manuel","family":"Rivera","sequence":"additional","affiliation":[{"name":"Unidad Acad\u00e9mica de Matem\u00e1ticas, Universidad Aut\u00f3noma de Zacatecas, Zacatecas 98066, Mexico"}]},{"given":"Ana Laura","family":"Trujillo-Negrete","sequence":"additional","affiliation":[{"name":"Departamento de Matem\u00e1ticas, Cinvestav, Mexico City 07360, Mexico"}]}],"member":"1968","published-online":{"date-parts":[[2021,6,16]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1109\/TIT.1962.1057714","article-title":"A new upper bound for error-correcting codes","volume":"8","author":"Johnson","year":"1962","journal-title":"IRE Trans. Inform. Theory"},{"key":"ref_2","unstructured":"Alavi, Y., Behzad, M., and Simpson, J.E. (1991). Planarity of double vertex graphs. Graph Theory, Combinatorics, Algorithms, and Applications, SIAM."},{"key":"ref_3","first-page":"37","article-title":"Double vertex graphs","volume":"16","author":"Alavi","year":"1991","journal-title":"J. Comb. Inform. Syst. Sci."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"709","DOI":"10.1007\/s003730200055","article-title":"Survey of double vertex graphs","volume":"18","author":"Alavi","year":"2002","journal-title":"Graphs Comb."},{"key":"ref_5","first-page":"65","article-title":"Hamiltonian cycles in double vertex graphs of bipartite graphs","volume":"93","author":"Alavi","year":"1993","journal-title":"Congr. Numer."},{"key":"ref_6","first-page":"97","article-title":"n-Tuple vertex graphs","volume":"89","author":"Zhu","year":"1992","journal-title":"Congr. Numer."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1016\/j.jctb.2006.04.002","article-title":"Symmetric squares of graphs","volume":"97","author":"Audenaert","year":"2007","journal-title":"J. Comb. Theory B"},{"key":"ref_8","unstructured":"Rudolph, T. (2002). Constructing physically intuitive graph invariants. arXiv."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1090\/conm\/741\/14921","article-title":"A Schr\u00f6dinger operator approach to higher spin XXZ systems on general graphs. Analytic Trends in Mathematical Physics","volume":"741","author":"Fischbacher","year":"2020","journal-title":"Contemp. Math."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"051901","DOI":"10.1063\/1.5023216","article-title":"Droplet states in quantum XXZ spin systems on general graphs","volume":"59","author":"Fischbacher","year":"2018","journal-title":"J. Math. Phys."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"071901","DOI":"10.1063\/1.5084136","article-title":"Computing spectral bounds of the Heisenberg ferromagnet from geometric considerations","volume":"60","author":"Ouyang","year":"2019","journal-title":"J. Math. Phys."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/s00373-011-1055-9","article-title":"Token graphs","volume":"28","author":"Huemer","year":"2012","journal-title":"Graph Comb."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"573","DOI":"10.7151\/dmgt.1959","article-title":"Regularity and planarity of token graphs","volume":"37","author":"Carballosa","year":"2017","journal-title":"Discuss. Math. Graph Theory"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1016\/j.laa.2021.05.005","article-title":"On the Laplacian spectra of token graphs","volume":"625","author":"Duque","year":"2021","journal-title":"Linear Algebra Appl."},{"key":"ref_15","first-page":"310","article-title":"Characterization of token graphs","volume":"6","author":"Deepalakshmi","year":"2017","journal-title":"J. Eng. Technol."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/j.akcej.2019.05.002","article-title":"On the 2-token graph of a graph","volume":"17","author":"Deepalakshmi","year":"2020","journal-title":"AKCE Int. J. Graphs Comb."},{"key":"ref_17","unstructured":"Fabila-Monroy, R., nos, J.L., and Trujillo-Negrete, A.L. (2020). On the Connectivity of Token Graphs of Trees. arXiv."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1016\/j.dam.2018.03.085","article-title":"The packing number of the double vertex graph of the path graph","volume":"247","author":"Rivera","year":"2018","journal-title":"Discret. Appl. Math."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"1013","DOI":"10.1007\/s00373-021-02301-0","article-title":"The edge-connectivity of token graphs","volume":"37","author":"Ndjatchi","year":"2021","journal-title":"Graphs Comb."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"777","DOI":"10.1007\/s00373-018-1913-9","article-title":"The connectivity of token graphs","volume":"34","year":"2018","journal-title":"Graphs Comb."},{"key":"ref_21","first-page":"387","article-title":"Independence and matching number of some token graphs","volume":"76","author":"Carballosa","year":"2020","journal-title":"Australas. J. Comb."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1007\/s13226-015-0119-6","article-title":"On the Hamiltonicity of random bipartite graphs","volume":"46","author":"Shang","year":"2015","journal-title":"Indian J. Pure Appl. Math."},{"key":"ref_23","unstructured":"Garey, M.R., and Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Alhevaz, A., Baghipur, M., Ganie, H.A., and Shang, Y. (2020). The Generalized Distance Spectrum of the Join of Graphs. Symmetry, 12.","DOI":"10.3390\/sym12010169"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"1311","DOI":"10.1007\/s00010-014-0324-0","article-title":"Hyperbolicity in the corona and join of graphs","volume":"89","author":"Carballosa","year":"2015","journal-title":"Aequ. Math."},{"key":"ref_26","first-page":"723451","article-title":"Mathematical Properties of the Hyperbolicity of Circulant Networks","volume":"2015","author":"Sigarreta","year":"2015","journal-title":"Adv. Math. Phys."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"1429","DOI":"10.1142\/S0219749909006103","article-title":"Quantum Perfect State Transfer on Weighted Join Graphs","volume":"7","author":"Norton","year":"2009","journal-title":"Int. J. Quantum Inf."},{"key":"ref_28","first-page":"#P07","article-title":"Hamiltonicity of token graphs of fan graphs","volume":"1","author":"Rivera","year":"2018","journal-title":"Art Discr. Appl. Math."},{"key":"ref_29","unstructured":"West, D.B. (2001). Introduction to Graph Theory, Pearson Education. [2nd ed.]."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"353","DOI":"10.2307\/3617115","article-title":"Knotted doughnuts and other mathematical entertainments, by Martin Gardner","volume":"71","author":"Baylis","year":"1987","journal-title":"Math. Gaz."},{"key":"ref_31","unstructured":"Ruskey, F. (2003). Combinatorial Generation, University of Victoria. Preliminary Working Draft."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"605","DOI":"10.1137\/S0036144595295272","article-title":"A survey of combinatorial Gray codes","volume":"39","author":"Savage","year":"1997","journal-title":"SIAM Rev."}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/13\/6\/1076\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T06:16:44Z","timestamp":1760163404000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/13\/6\/1076"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,16]]},"references-count":32,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2021,6]]}},"alternative-id":["sym13061076"],"URL":"https:\/\/doi.org\/10.3390\/sym13061076","relation":{},"ISSN":["2073-8994"],"issn-type":[{"value":"2073-8994","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,6,16]]}}}