论文标题
大地凸和旋转图
Geodetic convexity and Kneser graphs
论文作者
论文摘要
对于正整数$ n $和$ k $，{\ em kneser graph} $ k（2n+k，n）$是图$ g =（v，e）$，以至于$ v = = \ {s \ subseteq \ {1，\ ldots，\ ldots，\ ldots，2n+k \} v = \ emptyset $。 Kneser图具有一个不错的组合结构，并且已经确定了许多参数，例如直径，色数，独立数，以及最近的船体编号（在$ P_3 $ -Convexity的上下文中）。然而，在旋塞图中测定测量凸的参数仍然保持开放。在这项工作中，我们研究了Geodetic数字和Geodetic Hull图形的数量。我们给出上限，并确定直径两的旋塞图（形成非平凡的亚科）的这些参数的确切值。我们证明，直径二的旋转图的大地船体数为两个，除了$ k（5,2）$，$ k（6,2）$和$ k（8,2）$，它们的地球船体数字三。我们还通过呈现$ K（2n+k，n）$中直径路径的端点的特征来为对旋塞图的知识做出了贡献，该端点用作获得这项工作中一些主要结果的工具。
The {\em Kneser graph} $K(2n+k,n)$, for positive integers $n$ and $k$, is the graph $G=(V,E)$ such that $V=\{S\subseteq\{1,\ldots,2n+k\} : |S|=n\}$ and there is an edge $uv\in E$ whenever $u\cap v=\emptyset$. Kneser graphs have a nice combinatorial structure, and many parameters have been determined for them, such as the diameter, the chromatic number, the independence number, and, recently, the hull number (in the context of $P_3$-convexity). However, the determination of geodetic convexity parameters in Kneser graphs still remained open. In this work, we investigate both the geodetic number and the geodetic hull number of Kneser graphs. We give upper bounds and determine the exact value of these parameters for Kneser graphs of diameter two (which form a nontrivial subfamily). We prove that the geodetic hull number of a Kneser graph of diameter two is two, except for $K(5,2)$, $K(6,2)$, and $K(8,2)$, which have geodetic hull number three. We also contribute to the knowledge on Kneser graphs by presenting a characterization of endpoints of diametral paths in $K(2n+k,n)$, used as a tool for obtaining some of the main results in this work.
