Atenção:
O eduCAPES é um repositório de objetos educacionais, não sendo responsável por materiais de terceiros submetidos na plataforma. O usuário assume ampla e total responsabilidade quanto à originalidade, à titularidade e ao conteúdo, citações de obras consultadas, referências e outros elementos que fazem parte do material que deseja submeter. Recomendamos que se reporte diretamente ao(s) autor(es), indicando qual parte do material foi considerada imprópria (cite página e parágrafo) e justificando sua denúncia.
Caso seja o autor original de algum material publicado indevidamente ou sem autorização, será necessário que se identifique informando nome completo, CPF e data de nascimento. Caso possua uma decisão judicial para retirada do material, solicitamos que informe o link de acesso ao documento, bem como quaisquer dados necessários ao acesso, no campo abaixo.
Todas as denúncias são sigilosas e sua identidade será preservada. Os campos nome e e-mail são de preenchimento opcional. Porém, ao deixar de informar seu e-mail, um possível retorno será inviabilizado e/ou sua denúncia poderá ser desconsiderada no caso de necessitar de informações complementares.
Metadados | Descrição | Idioma |
---|---|---|
Autor(es): dc.contributor | Almeida, Sheila Morais de | - |
Autor(es): dc.contributor | https://orcid.org/0000-0002-8639-3532 | - |
Autor(es): dc.contributor | http://lattes.cnpq.br/9151881548763857 | - |
Autor(es): dc.contributor | Zatesko, Leandro Miranda | - |
Autor(es): dc.contributor | http://lattes.cnpq.br/4259616811045288 | - |
Autor(es): dc.contributor | Luiz, Atílio Gomes | - |
Autor(es): dc.contributor | https://orcid.org/0000-0002-6177-403X | - |
Autor(es): dc.contributor | http://lattes.cnpq.br/7364915463901013 | - |
Autor(es): dc.contributor | Groshaus, Marina Esther | - |
Autor(es): dc.contributor | http://lattes.cnpq.br/4281319177692811 | - |
Autor(es): dc.contributor | Carmo, Renato José da Silva | - |
Autor(es): dc.contributor | http://lattes.cnpq.br/2968055170351130 | - |
Autor(es): dc.contributor | Almeida, Sheila Morais de | - |
Autor(es): dc.contributor | https://orcid.org/0000-0002-8639-3532 | - |
Autor(es): dc.contributor | http://lattes.cnpq.br/9151881548763857 | - |
Autor(es): dc.creator | Rocha, Aleffer | - |
Data de aceite: dc.date.accessioned | 2022-02-21T21:44:47Z | - |
Data de disponibilização: dc.date.available | 2022-02-21T21:44:47Z | - |
Data de envio: dc.date.issued | 2020-10-15 | - |
Data de envio: dc.date.issued | 2020-10-15 | - |
Data de envio: dc.date.issued | 2020-07-16 | - |
Fonte completa do material: dc.identifier | http://repositorio.utfpr.edu.br/jspui/handle/1/5232 | - |
Fonte: dc.identifier.uri | http://educapes.capes.gov.br/handle/capes/659607 | - |
Descrição: dc.description | Rainbow 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.description | Universidade Tecnológica Federal do Paraná (UTFPR) | - |
Descrição: dc.description | Problemas 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.format | application/pdf | - |
Idioma: dc.language | pt_BR | - |
Publicador: dc.publisher | Universidade Tecnológica Federal do Paraná | - |
Publicador: dc.publisher | Ponta Grossa | - |
Publicador: dc.publisher | Brasil | - |
Publicador: dc.publisher | Programa de Pós-Graduação em Ciência da Computação | - |
Publicador: dc.publisher | UTFPR | - |
Direitos: dc.rights | openAccess | - |
Palavras-chave: dc.subject | Teoria dos grafos | - |
Palavras-chave: dc.subject | Arco-íris | - |
Palavras-chave: dc.subject | Conectividade (Computadores) | - |
Palavras-chave: dc.subject | Graph theory | - |
Palavras-chave: dc.subject | Rainbow | - |
Palavras-chave: dc.subject | Connection machines | - |
Palavras-chave: dc.subject | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO | - |
Palavras-chave: dc.subject | Engenharia/Tecnologia/Gestão | - |
Título: dc.title | Coloracão arco-íris em classes de grafos | - |
Título: dc.title | Rainbow coloring in classes of graphs | - |
Tipo de arquivo: dc.type | livro digital | - |
Aparece nas coleções: | Repositorio Institucional da UTFPR - RIUT |
O Portal eduCAPES é oferecido ao usuário, condicionado à aceitação dos termos, condições e avisos contidos aqui e sem modificações. A CAPES poderá modificar o conteúdo ou formato deste site ou acabar com a sua operação ou suas ferramentas a seu critério único e sem aviso prévio. Ao acessar este portal, você, usuário pessoa física ou jurídica, se declara compreender e aceitar as condições aqui estabelecidas, da seguinte forma: