A Minimum Extended Connected Dominating Set in Interval Graphs with an Application to Railway Track Monitoring

Authors

  • Prodyot Ghara Research Centre in Natural and Applied Sciences, Raja N. L. Khan Women’s College, Midnapore 721102, India.
  • Mangal Pati Department of Mathematics, Asian International University, Imphal West 795113, India.
  • Sukumar Department of Mathematics, Raja N. L. Khan Women’s College, Midnapore 721102, India.
  • Sambhu Charan Barman * Department of Mathematics, Shahid Matangini Hazra Government General Degree College forWomen, Tamluk 721649, India.
  • Uma Shankar Department of Mathematics, Asian International University, Imphal West 795113, India.

https://doi.org/10.48314/tsc.v1i3.70

Abstract

For a graph G = (V, E) and a positive integer k, a set S ⊆ V is a k-extended dominating set if every vertex lies within distance one of S or has at least k distinct members of S at distance two. The minimum cardinality of such a set is denoted by γe k(G). For k = 2, a connected induced subgraph on S gives an extended connected dominating set. This paper studies structural properties of extended connected dominating sets in interval graphs whose intervals are ordered by nondecreasing right endpoint. An ordered sweep algorithm is presented for constructing a minimum extended connected dominating set under the stated selection invariants. With presorted interval endpoints and forward-only scan pointers, its running time and auxiliary storage are O(n). A railway-track monitoring example illustrates how the interval model can select a small connected sensor backbone while retaining two-hop redundancy. The application is illustrative and assumes a linear track, deterministic overlap, and equal communication ranges.

Keywords:

Extended domination, Connected dominating set, Interval graph, Linear-time sweep, Railway monitoring

References

  1. [1] Berge, C. (1962). The theory of graphs and its applications. Methuen & Co. Ltd., London. https://books.google.com/books/about/The_Theory_of_Graphs_and_Its_Application.html?id=Jd9QAAAAMAAJ
  2. [2] Ore, O. (1962). Theory of graphs. American Mathematical Society. https://doi.org/10.1090/coll/038
  3. [3] Haynes, T. W., Hedetniemi, S., & Slater, P. (1998). Fundamentals of domination in graphs. CRC Press. https://doi.org/10.1201/9781482246582
  4. [4] Stojmenovic, I., Seddigh, M., & Zunic, J. (2002). Dominating sets and neighbor elimination-based broadcasting algorithms in wireless networks. IEEE transactions on parallel and distributed systems, 13(1), 14-25. https://doi.org/10.1109/71.980024
  5. [5] Carle, J., & Simplot-Ryl, D. (2004). Energy-efficient area monitoring for sensor networks. Computer, 37(2), 40-46. https://doi.org/10.1109/MC.2004.1266294
  6. [6] Sampathkumar, E., & Walikar, H. B. (1979). The connected domination number of a graph. Journal of mathematical and physical sciences, 13(6), 607–613.
  7. [7] D’Atri, A., & Moscarini, M. (1988). Distance-hereditary graphs, Steiner trees, and connected domination. SIAM journal on computing, 17(3), 521-538. https://doi.org/10.1137/0217032
  8. [8] Demaine, E. D., Fomin, F. V., Hajiaghayi, M., & Thilikos, D. M. (2005). Fixed-parameter algorithms for (k, r)-center in planar graphs and map graphs. ACM transactions on algorithms (TALG), 1(1), 33-47. https://doi.org/10.1145/1077464.1077468
  9. [9] Kundu, S., & Majumder, S. (2016). A linear time algorithm for optimal k-hop dominating set of a tree. Information processing letters, 116(2), 197-202. https://doi.org/10.1016/j.ipl.2015.07.014
  10. [10] Slater, P. J. (1976). R-domination in graphs. Journal of the ACM (JACM), 23(3), 446-450. https://doi.org/10.1145/321958.321964
  11. [11] Meybodi, M. A. (2022). k-Efficient domination: Algorithmic perspective. Discrete mathematics, algorithms and applications, 14(08), 2250051. https://doi.org/10.1142/S1793830922500513
  12. [12] Kumar, M. K., & Reddy, L. S. (2013). Inverse Roman domination in graphs. Discrete mathematics, algorithms and applications, 5(03), 1350011. https://doi.org/10.1142/S1793830913500110
  13. [13] Senthilkumar, B., Naresh Kumar, H., & Venkatakrishnan, Y. B. (2021). Bounds on total edge domination number of a tree. Discrete mathematics, algorithms and applications, 13(02), 2150011. https://doi.org/10.1142/S1793830921500117
  14. [14] Sahul Hamid, I., & Balamurugan, S. (2015). Vertex criticality with respect to isolate domination. Discrete mathematics, algorithms and applications, 7(02), 1550010. https://doi.org/10.1142/S179383091550010X
  15. [15] Duraisamy, P., & Esakkimuthu, S. (2021). Linear programming approach for various domination parameters. Discrete mathematics, algorithms and applications, 13(01), 2050096. https://doi.org/10.1142/S1793830920500962
  16. [16] Gupta, P., Goyal, A., & Arumugam, S. (2023). Line-set domination in graphs. Discrete mathematics, algorithms and applications, 15(05), 2250117. https://doi.org/10.1142/S1793830922501178
  17. [17] Chang, G. J. (1998). Algorithmic aspects of domination in graphs. In Handbook of combinatorial optimization: Volume1–3 (pp. 1811-1877). Boston, MA: Springer US. https://doi.org/10.1007/978-1-4613-0303-9_28
  18. [18] Kang, C. X., & Yi, E. (2018). Bounds on the sum of domination number and metric dimension of graphs. Discrete mathematics, algorithms and applications, 10(05), 1850066. https://doi.org/10.1142/S1793830918500660
  19. [19] Rana, A. (2021). A survey on the domination of fuzzy graphs. Discrete mathematics, algorithms and applications, 13(01), 2130001. https://doi.org/10.1142/S1793830921300010
  20. [20] Cockayne, E. J., Dawes, R. M., & Hedetniemi, S. T. (1980). Total domination in graphs. Networks, 10(3), 211-219. https://doi.org/10.1002/net.3230100304
  21. [21] Chao, H. S., Hsu, F. R., & Lee, R. C. T. (2000). An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs. Discrete applied mathematics, 102(3), 159-173. https://doi.org/10.1016/S0166-218X(98)00145-0
  22. [22] Van Der Merwe, L. C., Mynhardt, C. M., & Haynes, T. W. (1998). Criticality index of total domination. Congressus numerantium, 67-74.
  23. [23] Van der Merwe, L. C., Mynhardt, C. M., & Haynes, T. W. (1998). Total domination edge critical graphs. Utilitas mathematica, 54, 229-240. https://dc.etsu.edu/etsu-works/13145/
  24. [24] Haynes, T. W. (1998). Domination in graphs: Advanced topics. Routledge. https://doi.org/10.1201/9781315141428
  25. [25] Haynes, T. W., Mynhardt, C. M., & van der Merwe, L. C. (2001). Total domination edge critical graphs with maximum diameter. Discuss. Math. Graph Theory, 21(2), 187-205.
  26. [26] Sumner, D. P., & Blitch, P. (1983). Domination critical graphs. Journal of combinatorial theory, series B, 34(1), 65-76. https://doi.org/10.1016/0095-8956(83)90007-2
  27. [27] Carlisle, M. C., & Lloyd, E. L. (1991, May). On the k-coloring of intervals. International conference on computing and information (pp. 90-101). Berlin, Heidelberg: Springer Berlin Heidelberg. https://doi.org/10.1007/3-540-54029-6_157
  28. [28] Jungck, J. R., Dick, G., & Dick, A. G. (1982). Computer-assisted sequencing, interval graphs, and molecular evolution. Biosystems, 15(3), 259-273. https://doi.org/10.1016/0303-2647(82)90010-7
  29. [29] Golumbic, M. C. (2004). Algorithmic graph theory and perfect graphs (Vol. 57). Elsevier. https://shop.elsevier.com/books/algorithmic-graph-theory-and-perfect-graphs/golumbic/978-0-444-51530-8
  30. [30] Fabri, J. (1979). Automatic storage optimization. UMI Research Press.
  31. [31] Ohtsuki, T., Mori, H., Kuh, E., Kashiwabara, T., & Fujisawa, T. (1979). One-dimensional logic gate assignment and interval graphs. IEEE Transactions on Circuits and Systems, 26(9), 675-684. https://ieeexplore.ieee.org/document/1084695/
  32. [32] Hashimoto, A., & Stevens, J. (1971. Wire routing by optimizing channel assignment within large apertures. Proceedings of the 8th design automation workshop (pp. 155-169). ACM Digital Library. https://doi.org/10.1145/800158.805069
  33. [33] Olariu, S. (1991). An optimal greedy heuristic to color interval graphs. Information processing letters, 37(1), 21-25. https://doi.org/10.1016/0020-0190(91)90245-D
  34. [34] Guha, S., & Khuller, S. (1998). Approximation algorithms for connected dominating sets. Algorithmica, 20(4), 374-387. https://doi.org/10.1007/PL00009201
  35. [35] Fink, J. F., & Jacobson, M. S. (1985). On n-domination, k-domination, and graph products with applications to coverings and independence. Congr. Numer. 49, 87–95.
  36. [36] Wu, J. (2002). Extended dominating-set-based routing in ad hoc wireless networks with unidirectional links. IEEE transactions on parallel and distributed systems, 13(9), 866-881. https://doi.org/10.1109/TPDS.2002.1036062
  37. [37] Wu, J., Cardei, M., Dai, F., & Yang, S. (2006). Extended dominating set and its applications in ad hoc networks using cooperative communication. IEEE transactions on parallel and distributed systems, 17(8), 851-864. https://doi.org/10.1109/TPDS.2006.103
  38. [38] Gao, Z., Shi, Y., Xi, C., & Yue, J. (2023). The extended dominating sets in graphs. Asia-pacific journal of operational research, 40(05), 2340015. https://doi.org/10.1142/S0217595923400158

Downloads

Published

2025-09-21

Issue

Vol. 1 No. 3 (2025): Transactions on Soft Computing

Section

Articles

License

Copyright (c) 2026 Transactions on Soft Computing

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

How to Cite

Ghara, P., Pati, M., Sukumar, Barman, S. C., & Shankar, U. (2025). A Minimum Extended Connected Dominating Set in Interval Graphs with an Application to Railway Track Monitoring. Transactions on Soft Computing , 1(3), 217-228. https://doi.org/10.48314/tsc.v1i3.70

Similar Articles

1-10 of 14

You may also start an advanced similarity search for this article.