1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

Hop Domination in Chordal Bipartite Graphs

Published Online: 05 May 2021
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 21 Nov 2020
Accepted: 18 Mar 2021
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
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

MSC 2010

[1] S.K. Ayyaswamy and C. Natarajan, Hop domination in graphs, manuscript.Search in Google Scholar

[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. doi:10.1007/s12044-015-0251-610.1007/s12044-015-0251-6Search in Google Scholar

[3] A. Brandstädt, V.B. Le and J.P. Spinrad, Graph Classes: A Survey (SIAM, Philadelphia, PA, USA, 1999). doi:10.1137/1.978089871979610.1137/1.9780898719796Search in Google Scholar

[4] Y. Caro, A. Lev and Y. Roditty, Some results in step domination of graphs, Ars Combin. 68 (2003) 105–114.Search in Google Scholar

[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. doi:10.1007/BFb000949010.1007/BFb0009490Search in Google Scholar

[6] G. Chartrand, F. Harary, M. Hossain and K. Schultz, Exact 2-step domination in graphs, Math. Bohem. 120 (1995) 125–134. doi:10.21136/MB.1995.12622810.21136/MB.1995.126228Search in Google Scholar

[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. doi:10.1007/s40840-019-00778-w10.1007/s40840-019-00778-wSearch in Google Scholar

[8] P. Damaschke, H. Müller and D. Kratsch, Domination in convex and chordal bipartite graphs, Inform. Process. Lett. 36 (1990) 231–236. doi:10.1016/0020-0190(90)90147-P10.1016/0020-0190(90)90147-PSearch in Google Scholar

[9] G. Dror, A. Lev and Y. Roditty, A note: some results in step domination of trees, Discrete Math. 289 (2004) 137–144. doi:10.1016/j.disc.2004.08.00710.1016/j.disc.2004.08.007Search in Google Scholar

[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. doi:10.1016/j.jda.2014.08.00410.1016/j.jda.2014.08.004Search in Google Scholar

[11] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker Inc., New York, 1998).Search in Google Scholar

[12] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (Marcel Dekker Inc., New York, 1998).Search in Google Scholar

[13] M.A. Henning and N. Jafari Rad, On 2-step and hop dominating sets in graphs, Graphs Combin. 33 (2017) 913–927. doi:10.1007/s00373-017-1789-010.1007/s00373-017-1789-0Search in Google Scholar

[14] M.A. Henning, S. Pal and D. Pradhan, Algorithm and hardness results on hop domination in graphs, Inform. Process. Lett. 153 (2020) 105872. doi:10.1016/j.ipl.2019.10587210.1016/j.ipl.2019.105872Search in Google Scholar

[15] P. Hersh, On exact n-step domination, Discrete Math. 205 (1999) 235–239. doi:10.1016/S0012-365X(99)00024-210.1016/S0012-365X(99)00024-2Search in Google Scholar

[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.Search in Google Scholar

[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. doi:10.1016/j.ipl.2015.07.01410.1016/j.ipl.2015.07.014Search in Google Scholar

[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. doi:10.1016/0304-3975(87)90067-310.1016/0304-3975(87)90067-3Search in Google Scholar

[19] C. Natarajan and S.K. Ayyaswamy, Hop domination in graphs-II, An. Stiint. Univ. “Ovidius” Constanta Ser. Mat. 23 (2015) 187–199. doi:10.1515/auom-2015-003610.1515/auom-2015-0036Search in Google Scholar

[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. doi:10.12732/ijam.v32i3.210.12732/ijam.v32i3.2Search in Google Scholar

[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.Search in Google Scholar

[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. doi:10.1007/s10878-012-9483-x10.1007/s10878-012-9483-xSearch in Google Scholar

[23] D. Pradhan, Complexity of certain functional variants of total domination in chordal bipartite graphs, Discrete Math. Algorithms Appl. 4(3) (2012) 1250045. doi:10.1142/S179383091250045010.1142/S1793830912500450Search in Google Scholar

[24] Y.M. Pabilona and H.M. Rara, Connected hop domination in graphs under some binary operations, Asian-Eur. J. Math. 11 (2018) 1850075. doi:10.1142/S179355711850075410.1142/S1793557118500754Search in Google Scholar

[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. doi:10.1016/j.tcs.2019.09.03910.1016/j.tcs.2019.09.039Search in Google Scholar

[26] R.C. Rakim, C.J.C. Saromines and H.M. Rara, Perfect hop domination in graphs, Appl. Math. Sci. 12 (2018) 635–649. doi:10.12988/ams.2018.857610.12988/ams.2018.8576Search in Google Scholar

[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. doi:10.1007/3-540-45465-9_8510.1007/3-540-45465-9_85Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo