This paper considers the NP-hard graph problem of determining a maximum cardinality subset of vertices inducing a k-regular subgraph. For any graph G, this maximum will be denoted by α k (G). From a well known Motzkin-Straus result, a relationship is deduced between α k (G) and the independence number α(G). Next, it is proved that the upper bounds υ k (G) introduced in Cardoso et al. (J. Comb. Optim., 14, 455–463, 2007) can easily be computed from υ 0(G), for any positive integer k. This relationship also allows one to present an alternative proof of the Hoffman bound extension introduced in the above paper. The paper continues with the introduction of a new upper bound on α k (G) improving υ k (G). Due to the difficulty of computing this improved bound, two methods are provided for approximating it. Finally, some computational experiments which were performed to compare all bounds studied are reported.
展开▼
机译：本文考虑了确定诱导k正则子图的顶点的最大基数子集的NP硬图问题。对于任何图G，此最大值将由α k （G）表示。根据众所周知的Motzkin-Straus结果，推导出α k （G）与独立数α（G）之间的关系。接下来，证明了Cardoso等人引入的上限υ k （G）。 （J. Comb。Optim。，14，455–463，2007）可以很容易地从υ 0 （G）计算任意正整数k。这种关系也使人们可以提出上述论文中霍夫曼界扩展的另一种证明。本文继续介绍α k （G）的新上限，以改善υ k （G）。由于难以计算此改进的边界，因此提供了两种近似方法。最后，报告了一些用于比较所有研究范围的计算实验。
展开▼
