Conjuntos dominantes localizadores em algumas subclasses de grafos split

Abstract

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.