Approximating the maximum size of a k-regular induced subgraph by an upper bound on the co-k-plex number - Luz, C.J. (2012)
Let α_{k} and α_{k} denote respectively the maximum cardinality k-regular induced subgraph and the co-k-plex number of a given graph. In this paper a convex quadratic programming upper bound on α_{k} which is also an upper bound on α_{k} will be introduced. The new bound, denoted by υ_{k}, improves on the bound υ_{k} given in CardKamLoz. For regular graphs, a necessary and sufficient condition under which υ_{k} equals υ_{k} is proved. It is also shown that the graphs for which α_{k} equals υ_{k} coincide with those such that α_{k} equals υ_{k}. Next, an improvement of υ_{k} denoted by ϑ_{k} is proposed, which is not worse than the upper bound ϑ_{k} for α_{k} introduced in Luzkind. Finally, some computational experiments perfomed to appraise the gains brought by ϑ_{k} are reported.