Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. On the Connectivity ...
Article

On the Connectivity of Token Graphs of Trees

Ruy Fabila-Monroy, Jesús Leaños, Ana Laura Trujillo-Negrete ORCID
Download article
Open on arXiv
Submitted on
June 2, 2021
Accepted on
February 14, 2022
Published on
March 30, 2022
Last modified on
March 31, 2025
Volume 24
vol. 24:1
Graph Theory
DOI
10.46298/dmtcs.7538
License
arXiv.org - Non-exclusive license to distribute
Indicators
1791
Views
1338
Downloads

On the Connectivity of Token Graphs of Trees

Ruy Fabila-Monroy, Jesús Leaños, Ana Laura Trujillo-Negrete ORCID
Abstract
Let $k$ and $n$ be integers such that $1\leq k \leq n-1$, and let $G$ be a simple graph of order $n$. The $k$-token graph $F_k(G)$ of $G$ is the graph whose vertices are the $k$-subsets of $V(G)$, where two vertices are adjacent in $F_k(G)$ whenever their symmetric difference is an edge of $G$. In this paper we show that if $G$ is a tree, then the connectivity of $F_k(G)$ is equal to the minimum degree of $F_k(G)$.
Keywords
  • Mathematics - Combinatorics
  • 05C40, 05C76
Mathematics Subject Classification 2020
  • 05C05 - Trees
  • 05C07 - Vertex degrees
  • 05C40 - Connectivity
Cited by

Source: OpenCitations

  • On the packing number of $ 3 $-token graph of the path graph $ P_n $

    AIMS Mathematics

    Authors : Christophe Ndjatchi ORCID, Joel Alejandro Escareño Fernández ORCID, L. M. Ríos-Castro ORCID, Teodoro Ibarra-Pérez ORCID, Hans Christian Correa-Aguado ORCID, Hugo Pineda Martínez

    Journal reference : Volume 9, 2024, pp. 11644-11659

    DOI : 10.3934/math.2024571

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

    Boletín de la Sociedad Matemática Mexicana

    Authors : Luis Manuel Rivera ORCID, Gerardo Vazquez Briones

    Journal reference : Volume 31, 2025, pp.

    DOI : 10.1007/s40590-025-00773-1

  • On the automorphism group of token graphs of complete bipartite graphs

    Boletín de la Sociedad Matemática Mexicana

    Authors : Ruy Fabila-Monroy ORCID, Ana Trujillo-Negrete ORCID

    Journal reference : Volume 31, 2025, pp.

    DOI : 10.1007/s40590-025-00723-x

  • Automorphism Groups of 2-Token Graph of Cartesian Product of Two Cycles

    Graphs and Combinatorics

    Authors : Ju Zhang ORCID, Young Soo Kwon ORCID, Jin-Xin Zhou ORCID

    Journal reference : Volume 41, 2025, pp.

    DOI : 10.1007/s00373-025-02940-7
Preview
Loading PDF preview...