论文标题
循环凸度和隧道数量的链接
Cycle convexity and the tunnel number of links
论文作者
论文摘要
在这项工作中，我们介绍了一个新的图凸度，我们称之为循环凸度，这是由结理论中相关概念激励的。 对于图$ g =（v，e）$，将周期中的间隔函数定义为$ i_ {cc}（s）= s \ cup \ {v \ in v（g）\ in v（g）\ mid \ text {有周期} cy} c \ text c \ text {in} g \ text {in} g \ text { $ s \ subseteq v（g）$。我们说，如果$ i_ {cc}（s）= s $，$ s \ subseteq v（g）$是凸。 $ s \ subseteq v（g）$的凸壳，由$ hull（s）$表示，是包含在包含的最小凸套装$ s'U $，因此$ s \ subseteq s'$。如果$ hull（s）= v（g）$，则设置$ s \ subseteq v（g）$称为船体集。周期内的$ g $的船体数，用$ hn_ {cc}（g）$表示，是$ g $的最小船体集的基数。 我们首先提出引入这种凸度及其相关船体数量的动机。然后，我们证明了：4型平面图的船体数量最多是其顶点的一半；计算平面图的船体数是$ NP $ - complete问题；可以在多项式时间内完成计算和弦图的船体Humber，$ p_4 $ -sparse图和网格。
In this work, we introduce a new graph convexity, that we call Cycle Convexity, motivated by related notions in Knot Theory. For a graph $G=(V,E)$, define the interval function in the Cycle Convexity as $I_{cc}(S) = S\cup \{v\in V(G)\mid \text{there is a cycle }C\text{ in }G\text{ such that } V(C)\setminus S=\{v\}\}$, for every $S\subseteq V(G)$. We say that $S\subseteq V(G)$ is convex if $I_{cc}(S)=S$. The convex hull of $S\subseteq V(G)$, denoted by $Hull(S)$, is the inclusion-wise minimal convex set $S'$ such that $S\subseteq S'$. A set $S\subseteq V(G)$ is called a hull set if $Hull(S)=V(G)$. The hull number of $G$ in the cycle convexity, denoted by $hn_{cc}(G)$, is the cardinality of a smallest hull set of $G$. We first present the motivation for introducing such convexity and the study of its related hull number. Then, we prove that: the hull number of a 4-regular planar graph is at most half of its vertices; computing the hull number of a planar graph is an $NP$-complete problem; computing the hull humber of chordal graphs, $P_4$-sparse graphs and grids can be done in polynomial time.
