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

Vol. 11 No. 2 (2020)

Section

Research Article

License

Creative Commons Licence 4.0 by  

Authors who publish with this journal agree to the following terms:

  • Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a CCAL that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
  • Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
  • Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.