Use este identificador para citar ou linkar para este item:
http://repositorio.utfpr.edu.br/jspui/handle/1/15956| Título: | Coloração arco-íris em grafos resultantes de produto cartesiano |
| Título(s) alternativo(s): | Coloring of the rainbow in graphs resulting from cartesian product |
| Autor(es): | Rocha, Aleffer |
| Orientador(es): | Almeida, Sheila Morais de |
| Palavras-chave: | Cores Arco-íris Representações dos grafos Colors Rainbow Representations of graphs |
| Data do documento: | 5-Dez-2017 |
| Editor: | Universidade Tecnológica Federal do Paraná |
| Câmpus: | Ponta Grossa |
| Citação: | ROCHA, Aleffer. Coloração arco-íris em grafos resultantes de produto cartesiano. 2017. 46 f. Trabalho de Conclusão de Curso (Ciência da Computação) - Universidade Tecnológica Federal do Paraná, Ponta Grossa, 2017. |
| Resumo: | Dado 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. |
| Abstract: | Given 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. |
| URI: | http://repositorio.utfpr.edu.br/jspui/handle/1/15956 |
| Aparece nas coleções: | PG - Ciência da Computação |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| PG_COCIC_2017_2_10.pdf | 9,19 MB | Adobe PDF |  Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.