| Summary: | 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 <cite>CardKamLoz</cite>. 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 <cite>Luzkind</cite>. Finally, some computational experiments perfomed to appraise the gains brought by ϑ_{k} are reported.
|
|---|