Regularity and Planarity of Token Graphs

• Autorzy: Walter Carballosa , Ruy Fabila-Monroy , Jesús Leaños , Luis Manuel Rivera
• Języki publikacji: EN

Abstrakty

EN

Let G = (V, E) be a graph of order n and let 1 ≤ k < n be an integer. The k-token graph of G is the graph whose vertices are all the k-subsets of V, two of which are adjacent whenever their symmetric difference is a pair of adjacent vertices in G. In this paper we characterize precisely, for each value of k, which graphs have a regular k-token graph and which connected graphs have a planar k-token graph.

Słowa kluczowe

EN

token graph; Johnson graph; regularity; planarity

Kategorie tematyczne

• 05C10: Planar graphs; geometric and topological aspects of graph theory
• 05C69: Dominating sets, independent sets, cliques

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2017
• Tom: 37
• Numer: 3
• Strony: 573-586

Daty

wydano

2017-08-01

otrzymano

2015-12-14

poprawiono

2016-05-26

zaakceptowano

2016-05-26

online

2017-07-06

Twórcy

autor

Walter Carballosa

• , , , FL

autor

Ruy Fabila-Monroy

• , ,

autor

Jesús Leaños

• , ,

autor

Luis Manuel Rivera

• , , Zac.,

Identyfikatory

DOI

10.7151/dmgt.1959