Criticality indices of locating-domination of paths and cycles

Abstract

A locating-dominating set of a graph G = (V,E) is a dominating set S ⊆ V such that for every pair of distinct vertices u and ν in V \ S, N _G{u) ∩ S ≠ N_G(ν) ∩ S. The minimum cardinality of a locating-dominating set is denoted by γL(G). The removal criticality index of locating-domination of a graph G is de fined as ci ^-_L(G) = (∑e∈E(G)( γL(G) - γL (G - e) / \E(G)\ and the addition criticality index of locating-domination of G is defined as ci⁺_L(G) = (∑e∈E(G)( γL(G) - γL (G + e) / \E(G)\ where G is the complement graph of G. In this paper, we determine the criticality indices of locating- domination of paths and cycles.