Recognition of graphs with convex quadratic stability number

Abstract

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.

Um conjunto estável máximo num grafo G é um conjunto estável com cardinalidade máxima. A cardinalidade de um conjunto estável máximo chama-se número de estabilidade do grafo e denota-se α(G). O problema da determinação do número de estabilidade de um grafo arbitrário é um problema de optimização NP-completo e, como tal, não se conhecem algoritmos polinomiais capazes dessa determinação. O objectivo desta tese é a construção de algoritmos de reconhecimento para grafos com número de estabilidade quadrático convexo, que são grafos cujo número de estabilidade é igual ao valor óptimo de um programa quadrático convexo associado à respectiva matriz de adjacência. Com esse objectivo, apresentam-se resultados que relacionam os valores próprios da matriz de adjacência com a existência de estáveis máximos e descrevem-se algoritmos de reconhecimento baseados em tais resultados. Os algoritmos são posteriormente aplicados a vários problemas clássicos como o da dominação eficiente e da existência de emparelhamentos perfeitos e de ciclos de Hamilton.