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

Abstract

The $2$-token graph $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$ and $H$, where $H$ is any graph. In this paper, we give a method to construct an independent set ${\mathcal{I}}^{\prime }$ of $F_2(G)$ from an independent set $\mathcal{I}$ of $F_2(G)$ such that $|{\mathcal{I}}^{\prime }|\ge |\mathcal{I}|$. As an application, we obtain the independence number of the $2$-token graphs of fan graphs $F_{n,m}$, wheel graphs $W_{n,m}$ and $E_n+K_n$.

12 pages