Aproximating the maximum size of a K-regular induced subgraph by an upper bound on the co k-plex number

• Type: Article in International Scientific Journal
• Date: 2010

Authors

C. J. Luz (Author) Other

Journal

Title: Journal of Mathematical Sciences

Vol. 182 No. 2

Pages: 216-226

ISSN: 1072-3374

Publisher: Springer Nature

Scientific classification

FOS: Natural sciences

Other information

Abstract (EN): 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.

Language: English

Type (Professor's evaluation): Scientific