Please use this identifier to cite or link to this item:
Title: Recognition of graphs with convex quadratic stability number
Other Titles: Reconhecimento de grafos com número de estabilidade quadrático convexo
Author: Pacheco, Maria de Fátima Moreira da Silva
Advisor: Luz, Carlos Jorge da Silva
Cardoso, Domingos Moreira
Keywords: Spectral graph theory
Convex quadratic programming in graphs
Stable sets
Adjacency matrix
Graphs with convex-QP stability number
Star sets, (κ, τ )- regular sets
Hamiltonian graphs
Defense Date: Mar-2019
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.
Appears in Collections:UA - Teses de doutoramento
DMat - Teses de doutoramento

Files in This Item:
File Description SizeFormat 
Documento_Maria_Fátima_Pacheco.pdf580.09 kBAdobe PDFView/Open

Formato BibTex MendeleyEndnote Degois 

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.