TY - JOUR
TI - Aproximating the maximum size of a K-regular induced subgraph by an upper bound on the co k-plex number
T2 - Journal of Mathematical Sciences
VL - 182
IS - 2
SN - 1072-3374
SP - 216-226
PY - 2010
AU - C. J. Luz
AB - 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 [3]. 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 [8]. Finally, some computational experiments performed to appraise the gains brought by ϑ^k are reported.
ER -