Coloracão arco-íris em classes de grafos

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorAlmeida, Sheila Morais de-
Autor(es): dc.contributorhttps://orcid.org/0000-0002-8639-3532-
Autor(es): dc.contributorhttp://lattes.cnpq.br/9151881548763857-
Autor(es): dc.contributorZatesko, Leandro Miranda-
Autor(es): dc.contributorhttp://lattes.cnpq.br/4259616811045288-
Autor(es): dc.contributorLuiz, Atílio Gomes-
Autor(es): dc.contributorhttps://orcid.org/0000-0002-6177-403X-
Autor(es): dc.contributorhttp://lattes.cnpq.br/7364915463901013-
Autor(es): dc.contributorGroshaus, Marina Esther-
Autor(es): dc.contributorhttp://lattes.cnpq.br/4281319177692811-
Autor(es): dc.contributorCarmo, Renato José da Silva-
Autor(es): dc.contributorhttp://lattes.cnpq.br/2968055170351130-
Autor(es): dc.contributorAlmeida, Sheila Morais de-
Autor(es): dc.contributorhttps://orcid.org/0000-0002-8639-3532-
Autor(es): dc.contributorhttp://lattes.cnpq.br/9151881548763857-
Autor(es): dc.creatorRocha, Aleffer-
Data de aceite: dc.date.accessioned2022-02-21T21:44:47Z-
Data de disponibilização: dc.date.available2022-02-21T21:44:47Z-
Data de envio: dc.date.issued2020-10-15-
Data de envio: dc.date.issued2020-10-15-
Data de envio: dc.date.issued2020-07-16-
Fonte completa do material: dc.identifierhttp://repositorio.utfpr.edu.br/jspui/handle/1/5232-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/659607-
Descrição: dc.descriptionRainbow coloring problems, of noteworthy applications in Information Security, have been receiving much attention in the last years in Combinatorics. In particular, the rainbow connection number of a connected graph 𝐺, denoted 𝑟𝑐(𝐺), is the least 𝑘 for which 𝐺 admits a (not necessarily proper) 𝑘-edge-coloring such that between any pair of vertices there is a rainbow path, i. e., a path whose edge colors are all distinct. Given an edge coloring 𝜑 for a graph 𝐺, if between any pair of vertices there is a minimum path which is rainbow, then 𝜑 is a strong rainbow coloring. The minimum number of colors for which a given graph 𝐺 has a strong rainbow coloring is the strong rainbow connection number of 𝐺. A graph 𝐺 is rainbow critical if the deletion of any edge of 𝐺 increases 𝑟𝑐(𝐺). In this work, we determine the rainbow connection number and the strong rainbow connection number of shadow graphs of paths, triple triangular snake graphs, circulant graphs 𝐶 1,𝑘 2𝑘 and join graphs 𝐺 + 𝐾𝑚 when 𝐺 has 𝑟𝑐(𝐺) ≤ 2. We also determine the rainbow connection number of join graphs of sunlet (𝑅𝑛) with 𝐺 when |𝑉 (𝐺)| ≥ 𝑛 − 1 and of cographs with three pendent vertices. We found new upper bounds for the rainbow connection number of snake graphs, join graphs of two graphs with universal vertices, and join graphs 𝑅𝑛 + 𝐾𝑚 when 𝑚 ≤ 𝑛 − 2. We also present necessary and sufficient conditions for the criticality of fan graphs, Cartesian products 𝐺 × 𝑃𝑛 when 𝑟𝑐(𝐺) = 𝑑𝑖𝑎𝑚(𝐺) ≥ 2 or when 𝐺 is a pan graph, 𝐺 × 𝐾𝑚 when 𝑟𝑐(𝐺) = 𝑑𝑖𝑎𝑚(𝐺) ≥ 1, and 𝐶𝑚 × 𝐶𝑛 when 𝑚 and 𝑛 are even.-
Descrição: dc.descriptionUniversidade Tecnológica Federal do Paraná (UTFPR)-
Descrição: dc.descriptionProblemas de coloração arco-íris, com notáveis aplicações em segurança de informação, têm recebido bastante atenção nos últimos anos na área de Combinatória. Em particular, o número de conexão arco-íris de um grafo conexo 𝐺, denotado por 𝑟𝑐(𝐺), é o menor inteiro 𝑘 para o qual 𝐺 admite uma 𝑘-coloração de arestas (não necessariamente própria) tal que, entre qualquer par de vértices, existe um caminho arco-íris, ou seja, um caminho em que as cores das arestas são todas distintas. Dada uma coloração de arestas 𝜑 para um grafo 𝐺, se entre cada par de vértices existe um caminho mínimo que é arco-íris, então 𝜑 é uma coloração arco-íris forte. O menor número de cores que permite uma coloração arco-íris forte de um dado grafo 𝐺 é o número de conexão arco-íris forte de 𝐺. Um grafo 𝐺 é arco-íris crítico se a remoção de uma aresta qualquer aumenta o número de conexão arco-íris de 𝐺. Neste trabalho, são determinados o número de conexão arco-íris e o número de conexão arco-íris forte dos grafos sombras de caminhos, cobras triangulares triplas, circulantes 𝐶 1,𝑘 2𝑘 e junção 𝐺+𝐾𝑚 quando 𝐺 tem 𝑟𝑐(𝐺) ≤ 2. Também foram determinados os números de conexão arco-íris dos grafos junção de sunlet (𝑅𝑛) com 𝐺 quando |𝑉 (𝐺)| ≥ 𝑛 − 1 e de cografos com três vértices pendentes. Foram encontrados novos limitantes superiores para o número de conexão arco-íris dos grafos cobras, de junção de dois grafos com vértice universal e de junção 𝑅𝑛 +𝐾𝑚 quando 𝑚 ≤ 𝑛−2. Também são apresentadas condições necessárias e suficientes para a criticalidade dos grafos leque, dos produtos cartesianos de 𝐺 × 𝑃𝑛 quando 𝑟𝑐(𝐺) = 𝑑𝑖𝑎𝑚(𝐺) ≥ 2 ou quando 𝐺 é uma panela, 𝐺 × 𝐾𝑚 quando 𝑟𝑐(𝐺) = 𝑑𝑖𝑎𝑚(𝐺) ≥ 1 e de 𝐶𝑚 × 𝐶𝑛, quando 𝑚 e 𝑛 são pares.-
Formato: dc.formatapplication/pdf-
Idioma: dc.languagept_BR-
Publicador: dc.publisherUniversidade Tecnológica Federal do Paraná-
Publicador: dc.publisherPonta Grossa-
Publicador: dc.publisherBrasil-
Publicador: dc.publisherPrograma de Pós-Graduação em Ciência da Computação-
Publicador: dc.publisherUTFPR-
Direitos: dc.rightsopenAccess-
Palavras-chave: dc.subjectTeoria dos grafos-
Palavras-chave: dc.subjectArco-íris-
Palavras-chave: dc.subjectConectividade (Computadores)-
Palavras-chave: dc.subjectGraph theory-
Palavras-chave: dc.subjectRainbow-
Palavras-chave: dc.subjectConnection machines-
Palavras-chave: dc.subjectCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO-
Palavras-chave: dc.subjectEngenharia/Tecnologia/Gestão-
Título: dc.titleColoracão arco-íris em classes de grafos-
Título: dc.titleRainbow coloring in classes of graphs-
Tipo de arquivo: dc.typelivro digital-
Aparece nas coleções:Repositorio Institucional da UTFPR - RIUT

Não existem arquivos associados a este item.