Co-isolated Locating Dominating Sets on Subdivision Graphs

The study of dominating sets in graphs began in the early 20th century when mathematicians started investigating problems related to covering or controlling vertices in a graph. A dominating set in a graph G is a set of vertices such that every vertex not in the set is adjacent to at least one vertex in the set. Early work focused on finding minimum dominating sets. The concept of locating domination emerged in the 1970’s as an extension of dominating sets. It was introduced by Cockayne, Dawes, and Hedetniemi in 1977. The idea was to find a subset of vertices called "locating-dominating set" such that, for each pair of vertices, there exists a vertex in the set whose removal disconnects the pair. The initial focus was on locating-dominating sets in trees. In 1977, Cockayne, Dawes, and Hedetniemi introduced the concept of "locating-total domination" in trees, where every vertex in the tree is either in the locating-dominating set or adjacent to one. This concept was further explored by many researchers in the following years. Moreover a new domination parameter can be obtained by combining two parameters. In this relevance Muthammai and Meenal in the year 2015, defined Co-isolated Locating Domination in Graphs which states that there exists at least one isolated vertex in the complement set of the Locating Dominating set. Locating domination on subdivision graphs is an interesting and important problem in graph theory. Subdivision graphs are graphs that can be obtained from another graph by replacing edges with paths. In a subdivision graph, locating domination can be defined as follows: Given a subdivision graph G, find a minimum-sized set S of vertices such that for each vertex v in G, there exists a vertex u in S such that the distance between u and v is at most one along the graph edges. The computational complexity of locating domination on subdivision graphs is an active research area. Finding a minimum locating-dominating set on general graphs is known to be NP-hard. However, specific algorithms and heuristics have been developed to solve this problem efficiently for certain subclasses of graphs. Locating domination on subdivision graphs has practical applications in network design, facility location, and surveillance systems, similar to its applications in general graph theory. For example, in network design, it can help in optimizing the placement of routers or monitoring points in a communication network. In this article, co-isolated locating domination numbers of subdivision graphs for some standard graphs are obtained. Also, the corresponding number on subdivision graphs are characterized for cubic graphs.