Use este identificador para citar ou linkar para este item:
http://repositorio.utfpr.edu.br/jspui/handle/1/30627| Título: | Colorações de arestas distinguidoras em potências de caminhos |
| Título(s) alternativo(s): | Distinguishing edge colorings on powers of paths |
| Autor(es): | Salgado, Pedro Henrique |
| Orientador(es): | Almeida, Sheila Morais de |
| Palavras-chave: | Grafos de ligação Otimização combinatória Complexidade computacional Bond graphs Combinatorial optimization Computational complexity |
| Data do documento: | 30-Nov-2022 |
| Editor: | Universidade Tecnológica Federal do Paraná |
| Câmpus: | Ponta Grossa |
| Citação: | SALGADO, Pedro Henrique. Colorações de arestas distinguidoras em potências de caminhos. 2022. Trabalho de Conclusão de Curso (Tecnologia em Análise e Desenvolvimento de Sistemas) - Universidade Tecnológica Federal do Paraná, Ponta Grossa, 2022. |
| Resumo: | Uma coloração de arestas própria para um grafo 𝐺 é uma atribuição de cores para as arestas de 𝐺 tal que arestas que incidem no mesmo vértice recebem cores distintas. Dado um grafo com uma coloração de arestas, o conjunto de cores de um vértice 𝑣 é o conjunto das cores das arestas incidentes em 𝑣. Uma coloração de arestas própria é distinguidora de vértices adjacentes quando, para quaisquer dois vértices adjacentes, seus conjuntos de cores são distintos; e é distinguidora de vértices quando, para quaisquer dois vértices (não necessariamente adjacentes), seus conjuntos de cores são distintos. O Problema da Coloração de Arestas Distinguidora de Vértices Adjacentes é determinar o menor número de cores para realizar uma coloração de arestas distinguidora de vértices adjacentes para um dado um grafo 𝐺. Tal número é chamado de índice cromático distinguidor de vértices adjacentes. Similarmente, o Problema da Coloração de Arestas Distinguidora de Vértices é determinar o menor número de cores para realizar uma coloração de arestas distinguidora de vértices para um dado um grafo 𝐺. Tal número é chamado de índice cromático distinguidor de vértices. A 𝑘-ésima potência de um caminho com 𝑛 vértices é o grafo obtido a partir do caminho com 𝑛 vértices pela adição de arestas entre quaisquer dois vértices que estejam a uma distância de no máximo 𝑘 no caminho. Omai et al. determinaram o índice cromático distinguidor de vértices adjacentes das potências de caminhos. Para tanto, o problema foi dividido em casos e utilizaram-se diversas técnicas de coloração de arestas. Neste trabalho, apresentamos uma nova técnica para a coloração de arestas distinguidora de de vértices adjacentes em potências de caminhos que têm vértice universal. Esta nova técnica une casos que antes eram tratados separadamente, sendo uma prova mais simples. Além disso, esta técnica permite determinar o índice cromático distinguidor de vértices de um subconjunto das potências de caminho com vértice universal. |
| Abstract: | A proper edge coloring of a graph 𝐺 is an assignment of colors to the edges of 𝐺 such that edges that share a common vertex receive distinct colors. Give a graph with an edge coloring, the set of colors of a vertex 𝑣 is the set of the colors of the edges incident with 𝑣. A proper edge coloring is an adjacent-vertex-distinguishing edge coloring if, for any two adjacent vertices, theirs set of colors are distinct; and it is a vertex-distinguishing edge coloring when, for any two (not necessarily adjacent) vertices, its set of colors are distinct. The Adjacent-Vertex-Distinguishing Edge Coloring Problem is to determine the minimum number of colors for an adjacent-vertex-distinguishing edge coloring of a given graph 𝐺. This number is called the adjacent-vertex-distinguishing chromatic index. Similarly, the Vertex-Distinguishing Edge Coloring Problem is to determine the minimum number of colors for a vertex-distinguishing edge coloring of a given graph 𝐺. This number is called the vertex-distinguishing chromatic index. The 𝑘-th power of a path with 𝑛 vertices is the graph obtained from the path with 𝑛 vertices by adding edges between any two vertices at distance at most 𝑘. Omai et al. determined the adjacent-vertex-distinguishing chromatic index of the powers of paths. To that end, the problem was divide into cases that used several different edge coloring techniques. We present a new technique to obtain an adjacent-vertex-distinguishing edge coloring of powers of paths which contain universal vertices. This new technique is applicable to cases that were previously treated separately, being a simpler proof. Moreover, this technique allows to determine the vertex-distinguishing chromatic index of a subset of powers of paths with universal vertex. |
| URI: | http://repositorio.utfpr.edu.br/jspui/handle/1/30627 |
| Aparece nas coleções: | PG - Tecnologia em Análise e Desenvolvimento de Sistemas |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| coloracoesarestasdistinguidoras.pdf | 411,35 kB | Adobe PDF |  Visualizar/Abrir |
Este item está licenciada sob uma Licença Creative Commons
