The 2-token graph <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40590_2025_773_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="44" /> </InlineMediaObject> <EquationSource Format="TEX">$F_2(G)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>F</mi> <mn>2</mn> </msub> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> of a graph G is the graph whose set of vertices consists of all the 2-subsets of V(G), where two vertices are adjacent if and only if their symmetric difference is an edge in G. Let G be the join graph of <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40590_2025_773_Article_IEq2.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="22" /> </InlineMediaObject> <EquationSource Format="TEX">$E_n$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>E</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation> and H, where H is any graph. In this paper, we give a method to construct an independent set <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40590_2025_773_Article_IEq3.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="17" /> </InlineMediaObject> <EquationSource Format="TEX">${\mathcal {I}}'$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mrow> <mi mathvariant="script">I</mi> </mrow> <mo>′</mo> </msup> </math></EquationSource> </InlineEquation> of <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40590_2025_773_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="44" /> </InlineMediaObject> <EquationSource Format="TEX">$F_2(G)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>F</mi> <mn>2</mn> </msub> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> from an independent set <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40590_2025_773_Article_IEq5.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="14" /> </InlineMediaObject> <EquationSource Format="TEX">${\mathcal {I}}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">I</mi> </math></EquationSource> </InlineEquation> of <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40590_2025_773_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="44" /> </InlineMediaObject> <EquationSource Format="TEX">$F_2(G)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>F</mi> <mn>2</mn> </msub> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> such that <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40590_2025_773_Article_IEq7.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="73" /> </InlineMediaObject> <EquationSource Format="TEX">$|{\mathcal {I}}'| \ge |{\mathcal {I}}|$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mo stretchy="false">|</mo> </mrow> <msup> <mrow> <mi mathvariant="script">I</mi> </mrow> <mo>′</mo> </msup> <mrow> <mo stretchy="false">|</mo> <mo>≥</mo> <mo stretchy="false">|</mo> <mi mathvariant="script">I</mi> <mo stretchy="false">|</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>. As an application, we obtain the independence number of the 2-token graphs of fan graphs <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40590_2025_773_Article_IEq8.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="34" /> </InlineMediaObject> <EquationSource Format="TEX">$F_{n, m}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>F</mi> <mrow> <mi>n</mi> <mo>,</mo> <mi>m</mi> </mrow> </msub> </math></EquationSource> </InlineEquation>, wheel graphs <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40590_2025_773_Article_IEq9.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="39" /> </InlineMediaObject> <EquationSource Format="TEX">$W_{n, m}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>W</mi> <mrow> <mi>n</mi> <mo>,</mo> <mi>m</mi> </mrow> </msub> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq10"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40590_2025_773_Article_IEq10.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="64" /> </InlineMediaObject> <EquationSource Format="TEX">$E_n+K_n$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>E</mi> <mi>n</mi> </msub> <mo>+</mo> <msub> <mi>K</mi> <mi>n</mi> </msub> </mrow> </math></EquationSource> </InlineEquation>.

Independence numbers of the 2-token graphs of some join graphs

期刊论文
发表日期：

2025年7月15日

查看全文

Luis Manuel Rivera,
Gerardo Vazquez Briones

摘要

The 2-token graph $F_2(G)$ $F_{2} (G)$ of a graph G is the graph whose set of vertices consists of all the 2-subsets of V(G), where two vertices are adjacent if and only if their symmetric difference is an edge in G. Let G be the join graph of $E_n$ $E_{n}$ and H, where H is any graph. In this paper, we give a method to construct an independent set ${\mathcal {I}}'$ $I^{'}$ of $F_2(G)$ $F_{2} (G)$ from an independent set ${\mathcal {I}}$ $I$ of $F_2(G)$ $F_{2} (G)$ such that $|{\mathcal {I}}'| \ge |{\mathcal {I}}|$ $| I^{'} | \geq | I |$ . As an application, we obtain the independence number of the 2-token graphs of fan graphs $F_{n, m}$ $F_{n, m}$ , wheel graphs $W_{n, m}$ $W_{n, m}$ and $E_n+K_n$ $E_{n} + K_{n}$ .