论文标题
连接（$ c_4 $，钻石） - 免费图形从其令牌图中唯一可重建
Connected ($C_4$,Diamond)-free Graphs Are Uniquely Reconstructible from Their Token Graphs
论文作者
论文摘要
钻石是从$ 4 $顶点上删除完整图的边缘获得的图形。 A（$ c_4 $，钻石） - 免费图是一个图形，它不包含钻石或四个顶点上的循环，如诱导的子图。令$ g $为连接的（$ C_4 $，钻石） - $ n $顶点上的免费图。令$ 1 \ le K \ le n-1 $为整数。 $ k $ token图，$ f_k（g）$ of $ g $是其顶点的图形，其所有$ k $顶点的$ g $均为$ g $;其中两个是相邻的，如果它们的对称差为$ g $的一对相邻顶点。令$ f $为$ f_k（g）$的同构图。在本文中，我们表明只有$ f $，我们可以在多项式时间内构造同构至$ g $的图。令$ \ operatorname {aut}（g）$为$ g $的自动形态组。我们还表明，如果$ k \ neq n/2 $，则$ \ operatorName {aut}（g）\ simeq \ operatorName {aut}（aut}（f_k（g））$;如果$ k = n/2 $，则$ \ operatorname {aut}（g）\ simeq \ operatatorName {aut}（aut}（f_k（g））\ times \ times \ times \ mathbb {z} _2 $。
A diamond is the graph that is obtained from removing an edge from the complete graph on $4$ vertices. A ($C_4$,diamond)-free graph is a graph that does not contain a diamond or a cycle on four vertices as induced subgraphs. Let $G$ be a connected ($C_4$,diamond)-free graph on $n$ vertices. Let $1 \le k \le n-1$ be an integer. The $k$-token graph, $F_k(G)$, of $G$ is the graph whose vertices are all the sets of $k$ vertices of $G$; two of which are adjacent if their symmetric difference is a pair of adjacent vertices in $G$. Let $F$ be a graph isomorphic to $F_k(G)$. In this paper we show that given only $F$, we can construct in polynomial time a graph isomorphic to $G$. Let $\operatorname{Aut}(G)$ be the automorphism group of $G$. We also show that if $k\neq n/2$, then $\operatorname{Aut}(G) \simeq \operatorname{Aut}(F_k(G))$; and if $k = n/2$, then $\operatorname{Aut}(G) \simeq \operatorname{Aut}(F_k(G)) \times \mathbb{Z}_2$.
