论文标题
Lollipop图和其他人的朋友和trangers图的连接性
The connectedness of the friends-and-strangers graph of lollipop graphs and others
论文作者
论文摘要
令$ x $和$ y $是订单$ n $的任何两个图。朋友和tragners图$ \ Mathsf {fs}（x，y）$ $ x $和$ y $的$是一个图形，其中包含所有bijections $σ：v（x）\ mapSto v（y）$，其中两个$σ$，$σ'$相互差异，并且在两个相邻的情况下，$ nivectice in sepertice in nys impertice intercections in n and immiessive at in niventice intercections。 $ y $相邻。人们可以询问这些朋友和纠缠的最根本的问题是它们是否已连接。令$ \ mathsf {Lollipop} _ {n-k，k} $为订单$ n $的棒棒糖图，通过识别订单$ n-k+1 $的一端，并具有完整的订单$ k $的顶点。 Defant和Kravitz开始研究$ \ Mathsf {fs}（\ Mathsf {Lollipop} _ {N-K，K}，Y）$的连接性。在本文中，我们给出了$ \ mathsf {fs}（\ Mathsf {lollipop} _ {n-k，k}，y）$的足够且必要的条件，以连接所有$ 2 \ leq k \ leq leq n $。
Let $X$ and $Y$ be any two graphs of order $n$. The friends-and-strangers graph $\mathsf{FS}(X,Y)$ of $X$ and $Y$ is a graph with vertex set consisting of all bijections $σ:V(X) \mapsto V(Y)$, in which two bijections $σ$, $σ'$ are adjacent if and only if they differ precisely on two adjacent vertices of $X$, and the corresponding mappings are adjacent in $Y$. The most fundamental question that one can ask about these friends-and-strangers graphs is whether or not they are connected. Let $\mathsf{Lollipop}_{n-k,k}$ be a lollipop graph of order $n$ obtained by identifying one end of a path of order $n-k+1$ with a vertex of a complete graph of order $k$. Defant and Kravitz started to study the connectedness of $\mathsf{FS}(\mathsf{Lollipop}_{n-k,k},Y)$. In this paper, we give a sufficient and necessary condition for $\mathsf{FS}(\mathsf{Lollipop}_{n-k,k},Y)$ to be connected for all $2\leq k\leq n$.
