Dissertation/ Thesis
Colorações de arestas distinguidoras em potências de caminhos ; Distinguishing edge colorings on powers of paths
| العنوان: | Colorações de arestas distinguidoras em potências de caminhos ; Distinguishing edge colorings on powers of paths |
|---|---|
| المؤلفون: | Salgado, Pedro Henrique |
| المساهمون: | Almeida, Sheila Morais de, Rocha, Aleffer, Zatesko, Leandro Miranda |
| بيانات النشر: | Universidade Tecnológica Federal do Paraná Ponta Grossa Brasil Departamento Acadêmico de Informática Tecnologia em Análise e Desenvolvimento de Sistemas UTFPR |
| سنة النشر: | 2022 |
| المجموعة: | Universidade Tecnológica Federal do Paraná (UTFPR): Repositório Institucional (RIUT) |
| مصطلحات موضوعية: | Grafos de ligação, Otimização combinatória, Complexidade computacional, Bond graphs, Combinatorial optimization, Computational complexity, CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::SISTEMAS DE COMPUTACAO |
| الوصف: | 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. ; Conselho Nacional do Desenvolvimento Científico e Tecnológico (CNPq) ; 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 ... |
| نوع الوثيقة: | bachelor thesis |
| وصف الملف: | application/pdf |
| اللغة: | Portuguese |
| Relation: | 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.; http://repositorio.utfpr.edu.br/jspui/handle/1/30627 |
| الاتاحة: | http://repositorio.utfpr.edu.br/jspui/handle/1/30627 |
| Rights: | openAccess ; http://creativecommons.org/licenses/by/4.0/ |
| رقم الانضمام: | edsbas.88A7E572 |
| قاعدة البيانات: | BASE |
| الوصف غير متاح. |