| Resumo: | A maximum stable set is a stable set with the largest possible size, for a given graph G. This size is called the stability number of G, and it is denoted α(G). The problem of determining the stability number of an arbitrary graph, is a NP-complete optimization problem. As such, it is unlikely that there is a polynomial algorithm for finding a maximum stable set of a graph. The main purpose of this thesis is the achievement of recognition algorithms for graphs with convex quadratic stability number that are graphs whose stability number is equal to the optimal value of a convex quadratic program associated to the corresponding adjacency matrix . For that, results that relate the eigenvalues of the adjacency matrix and maximum stable sets are established and recognition algorithms are derived from those results. Such algorithms are applied to several well known problems such as efficient domination and the determination of graphs with perfect matchings and Hamiltonian cycles.
|
|---|