Abstract:
Recently, approximation solution methods are used for some problems of graphs. These are the minimum dominating set, maximum independent set, maximum clique, perfect matching, Hamiltonian circuit. In this study, the application of a polynomial method to the problem of finding maximum independent sets will be emphasized. At this aim, case studies on king graphs, which are one of the claw-free graphs, will be shown and analytical limit for the number of elements of the maximum independent set for clae-free graphs. © 2022 Gazi Universitesi Muhendislik-Mimarlik. All rights reserved.