ON THE BINARY LOCATING-DOMINATION NUMBER OF REGULAR AND STRONGLY-REGULAR GRAPHS

Graphs possessing minimal dominating sets have potential applicability in computer science & engineering. In a graph G, a dominating set L meeting N(x) pi L = N(y) pi L for any x,y E V\L is known as a binary locating-dominating set. Minimizing the cardinality of such a set in G would be called the binary location-domination number gamma l_d(G) of G. This paper considers regular and strongly-regular graphs to study their binary location-domination and global binary location-domination numbers. Being an NP-complete problem, it is natural to study this parameter for special families of graphs having combinatorial and geometrical importance. Exact values of gamma l_d(G) have been evaluated for complete graphs, cycles, complete bipartite graphs and the generalized Petersen graphs P(n,2), n 4 and P(n,4), (5 5 n - 0 (mod 3)). Certain tight upper and lower bounds are shown for the path graphs, generalized Petersen graph P(n,4), (5 5 n - 1,2 (mod 3)), prism graphs and two infinite families of strongly regular graphs known as the triangular graphs and the square grid graphs. Moreover, an integer linear programming (ILP) model has been employed via CPLEX solver to show tightness in the upper bounds. By studying the binary locating-dominating sets in the complements of some of the above families, we also study their global location-domination number. Some open problems which naturally arise from the study have been proposed at the end.