On locating and locating-total domination edge addition critical graphs
Abstract
A set of vertices S of a graph G = (V, E) is a locating-dominating set, abbreviated (LDS), if for every pair of distinct vertices u and ν in V - S the neighborhoods of u and ν in S are nonempty and different. A locating-total dominating set, abbreviated (LTDS) , is a LDS whose induced subgraph has no isolated vertices. The locating- domination number, γL{G)} of G is the minimum cardinality of a LDS of G and the locating-total domination number, γt L(G), of G is the minimum cardinality of a LTDS of G. The addition of any missing edge e in a graph G, can increase, decrease or remain unchanged the locating (locating-total, respectively) domination number. A graph G is γ+ L-EA-critical (γ- L-EA-critical, respectively) if γL(G) < γL(G+e) (γL(G+e) < γL(G), respectively) for every e ∉ E. γt+ & L-EA-critical and γt- L;-EA-critical graphs are defined similarly. In this paper, we give characterizations of π+-EA-critical graphs and π--EA-critical trees where π ∈ {γL, γtL}.
