Geodesic
Hop domination in chordal bipartite graphs
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 3, pp. 825-840 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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 
@article{DMGT_2023_43_3_a15,
     author = {Henning, Michael A. and Pal, Saikat and Pradhan, Dinabandhu},
     title = {Hop domination in chordal bipartite graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {825--840},
     year = {2023},
     volume = {43},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a15/}
}
TY  - JOUR
AU  - Henning, Michael A.
AU  - Pal, Saikat
AU  - Pradhan, Dinabandhu
TI  - Hop domination in chordal bipartite graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 825
EP  - 840
VL  - 43
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a15/
LA  - en
ID  - DMGT_2023_43_3_a15
ER  - 
%0 Journal Article
%A Henning, Michael A.
%A Pal, Saikat
%A Pradhan, Dinabandhu
%T Hop domination in chordal bipartite graphs
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 825-840
%V 43
%N 3
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a15/
%G en
%F DMGT_2023_43_3_a15
Henning, Michael A.; Pal, Saikat; Pradhan, Dinabandhu. Hop domination in chordal bipartite graphs. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 3, pp. 825-840. http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a15/

[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