Further results on the hop domination number of a graph
| Autor: | D. Anusha, S. Joseph Robin, J. John |
|---|---|
| Jazyk: | English<br />Portuguese |
| Rok vydání: | 2024 |
| Předmět: | |
| Zdroj: | Boletim da Sociedade Paranaense de Matemática, Vol 42 (2024) |
| Druh dokumentu: | article |
| ISSN: | 0037-8712 2175-1188 |
| DOI: | 10.5269/bspm.63022 |
| Popis: | 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. |
| Databáze: | Directory of Open Access Journals |
| Externí odkaz: |
|