论文标题
覆盖良好的令牌图
Well-covered Token Graphs
论文作者
论文摘要
$ k $ -token Graph $ t_k（g）$是图形的顶点是图形$ g $的$ k $ -subsets，如果它们的对称差为$ g $，则两个顶点为$ t_k（g）$。当$ t_k（g）$是一张覆盖良好的图表时，我们将探索，也就是说，当它的所有最大独立集都具有相同的基数时。对于双方图$ g $，我们将$ t_k（g）$进行精心覆盖时进行分类。对于任意图$ g $，我们表明，如果$ t_2（g）$覆盖了，那么$ g $的围栏最多是四个。我们在$ t_k（g）$的独立性数字上包括上限和下限，并为一些覆盖的令牌图提供了一些家庭。
The $k$-token graph $T_k(G)$ is the graph whose vertices are the $k$-subsets of vertices of a graph $G$, with two vertices of $T_k(G)$ adjacent if their symmetric difference is an edge of $G$. We explore when $T_k(G)$ is a well-covered graph, that is, when all of its maximal independent sets have the same cardinality. For bipartite graphs $G$, we classify when $T_k(G)$ is well-covered. For an arbitrary graph $G$, we show that if $T_2(G)$ is well-covered, then the girth of $G$ is at most four. We include upper and lower bounds on the independence number of $T_k(G)$, and provide some families of well-covered token graphs.
