Let α k and α^k denote respectively the maximum cardinality of a k-regular induced subgraph and the co-k-plex number of a given graph. In this paper, we introduce a convex quadratic programming upper bound on α^k , which is also an upper bound on α k . The new bound denoted by υ^k improves the bound υ k given in . For regular graphs, we prove a necessary and sufficient condition under which υ^k equals υ k . We also show 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 . Finally, some computational experiments performed to appraise the gains brought by ϑ^k are reported.
Type (Professor's evaluation):