Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2015-04-30T13:50:06Z
No. of bitstreams: 2
Tese - Márcia Rodrigues Cappelle Santana - 2014.pdf: 631835 bytes, checksum: 92e31eb230a1e5640350250db336b352 (MD5)
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2015-04-30T13:54:17Z (GMT) No. of bitstreams: 2
Tese - Márcia Rodrigues Cappelle Santana - 2014.pdf: 631835 bytes, checksum: 92e31eb230a1e5640350250db336b352 (MD5)
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2015-04-30T13:54:17Z (GMT). No. of bitstreams: 2
Tese - Márcia Rodrigues Cappelle Santana - 2014.pdf: 631835 bytes, checksum: 92e31eb230a1e5640350250db336b352 (MD5)
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5)
Previous issue date: 2014-10-01 / Fundação de Amparo à Pesquisa do Estado de Goiás - FAPEG / 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. / Nesta tese, apresentamos alguns resultados relacionados, principalmente, aos tamanhos
de conjuntos independentes maximais em alguns grafos. Mostramos que para inteiros r e
D, com r 2 e D 3, há um número finito de grafos conexos de grau mínimo pelo menos
2, grau máximo até D e cintura pelo menos 7 que têm tamanhos de conjuntos independentes
maximais de até r tamanhos diferentes. Além disso, provamos outros resultados que
restringem os graus de tais grafos e que generalizam resultados já conhecidos sobre grafos
bem-cobertos. Foram estudados a estrutura e o reconhecimento dos grafos bem-cobertos
G de ordem n(G) sem vértice isolado que têm número de independência n(G)k
2 , para algum
inteiro não negativo k. Para k = 1, apresentamos uma descrição estrutural completa
destes grafos e para um k geral, porém fixo, descrevemos um algoritmo de complexidade
polinomial de tempo para o reconhecimento de tais grafos. Consideramos grafos G sem
vértice isolado cuja diferença entre o maior e o menor conjuntos independentes maximais
é no máximo k, para algum inteiro k não negativo. Obtivemos um limite superior sobre
o número de independência destes grafos. Apresentamos um algoritmo de complexidade
polinomial de tempo para reconhecimento de alguns produtos complementares, o qual
inclui todos os prismas complementares. Apresentamos também alguns resultados sobre
prismas complementares bem-cobertos. Mostramos que se G não é um grafo bem-coberto
e seu prisma complementar é bem-coberto, então G tem somente dois tamanhos de conjuntos
independentes maximais que são consecutivos. Apresentamos um limite superior
para a quantidade de tamanhos de conjuntos independentes maximais em prismas complementares
e também outros resultados relacionados à bem-cobertura. Apresentamos um
limite inferior para a quantidade de conjuntos independentes maximais de tamanhos diferentes
em produtos Cartesianos de caminhos e ciclos.
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.bc.ufg.br:tede/4475 |
| Date | 01 October 2014 |
| Creators | Cappelle, Márcia Rodrigues |
| Contributors | Barbosa, Rommel Melgaço, Barbosa, Rommel Melgaço, Abreu, Nair Maria Maia de, Santos, José Plínio de Oliveira, Longo, Humberto José, Silva, Hebert Coelho da |
| Publisher | Universidade Federal de Goiás, Programa de Pós-graduação em Ciência da Computação (INF/UFMS), UFG, Brasil, Instituto de Física - IF (RG) |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFG, instname:Universidade Federal de Goiás, instacron:UFG |
| Rights | http://creativecommons.org/licenses/by-nc-nd/4.0/, info:eu-repo/semantics/openAccess |
| Relation | 5425012756248488080, 600, 600, 600, 600, -4029658853652049306, 3671711205811204509, -961409807440757778 |
Page generated in 0.0018 seconds