Locating-dominating sets in some subclasses of split graphs

Abstract

Let G be a simple, finite and undirected graph. A set L ⊆ V ( G ) is a locating-dominating set (LD-set, for short) of G if L is a dominating set of G and N ( u ) ∩ L ≠ N ( v ) ∩ L for all distinct vertices u , v ∈ V ( G ) − L , where N(x) is the open neighborhood of x. The minimum cardinality of an LD-set of G is denoted by γ L ( G ) . A graph is a split graph if its vertices set can be partitioned into an independent set and a clique. We present closed formulas for γ L in complete split graphs and split corona graphs. Moreover, we propose a way to reduce split graphs with many twin vertices.