论文标题
定期距离的图表 - $ 2 $图形
A characterization of graphs with regular distance-$2$ graphs
论文作者
论文摘要
对于非阴性整数〜$ k $，我们考虑每个顶点在距离上完全具有$ k $的顶点〜$ 2 $，即距离的图形，其距离为$ 2 $ graphs为$ k $ regular。我们称之为$ k $ metAmour triminology in polyamory中的动机。 虽然构建$ k $ - metamour-regular图表相对容易 - 我们为任意〜$ k $提供了通用的结构 - 找到所有这些图形都更具挑战性。我们表明，只有$ k $ - metamour-formular图形没有特定属性的构造。此外，我们得出了$ k $ -metAmour-regular图表的完整表征，每个$ k = 0 $，$ k = 1 $和$ k = 2 $。特别是，当且仅当$ n \ ge5 $且图形是循环中的一个连接时，带有〜$ n $顶点的连接图为$ 2 $ - metamour-regular（仅当每个顶点都具有〜$ n-3 $），一个周期，或17美元的$ n \ n \ n \ le8 $ 8 $的$ 17 $。此外，每个顶点最多都有一个metamour的图表的表征。每个表征都伴随着对未标记图的相应计数序列的研究。
For non-negative integers~$k$, we consider graphs in which every vertex has exactly $k$ vertices at distance~$2$, i.e., graphs whose distance-$2$ graphs are $k$-regular. We call such graphs $k$-metamour-regular motivated by the terminology in polyamory. While constructing $k$-metamour-regular graphs is relatively easy -- we provide a generic construction for arbitrary~$k$ -- finding all such graphs is much more challenging. We show that only $k$-metamour-regular graphs with a certain property cannot be built with this construction. Moreover, we derive a complete characterization of $k$-metamour-regular graphs for each $k=0$, $k=1$ and $k=2$. In particular, a connected graph with~$n$ vertices is $2$-metamour-regular if and only if $n\ge5$ and the graph is a join of complements of cycles (equivalently every vertex has degree~$n-3$), a cycle, or one of $17$ exceptional graphs with $n\le8$. Moreover, a characterization of graphs in which every vertex has at most one metamour is acquired. Each characterization is accompanied by an investigation of the corresponding counting sequence of unlabeled graphs.
