Cycles through subsets with large degree sums
Cycles through subsets with large degree sums
复制标题
循环遍历具有大度数和的子集
DOI：
10.1016/s0012-365x(96)00071-4
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
H. J. Veldman
中科院分区：
文献类型：
--
作者：
H. Broersma;Hao Li;Jianping Li;F. Tian;H. J. Veldman
设G是一个有n个顶点的2连通图，设X⊥V(G)。如果G有一个X环，即一个包含X的所有顶点的环，我们说G是X可循环的。我们用α(X)表示由X引起的G的子图G[X]中成对非相邻顶点的最大数目。如果G[X]不完全，我们用κ(X)表示分隔X的两个顶点的G的一组顶点的最小基数。用σ3(X)求出X上任意三个不相邻顶点的度数和（在G中）的最小值。我们的第一个主要结果是下述关于Bauer等人在哈密顿图上的结果的X可循环性的推广。如果σ3(X)大于或等于n + mingk(X), δ(X)，则G是X可循环的。我们的第二个主要结果是下面对富尼耶结果的推广。若α(X)≥κ(X)，则G是X可循环的。我们给出了一些其他已知结果的推广，从而推广了Veldman最近的一些结果。
Let G be a 2-connected graph on n vertices and let X ⊆ V(G). We say that G is X-cyclable if G has an X-cycle, i.e., a cycle containing all vertices of X. We denote by α(X) the maximum number of pairwise nonadjacent vertices in the subgraph G[X] of G induced by X. If G[X] is not complete, we denote by κ(X) the minimum cardinality of a set of vertices of G separating two vertices of X. By δ(X) we denote the minimum degree (in G) of the vertices of X, and by σ3(X) the minimum value of the degree sum (in G) of any three pairwise nonadjacent vertices of X. Our first main result is the following extension in terms of X-cyclability of a result on hamiltonian graphs by Bauer et al. If σ3(X) ⩾ n + mingk(X), δ(X), then G is X-cyclable. Our second main result is the following generalization of a result of Fournier. If α(X) ⩽ κ(X), then G is X-cyclable. We give a number of extensions of other known results, thereby generalizing some recent results of Veldman.