DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume

Authors:

M.A. Henning

Michael A. Henning

University of Johannesburg

email: mahenning@uj.ac.za

0000-0001-8185-067X

S. Pal

Saikat Pal

Department of Applied Mathematics.
Indian Institute of Technology(ISM), Dhanbad
Dhanbad, Jharkhand-826004

email: palsaikat67@gmail.com

D. Pradhan

Dinabandhu Pradhan

Department of Mathematics and Computing, Indian Institute of Technology (ISM), Dhanbad

email: dina@iitism.ac.in

Title:

Hop domination in chordal bipartite graphs

PDF

Source:

Discussiones Mathematicae Graph Theory 43(3) (2023) 825-840

Received: 2020-11-21 , Revised: 2021-03-12 , Accepted: 2021-03-18 , Available online: 2021-04-14 , https://doi.org/10.7151/dmgt.2403

Abstract:

In a graph $G$, a vertex is said to $2$-step dominate itself and all the vertices which are at distance $2$ from it in $G$. A set $D$ of vertices in $G$ is called a hop dominating set of $G$ if every vertex outside $D$ is $2$-step dominated by some vertex of $D$. Given a graph $G$ and a positive integer $k$, the hop domination problem is to decide whether $G$ has a hop dominating set of cardinality at most $k$. The hop domination problem is known to be NP-complete for bipartite graphs. In this paper, we design a linear time algorithm for computing a minimum hop dominating set in chordal bipartite graphs.

Keywords:

domination, hop domination, polynomial time algorithm, chordal bipartite graphs

References:

  1. S.K. Ayyaswamy and C. Natarajan, Hop domination in graphs, manuscript.
  2. S.K. Ayyaswamy, B. Krishnakumari, C. Natarajan and Y.B. Venkatakrishnan, Bounds on the hop domination number of a tree, Proc. Indian Acad. Sci. Math. Sci. 125 (2015) 449–455.
    https://doi.org/10.1007/s12044-015-0251-6
  3. A. Brandstädt, V.B. Le and J.P. Spinrad, Graph Classes: A Survey (SIAM, Philadelphia, PA, USA, 1999).
    https://doi.org/10.1137/1.9780898719796
  4. Y. Caro, A. Lev and Y. Roditty, Some results in step domination of graphs, Ars Combin. 68 (2003) 105–114.
  5. M.S. Chang, Algorithms for maximum matching and minimum fill-in on chordal bipartite graphs, 7th ISAAC, Lecture Notes in Comput. Sci. 1178 (1996) 146–155.
    https://doi.org/10.1007/BFb0009490
  6. G. Chartrand, F. Harary, M. Hossain and K. Schultz, Exact $2 $-step domination in graphs, Math. Bohem. 120 (1995) 125–134.
    https://doi.org/10.21136/MB.1995.126228
  7. X. Chen and Y. Wang, On total domination and hop domination in diamond-free graphs, Bull. Malays. Math. Sci. Soc. 43 (2020) 1885–1891.
    https://doi.org/10.1007/s40840-019-00778-w
  8. P. Damaschke, H. Müller and D. Kratsch, Domination in convex and chordal bipartite graphs, Inform. Process. Lett. 36 (1990) 231–236.
    https://doi.org/10.1016/0020-0190(90)90147-P
  9. G. Dror, A. Lev and Y. Roditty, A note: some results in step domination of trees, Discrete Math. 289 (2004) 137–144.
    https://doi.org/10.1016/j.disc.2004.08.007
  10. F. Foucaud, Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes, J. Discrete Algorithms 31 (2015) 48–68.
    https://doi.org/10.1016/j.jda.2014.08.004
  11. T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker Inc., New York, 1998).
  12. T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (Marcel Dekker Inc., New York, 1998).
  13. M.A. Henning and N. Jafari Rad, On $2$-step and hop dominating sets in graphs, Graphs Combin. 33 (2017) 913–927.
    https://doi.org/10.1007/s00373-017-1789-0
  14. M.A. Henning, S. Pal and D. Pradhan, Algorithm and hardness results on hop domination in graphs, Inform. Process. Lett. 153 (2020) 105872.
    https://doi.org/10.1016/j.ipl.2019.105872
  15. P. Hersh, On exact $n$-step domination, Discrete Math. 205 (1999) 235–239.
    https://doi.org/10.1016/S0012-365X(99)00024-2
  16. M. Farhadi Jalalvand and N. Jafari Rad, On the complexity of k-step and k-hop dominating sets in graphs, Math. Montisnigri 40 (2017) 36–41.
  17. S. Kundu and S. Majumder, A linear time algorithm for optimal $k$-hop dominating set of a tree, Inform. Process. Lett. 116 (2016) 197–202.
    https://doi.org/10.1016/j.ipl.2015.07.014
  18. H. Müller and A. Brandstädt, The NP-completeness of Steiner Tree and Dominating Set for chordal bipartite graphs, Theoret. Comput. Sci. 53 (1987) 257–265.
    https://doi.org/10.1016/0304-3975(87)90067-3
  19. C. Natarajan and S.K. Ayyaswamy, Hop domination in graphs-II, An. Stiint. Univ. ``Ovidius'' Constanta Ser. Mat. 23 (2015) 187–199.
    https://doi.org/10.1515/auom-2015-0036
  20. C. Natarajan and S.K. Ayyaswamy, A note on the hop domination number of a subdivision graph, Int. J. Appl. Math. 32 (2019) 381–390.
    https://doi.org/10.12732/ijam.v32i3.2
  21. C. Natarajan, S.K. Ayyaswamy and G. Sathiamoorthy, A note on hop domination number of some special families of graphs, Int. J. Pure Appl. Math. 119 (2018) 14165–14171.
  22. B.S. Panda and D. Pradhan, Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs, J. Comb. Optim. 26 (2013) 770–785.
    https://doi.org/10.1007/s10878-012-9483-x
  23. D. Pradhan, Complexity of certain functional variants of total domination in chordal bipartite graphs, Discrete Math. Algorithms Appl. 4(3) (2012) 1250045.
    https://doi.org/10.1142/S1793830912500450
  24. Y.M. Pabilona and H.M. Rara, Connected hop domination in graphs under some binary operations, Asian-Eur. J. Math. 11 (2018) 1850075.
    https://doi.org/10.1142/S1793557118500754
  25. H. Rahbani, N. Jafari Rad and M.R. Sadeghi, A note on the complexity of locating-total domination in graphs, Theoret. Comput. Sci. 799 (2019) 32–39.
    https://doi.org/10.1016/j.tcs.2019.09.039
  26. R.C. Rakim, C.J.C. Saromines and H.M. Rara, Perfect hop domination in graphs, Appl. Math. Sci. 12 (2018) 635–649.
    https://doi.org/10.12988/ams.2018.8576
  27. R. Uehara, Linear time algorithms on chordal bipartite and strongly chordal graphs, in: Automata, Languages and Programming, Lecture Notes in Comput. Sci. 2380 (2002) 993–1004.
    https://doi.org/10.1007/3-540-45465-9_85
Close