Coloração arco-íris em grafos resultantes de produto cartesiano

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorAlmeida, Sheila Morais de-
Autor(es): dc.contributorAlmeida, Sheila Morais de-
Autor(es): dc.contributorNóbrega, Diana Sasaki-
Autor(es): dc.contributorQueiroz, Saulo Jorge Beltrao de-
Autor(es): dc.creatorRocha, Aleffer-
Data de aceite: dc.date.accessioned2022-02-21T21:36:38Z-
Data de disponibilização: dc.date.available2022-02-21T21:36:38Z-
Data de envio: dc.date.issued2020-11-18-
Data de envio: dc.date.issued2020-11-18-
Data de envio: dc.date.issued2017-12-05-
Fonte completa do material: dc.identifierhttp://repositorio.utfpr.edu.br/jspui/handle/1/15956-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/656487-
Descrição: dc.descriptionGiven a graph G, an edge-coloring of G is an assingment of colors to the edges of G. A proper edge-coloring is an edge coloring if adjacent edges have different colors. A rainbow coloring of a connected graph G is an edge coloring that is not necessarily proper such that there is a path between any pair of vertices of G whose edge colors are pairwise distinct. The rainbow connection number of a graph G, denoted as rc(G), is the least number of colors for which there is a rainbow coloring of G. A graph G is rainbow critical if its rainbow connection number increases when we remove any edge from G. In this work we determine the rainbow connection number for the cartesian product graphs CmxPn when mis odd and CmxCn when m and n have distinct parities. For the case in which n and m are odd, we prove that rc(CmxCn)<=(m+n)/2. We also show that the cartesian product PmxPn is rainbow critical if and only if it is a path Pn, n > 1, or a C4 and that the cartesian product Cm x Pn is not rainbow critical when m is even and n > 1.-
Descrição: dc.descriptionDado um grafo G, uma coloração de arestas de G é uma atribuição de cores para as arestas de G. Uma coloração de arestas é própria se arestas adjacentes têm cores distintas. Uma coloração arco-íris de um grafo conexo G é uma coloração de arestas, não necessariamente própria, tal que entre qualquer par de vértices de G existe um caminho cujas cores das arestas são duas a duas distintas. O número de conexão arco-íris de um grafo G, denotado por rc(G), é o menor número de cores necessárias para se obter uma coloração arco-íris de G. Um grafo G é arco-íris crítico se a remoção de qualquer aresta de G aumenta o seu número de conexão arco-íris. Neste trabalho determinamos o número de conexão arco-íris para os grafos que são resultantes do produto cartesiano Cm x Pn, quando m é ímpar, e Cm x Cn, quando m e n têm paridades distintas. Para os casos em que m e n são ímpares, provamos que rc(Cm x Cn) <= (m + n)/2. Também mostramos que o produto cartesiano Pm x Pn é arco-íris crítico se, e somente se, é um caminho Pn, n > 1, ou um C4 e que os produtos cartesianos Cm × Pn não são arco-íris críticos quando m é par e n > 1.-
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.publisherDepartamento Acadêmico de Informática-
Publicador: dc.publisherCiência da Computação-
Publicador: dc.publisherUTFPR-
Direitos: dc.rightsopenAccess-
Palavras-chave: dc.subjectCores-
Palavras-chave: dc.subjectArco-íris-
Palavras-chave: dc.subjectRepresentações dos grafos-
Palavras-chave: dc.subjectColors-
Palavras-chave: dc.subjectRainbow-
Palavras-chave: dc.subjectRepresentations of graphs-
Palavras-chave: dc.subjectCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO-
Título: dc.titleColoração arco-íris em grafos resultantes de produto cartesiano-
Título: dc.titleColoring of the rainbow in graphs resulting from cartesian product-
Tipo de arquivo: dc.typelivro digital-
Aparece nas coleções:Repositorio Institucional da UTFPR - RIUT

Não existem arquivos associados a este item.