Sobre grafos com r tamanhos diferentes de conjuntos independentes maximais e algumas extensões
Carregando...
Data
2014-10-01
Autores
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Goiás
Resumo
In this thesis, we present some results concerning about the sizes of maximal independent
sets in graphs. We prove that for integers r and D with r 2 and D 3, there are
only finitely many connected graphs of minimum degree at least 2, maximum degree
at most D, and girth at least 7 that have maximal independent sets of at most r different
sizes. Furthermore, we prove several results restricting the degrees of such graphs. These
contributions generalize known results on well-covered graphs. We study the structure
and recognition of the well-covered graphs G with order n(G) without an isolated vertex
that have independence number n(G)k
2 for some non-negative integer k. For k = 1, we
give a complete structural description of these graphs, and for a general but fixed k,
we describe a polynomial time recognition algorithm. We consider graphs G without an
isolated vertex for which the independence number a(G) and the independent domination
number i(G) satisfy a(G) i(G) k for some non-negative integer k. We obtain a
upper bound on the independence number in these graphs. We present a polynomial
algorithm to recognize some complementary products, which includes all complementary
prisms. Also, we present results on well-covered complementary prisms. We show that
if G is not well-covered and its complementary prism is well-covered, then G has only
two consecutive sizes of maximal independent sets. We present an upper bound for the
quantity of sizes of maximal independent sets in complementary prisms and other wellcovered
concerning results. We present a lower bound for the quantity of different sizes
of maximal independent sets in Cartesian products of paths and cycles.
Descrição
Citação
CAPPELLE, M. R. Sobre grafos com r tamanhos diferentes de conjuntos independentes maximais e algumas extensões. 2014. 86 f. Tese (Doutorado em Ciência da Computação em Rede) - Universidade Federal de Goiás, Goiânia, 2014.