Conjuntos dominantes localizadores em algumas subclasses de grafos split
Nenhuma Miniatura disponível
Data
2024-12-09
Autores
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Goiás
Resumo
A dominating set of a graph G is a subset S ⊆ V (G) such that every vertex not in S is adjacent to at least one vertex in S. A locating-dominating set of a graph G is a subset L ⊆ V (G) such that L is a dominating set and, for every pair of vertices u, v not in L, N(u) ∩ L ̸= N(v) ∩ L, where N(u) and N(v) are the vertices adjacent to u and v, respectively. A split graph is a graph G whose vertex set V (G) can be partitioned in two subsets Q and S such that Q is a clique and S is an independent set. In this work, a proposition was constructed to simplify split graphs that have mutually twin vertices, transforming them into graphs with fewer twins and reducing the minimum cardinality of the locating-dominating set by one unit for each removed vertex. Furthermore, closed formulas for the minimum cardinality of locating-dominating sets in complete split graphs and split corona graphs were presented.
Descrição
Palavras-chave
Teoria dos grafos, Conjuntos dominantes, Conjuntos dominantes localizadores, Grafos split, Graph theory, Dominating sets, Locating-dominating sets, Split graphs
Citação
BELO, Pedro Augusto Serafim. Conjuntos dominantes localizadores em algumas subclasses de grafos split. 2024. 59 f. Trabalho de Conclusão de Curso (Bacharelado em Ciência da Computação) - Instituto de Informática, Universidade Federal de Goiás, Goiânia, 2024.