Sobre grafos com r tamanhos diferentes de conjuntos independentes maximais e algumas extensões

Página do item simplificado
dc.contributor.advisor1Barbosa, Rommel Melgaço
dc.contributor.advisor1Latteshttp://lattes.cnpq.br/6228227125338610por
dc.contributor.referee1Barbosa, Rommel Melgaço
dc.contributor.referee2Abreu, Nair Maria Maia de
dc.contributor.referee3Santos, José Plínio de Oliveira
dc.contributor.referee4Longo, Humberto José
dc.contributor.referee5Silva, Hebert Coelho da
dc.creatorCappelle, Márcia Rodrigues
dc.creator.Latteshttp://lattes.cnpq.br/4638125536971138por
dc.date.accessioned2015-04-30T13:54:17Z
dc.date.issued2014-10-01
dc.description.abstractIn 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.eng
dc.description.provenanceSubmitted 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)eng
dc.description.provenanceApproved 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)eng
dc.description.provenanceMade 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-01eng
dc.description.resumoNesta 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.por
dc.description.sponsorshipFundação de Amparo à Pesquisa do Estado de Goiás - FAPEGpor
dc.formatapplication/pdf*
dc.identifier.citationCAPPELLE, 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.por
dc.identifier.urihttp://repositorio.bc.ufg.br/tede/handle/tede/4475
dc.languageporpor
dc.publisherUniversidade Federal de Goiáspor
dc.publisher.countryBrasilpor
dc.publisher.departmentInstituto de Física - IF (RG)por
dc.publisher.initialsUFGpor
dc.publisher.programPrograma de Pós-graduação em Ciência da Computação (INF/UFMS)por
dc.rightsAcesso Abertopor
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/
dc.subjectTeoria dos grafospor
dc.subjectConjuntos independentespor
dc.subjectGrafos bem-cobertospor
dc.subjectProdutos complementarespor
dc.subjectGraph theoryeng
dc.subjectIndependent setseng
dc.subjectWell-covered graphseng
dc.subjectComplementary productseng
dc.subject.cnpqCIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAOpor
dc.thumbnail.urlhttp://repositorio.bc.ufg.br/tede/retrieve/19328/Tese%20-%20M%c3%a1rcia%20Rodrigues%20Cappelle%20Santana%20-%202014.pdf.jpg*
dc.titleSobre grafos com r tamanhos diferentes de conjuntos independentes maximais e algumas extensõespor
dc.title.alternativeOn graphs having r different sizes of maximal independent sets and some extensionseng
dc.typeTesepor

Arquivos

Pacote Original
Agora exibindo 1 - 1 de 1
Imagem de Miniatura
Nome:
Tese - Márcia Rodrigues Cappelle Santana - 2014.pdf
Tamanho:
617.03 KB
Formato:
Adobe Portable Document Format
Descrição:
Baixar
Licença do Pacote
Agora exibindo 1 - 1 de 1
Nenhuma Miniatura disponível
Nome:
license.txt
Tamanho:
2.11 KB
Formato:
Item-specific license agreed upon to submission
Descrição:
Baixar

Coleções

Doutorado em Ciência da Computação em Rede - UFMS/UFG (INF)