Multiple Intruder Locating Dominating Sets in Graphs: An Algorithmic Approach

K. Venugopal, K. A. Vidya

Abstract


A set \(S\subseteq V\) of vertices (called codewords) of a graph \(G=(V, E)\) is called a Multiple Intruder Locating Dominating set (MILD set) if every non-codeword \(v\) is adjacent to at least one codeword \(u\) which is not adjacent to any other non-codeword. This enables one to locate intruders at multiple locations of a network and hence the name. The \(MILD(G)\) is the minimum cardinality of a \(MILD\) set in \(G\). Here, we show that the problem of finding MILD set for general graphs is NP-Complete. Further, we provide a linear time algorithm to find the MILD number of trees through dynamic programming approach and then, we extend the algorithm for unicyclic graphs.

Keywords


Complexity; Approximation; Multiple intruder locating domination; Chordal graph; Split graph; Bipartite graph

Full Text:

PDF

References


G.J. Chang, Algorithmic aspects of domination in graphs, in Handbook of Combinatorial Optimization, 1811 – 1877,Springer (1998), DOI: 10.1007/978-1-4613-0303-9_28.

M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NPCompleteness, W. H. Freeman & Co., USA (1979), https://dl.acm.org/doi/book/10.5555/578533.

A. González, C. Hernando and M. Mora, Metric-locating-dominating sets of graphs for constructing related subsets of vertices, Applied Mathematics and Computation 332 (2018), 449 – 456, DOI: 10.1016/j.amc.2018.03.053.

J. Guo, Z. Li and M. Lu, Locating-Total Domination in Grid Graphs, Bulletin of Malaysian Mathematical Science Society 43 (2020), 1195 – 1204, DOI: 10.1007/s40840-019-00733-9.

M.G. Karpovsky, K. Chakrabarty and L. B. Levitin, On a new class of codes for identifying vertices in graphs, IEEE Transactions on Information Theory 44(2) (1998), 599 – 61, DOI: 10.1109/18.661507.

G. Rajasekar and K. Nagarajan, Algorithm for finding location domination number of Corona product of graphs, Malaya Journal of Matematik S(1), 130 – 133, DOI: 10.26637/MJM0S01/0031.

S. J. Seo and P. J. Slater, Open neighborhood locating-dominating sets, Australasian Journal of Combinatorics 46 (2010), 109 – 120, https://ajc.maths.uq.edu.au/pdf/46/ajc_v46_p109.pdf.

A. Simic, M. Bogdanovic and J. Milosevic, The binary locating-dominating number of some convex polytopes, Ars Mathematica Contemporanea 13 (2017), 367 – 377, DOI: 10.26493/1855-3974.973.479.

P. J. Slater, Fault-tolerant locating-dominating sets, Discrete Mathematics 249(1-3) (2002), 179 – 189, DOI: 10.1016/S0012-365X(01)00244-8.

P. J. Slater, Locating dominating sets and locating-dominating sets, in Graph Theory, Combinatorics and Applications: Proceedings of the Seventh Quadrennial International Conference on the Theory and Applications of Graphs, 2, 1073 – 1079 (1995), https://scholar.google.com/scholar?q= Locating%20dominating%20sets%20and%20locatingdominating%20sets.

K. Venugopal and K. A. Vidya, Multiple intruder locating dominating sets, International Journal of Scientific Research in Mathematical and Statistical Sciences 6(2) (2019), 394 – 398, https://www.isroset.org/journal/IJSRMSS/full_paper_view.php?paper_id=1315.




DOI: http://dx.doi.org/10.26713%2Fcma.v11i2.1356

Refbacks

  • There are currently no refbacks.


eISSN 0975-8607; pISSN 0976-5905