On locating and locating-total domination edge addition critical graphs (Q2878222)

A dominating set \(D\) of a graph \(G=(V,E)\) is a locating-dominating set (LDS), if any two distinct vertices from \(V-D\) have different neighborhoods in \(D\). If an LDS \(D\) contains no isolated vertices, it is a locating-total dominating set (LTDS). The locating-domination number \(\gamma_L(G)\) and the locating-total domination number \(\gamma_L^t(G)\) are the sizes of a minimum cardinality LDS and LTDS, respectively. In this paper graphs \(G\) with the property that \(\gamma_L(G) < \gamma_L(G+e)\) holds for any \(e\notin E\) are characterized. The same class of graphs (with the natural additional property of being isolate-free) also characterizes graphs for which \(\gamma_L^t(G) < \gamma_L^t(G+e)\) holds for any \(e\notin E\). The graphs for which \(\gamma_L(G) > \gamma_L(G+e)\) (resp. \(\gamma_L^t(G) > \gamma_L^t(G+e)\)) holds for any \(e\notin E\) are characterized within the class of all trees.