Multiple Intruder Locating Dominating Sets in Graphs: An Algorithmic Approach

Authors

  • K. Venugopal Department of Mathematics, R.V. College of Engineering, Bengaluru 560059, Karnataka
  • K. A. Vidya Department of Mathematics, Dayananda Sagar Academy of Technology and Management, Bengaluru 560082, Karnataka

DOI:

https://doi.org/10.26713/cma.v11i2.1356

Keywords:

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

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.

Downloads

Download data is not yet available.

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.

Downloads

Published

30-06-2020
CITATION

How to Cite

Venugopal, K., & Vidya, K. A. (2020). Multiple Intruder Locating Dominating Sets in Graphs: An Algorithmic Approach. Communications in Mathematics and Applications, 11(2), 259–269. https://doi.org/10.26713/cma.v11i2.1356

Issue

Section

Research Article