Improving an upper bound on the size of k-regular induced subgraphs
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 alpha (k) (G). From a well known Motzkin-Straus result, a relationship is deduced between alpha (k) (G) and the independence number alpha(G). Next, it is proved that the upper bounds upsilon (k) (G) introduced in Cardoso et al. (J. Comb. Optim., 14, 455-463, 2007) can easily be computed from upsilon (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 alpha (k) (G) improving upsilon (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.
graphs independent sets induced matchings combinatorial optimization