论文标题
从顶点引起的子图的角度来看，关于令牌图的连通性和直径
On the connectivity and diameter of Token graphs from a vertex induced sub-graph perspective
论文作者
论文摘要
图形图形或对称的图形，请参见\ cite {alavi2002survey}和\ cite {fabila-monroy2012}，在$ k $ combinations上定义了一些图形$ l $的顶点的$ k $ combinations，其中两种图形$之间存在两种图形的$，如果它们的组合中存在两个$，则在其中$ nounds图中存在。已经注意到，例如在\ cite {audenaert200774}中，这些图构成了随机步行和图形不变性之间的关系，粒子系统与高阶图形属性之间的固有对应关系，特别是在角度诱导的子图中的结构。在这项工作中，我们通过对代币图的顶点连接的综合视角为这一观点做出了贡献，该角度等于其最小程度以及直径，如果基础图$ L $具有直径$ 2 $。 $ L $及其令牌图之间的集团 - 约翰逊图链路上的一些组合结果也得到了证明。
Token graphs, or symmetric powers of graphs, see \cite{alavi2002survey} and \cite{Fabila-Monroy2012}, are defined on the $k$-combinations of the vertex set of some graph $L$, where edges exist between two such combinations, if their symmetric difference corresponds to an edge in the underlying graph $L$. It has been noted, for example in \cite{AUDENAERT200774}, that these graphs constitute an inherent correspondence between the relationships between random walks and graph invariants, and particle systems and higher order graph properties, employing in particular the structure of vertex induced sub-graphs. In this work, we contribute to this perspective, by giving a synthetic perspective on the vertex connectivity of token graphs, which equals its minimal degree, as well as on their diameter, if the underlying graph $L$ has diameter $2$. Some combinatorial results on the clique-Johnson graph link between $L$ and its token graph are proven as well.
