Registro fonte: Colorações de arestas distinguidoras em potências de caminhos

Colorações de arestas distinguidoras em potências de caminhos

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...

ver descrição completa

Autor principal:	Salgado, Pedro Henrique
Formato:	Trabalho de Conclusão de Curso (Graduação)
Idioma:	Português
Publicado em:	Universidade Tecnológica Federal do Paraná 2023
Assuntos:	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
Acesso em linha:	http://repositorio.utfpr.edu.br/jspui/handle/1/30627
Tags:	Adicionar Tag Sem tags, seja o primeiro a adicionar uma tag!

id	riut-1-30627
recordtype	dspace
spelling	riut-1-306272023-02-26T06:06:58Z 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 Almeida, Sheila Morais de 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 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. 2023-02-24T12:13:41Z 2023-02-24T12:13:41Z 2022-11-30 bachelorThesis 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 por openAccess http://creativecommons.org/licenses/by/4.0/ application/pdf Universidade Tecnológica Federal do Paraná Ponta Grossa Brasil Departamento Acadêmico de Informática Tecnologia em Análise e Desenvolvimento de Sistemas UTFPR
institution	Universidade Tecnológica Federal do Paraná
collection	RIUT
language	Português
topic	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
spellingShingle	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 Salgado, Pedro Henrique Colorações de arestas distinguidoras em potências de caminhos
description	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.
format	Trabalho de Conclusão de Curso (Graduação)
author	Salgado, Pedro Henrique
author_sort	Salgado, Pedro Henrique
title	Colorações de arestas distinguidoras em potências de caminhos
title_short	Colorações de arestas distinguidoras em potências de caminhos
title_full	Colorações de arestas distinguidoras em potências de caminhos
title_fullStr	Colorações de arestas distinguidoras em potências de caminhos
title_full_unstemmed	Colorações de arestas distinguidoras em potências de caminhos
title_sort	colorações de arestas distinguidoras em potências de caminhos
publisher	Universidade Tecnológica Federal do Paraná
publishDate	2023
citation	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.
url	http://repositorio.utfpr.edu.br/jspui/handle/1/30627
_version_	1805452973273251840
score	10,814766

Colorações de arestas distinguidoras em potências de caminhos

Registros relacionados