Independence numbers of the 2-token graphs of some join graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909620991164416 |
|---|---|
| author | Rivera, Luis Manuel Briones, Gerardo Vazquez |
| author_facet | Rivera, Luis Manuel Briones, Gerardo Vazquez |
| contents | 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}'$ of $F_2(G)$ from an independent set ${\mathcal I}$ of $F_2(G)$ such that $|{\mathcal I}'| \geq |{\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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_17419 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Independence numbers of the 2-token graphs of some join graphs Rivera, Luis Manuel Briones, Gerardo Vazquez Combinatorics 05C69, 05C76 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}'$ of $F_2(G)$ from an independent set ${\mathcal I}$ of $F_2(G)$ such that $|{\mathcal I}'| \geq |{\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$. |
| title | Independence numbers of the 2-token graphs of some join graphs |
| topic | Combinatorics 05C69, 05C76 |
| url | https://arxiv.org/abs/2505.17419 |