A sharp lower bound for locating-dominating sets in trees
Justine Louis, Sewell Peter, James J.R. Huddleston Slater · Australas. J Comb. · 2014
Let LD(G) denote the minimum cardinality of a locating-dominating set for graph G .I fT is a tree of order n with l leaf vertices and s support vertices, then a known lower bound of Blidia, Chellali, Maffray, Moncel and Semri [Australas. J. Combin. 39 (2007), 219–232] is LD(T ) ≥� (n +1+ l − s)/3� . In this paper, we show that LD(T ) ≥ � (n +1+2 (l − s))/3� and these bounds are sharp. We constructively characterize the trees achieving the lower bounds.