论文标题
关于朋友和trangers图的结构性方面
On Structural Aspects of Friends-And-Strangers Graphs
论文作者
论文摘要
给定两个图表$ x $和$ y $具有相同数量的顶点，朋友和trangers图$ \ mathsf {fs}（fs}（x，y）$都具有其顶点，从$ v（x）$到$ v（$ v（y）$），在$ v（y）$中，在$ nefencent $ nefencent $ et n. friend $ news $ n. $ y $。在本文中，我们研究了$ \ mathsf {fs}（x，y）$的必要条件，并从某些集合中连接所有图形$ x $。在我们采用$ x $的设置中，要从所有双连接图中绘制出$ x $，我们证明了$ \ mathsf {fs}（x，y）$连接到所有双连接的$ x $时，并且仅当$ \ overline {y} $是一棵具有共同竞争尺寸的树木的林中，这解决了防御者和克拉维兹的猜想。 We also initiate and make significant progress toward determining the girth of $\mathsf{FS}(X, \text{Star}_n)$ for connected graphs $X$, and in particular focus on the necessary trajectories that the central vertex of $\text{Star}_n$ takes around all such graphs $X$ to achieve the girth.
Given two graphs $X$ and $Y$ with the same number of vertices, the friends-and-strangers graph $\mathsf{FS}(X, Y)$ has as its vertices all $n!$ bijections from $V(X)$ to $V(Y)$, with bijections $σ, τ$ adjacent if and only if they differ on two elements of $V(X)$, whose mappings are adjacent in $Y$. In this article, we study necessary and sufficient conditions for $\mathsf{FS}(X, Y)$ to be connected for all graphs $X$ from some set. In the setting that we take $X$ to be drawn from the set of all biconnected graphs, we prove that $\mathsf{FS}(X, Y)$ is connected for all biconnected $X$ if and only if $\overline{Y}$ is a forest with trees of jointly coprime size; this resolves a conjecture of Defant and Kravitz. We also initiate and make significant progress toward determining the girth of $\mathsf{FS}(X, \text{Star}_n)$ for connected graphs $X$, and in particular focus on the necessary trajectories that the central vertex of $\text{Star}_n$ takes around all such graphs $X$ to achieve the girth.
