Find in Library

Let <i>G</i> be a simple graph of order <i>n</i> with vertex set <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>V</mi><mo>(</mo><mi>G</mi><mo>)</mo></mrow></semantics></math></inline-formula> and edge set <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>E</mi><mo>(</mo><mi>G</mi><mo>)</mo></mrow></semantics></math></inline-formula>, and let <i>k</i> be an integer such that <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>1</mn><mo>≤</mo><mi>k</mi><mo>≤</mo><mi>n</mi><mo>−</mo><mn>1</mn></mrow></semantics></math></inline-formula>. The <i>k</i>-token graph <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msup><mi>G</mi><mrow><mo>{</mo><mi>k</mi><mo>}</mo></mrow></msup></semantics></math></inline-formula> of <i>G</i> is the graph whose vertices are the <i>k</i>-subsets of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>V</mi><mo>(</mo><mi>G</mi><mo>)</mo></mrow></semantics></math></inline-formula>, where two vertices <i>A</i> and <i>B</i> are adjacent in <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msup><mi>G</mi><mrow><mo>{</mo><mi>k</mi><mo>}</mo></mrow></msup></semantics></math></inline-formula> whenever their symmetric difference <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>A</mi><mo>▵</mo><mi>B</mi></mrow></semantics></math></inline-formula>, defined as <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>(</mo><mi>A</mi><mo>∖</mo><mi>B</mi><mo>)</mo><mo>∪</mo><mo>(</mo><mi>B</mi><mo>∖</mo><mi>A</mi><mo>)</mo></mrow></semantics></math></inline-formula>, is a pair <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>{</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo>}</mo></mrow></semantics></math></inline-formula> of adjacent vertices in <i>G</i>. In this paper we study the Hamiltonicity of the <i>k</i>-token graphs of some join graphs. We provide an infinite family of graphs, containing Hamiltonian and non-Hamiltonian graphs, for which their <i>k</i>-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 <i>k</i>-token graphs, for any <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>2</mn><mo><</mo><mi>k</mi><mo><</mo><mi>n</mi><mo>−</mo><mn>2</mn></mrow></semantics></math></inline-formula>.