Further results on the hop domination number of a graph
Résumé
A hop dominating set S in a connected graph G is called a minimal hop dominating set if no proper subset of S is a hop dominating set of G. The upper hop domination number γ+h (G) of G is the maximum cardinality of a minimal hop dominating set of G. Some general properties satisfied by this concept are studied. It is shown that for every two positive integers a and b where 2 ≤ a ≤ b, there exists a connected graph G such that γh(G) = a and γ+ h (G) = b. It is proved that minimal hop dominating set is NP-complete. It is proved that γh(G) and γ(G) are in general incomparable. It is shown that for every pair of positive integers a and b with a ≥ 2 and b ≥ 1, there exists a connected graph G such that γh(G) = a and γ(G) = b. We present an algorithm to compute minimal hop dominating set of G. Finally, we formulate an Integer linear programming problem to compute the hop domination number of G.
Téléchargements
Références
H. Abdollahzadeh Ahangar, J. Amjadi, S. M. Sheikholeslami and M. Soroudi, On The Total Roman Domination Number of Graphs, Ars Combinatoria 150, 225-240, (2020).
A.D. Amis, R.Prakash, T.H.P. Vuong, D.T. Huynh, Max-min d-cluster formation in wireless ad hoc networks, In Proc. 19th IEEE INFOCOM 1, 32–41, (2000).
V.S. Anitha, M.P. Sebastian, (k, r)-Dominating set-based, weighted and adaptive clustering algorithms for mobile ad hoc networks, IET Communications 5, (13), 836-1853, (2011).
D.Anusha, J.John and S.Joseph Robin, Graphs with small and large hop domination numbers, Bulletin of IMVI 11(3), 483-489, (2021).
P. Basuchowdhuri, S. Majumder, Finding influential nodes in social networks using minimum k-hop dominating set, In Proc. 1st ICAA, 8321, 137–151, (2014).
F.Buckley and F.Harary, Distance in Graph, Addition-Wesly-wood city, CA (1990).
G. Chartrand, F. Harary and K. Hossain M.Schultz, Exact 2-step domination in graphs, Mathematica Bohemica 120, 125-134, (1995).
Doost Ali Mojdeh and Nader Jafari Rad, On domination and its forcing in Mycielski’s graphs, Scientia Iranica 15,(2), 218-222, (2008).
Doost Ali Mojdeh and Azam Sadat Emadi, Hop domination polynomial of graphs, Journal of Discrete Mathematical Sciences and Cryptography, 23(1),1-16,(2019).
Gemma P. Salasalan and Sergio R. Canoy, Jr.,Global hop domination numbers of graphs, European Journal of Pure And Applied Mathematics 14(1),112-125, (2021).
T.W.Haynes, S.T.Hedetniemi and P.J.Slater, Fundamentals of domination in graphs, Marcel Dekker, New York, (1998).
C.L. Liu, Introduction to Combinatorial Mathematics, Computer Science Series, McGraw-Hill, (1968).
N. Meghanathan, On the use of centrality measure to determine connected dominating sets for mobile ad hoc networks, International Journal of Ad Hoc and Ubiquitous Computing 26, (4), 205–221,(2017).
Michael A.Henning and Nader Jafari Rad, On 2-step and hop dominating sets in graphs, Graphs and Combinatorics 33,(2),1-15, (2017).
Michael A. Henning, Saikat Pal and D. Pradhan, Hop domination in chordal bipartite graphs, Discussiones Mathematicae Graph Theory, DOI:10.7151/dmgt.2403.
Michael A.Henning, Saikat Pal and D.Pradhan, Algorithm and hardness results on hop domination in graphs, Information Processing Letters 153, 105872, (2020).
Nader Jafari Rad and Elahe Shabani, On the complexity of some hop domination parameters, Electronic Journal of Graph Theory and Applications 7(1), 77-89, (2019).
C. Natarajan and S.K.Ayyaswamy, Hop domination sets in graphs-II, Analele Stiintifice ale Universitatii Ovidius Constanta, Seria Matematica,(ASUOC) 23(2), 187-199,(2015).
Copyright (c) 2024 Boletim da Sociedade Paranaense de Matemática
Ce travail est disponible sous la licence Creative Commons Attribution 4.0 International .
When the manuscript is accepted for publication, the authors agree automatically to transfer the copyright to the (SPM).
The journal utilize the Creative Common Attribution (CC-BY 4.0).
