





















In this paper we give a new generalization of token graphs. Given two integers $1\leq m \leq k$ and a graph $G$ we define the generalized token graph of the graph $G$, to be the graph $F_k^m(G)$ whose vertices correspond to configurations of $k$ indistinguishable tokens placed at distinct vertices of $G$, where two configurations are adjacent whenever one configuration can be reached from the other by moving $m$ tokens along $m$ edges of $G$. When $m=1$, the usual token graph $F_k(G)$ is recovered. We give sufficient and necessary conditions on the graph $G$ for $F_2^2(G)$ to be connected and we give sufficient and necessary conditions on the graph $G$ for $F_2^2(G)$ to be bipartite. We also analyze some properties of generalized token graphs, such as clique number, chromatic number, independence number and domination number. Finally, we conclude with an analysis of the automorphism group of the generalized token graph.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。