单和双圈图k-孤立数的上确界

Upper Bound on k-Isolation Number of Unicyclic and Bicyclic Graphs

摘要: 对一个自然数$k$ ，若简单无向图$G$ 的顶点子集$D$ 满足条件：减去$D$ 的闭邻域后得到的图$G-N\left[D\right]$ 不含$k+2$ 阶的星图$K_{1,k+1}$ 作为子图，则$D$ 被称为$G$ 的一个$k$ -孤立集。图$G$ 的最小一个$k$ -孤立集$D$ 的阶数被称为图$G$ 的$k$ -孤立数。本文得到了单和双圈图的$k$ -孤立数的上确界。

Abstract: For a natural number k, a vertex subset D of a simple undirected graph G satisfies the condition that the graph $G-N\left[D\right]$ obtained by removing the closed neighborhood of D does not contain the star graph $K_{1,k+1}$ of order $k+2$ as a subgraph, then it is calwled a k-isolating set of the graph. The minimum order of such a k-isolating set in a graph is referred to as the k-isolation number of the graph. This paper establishes the upper bound of the k-isolation numbers for unicyclic and bicyclic graphs.