Scholarlink

A set \(S \subseteq V(G)\) is said to be a hop dominating set if every vertex \( u \in V(G) \setminus S\) , there exists a vertex \(v \in S\) such that \(d(u,v)=2\) where d(u, v) represents the distance between u and v in G. The minimum k for which there exists a hop dominating set of size k is called the hop domination number denoted by \(\gamma _{h}(G)\) . Henning et al. (Inf. Process. Lett. 2020) showed that Hop Domination  is NP-hard for bipartite graphs and chordal graphs. The following are the results of this paper.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Polynomial Time Algorithms for Hop Domination

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • D. Karthika,
  • R. Muthucumaraswamy,
  • Sriram Bhyravarapu,
  • Pritesh Kumar

摘要

A set \(S \subseteq V(G)\) is said to be a hop dominating set if every vertex \( u \in V(G) \setminus S\) , there exists a vertex \(v \in S\) such that \(d(u,v)=2\) where d(u, v) represents the distance between u and v in G. The minimum k for which there exists a hop dominating set of size k is called the hop domination number denoted by \(\gamma _{h}(G)\) . Henning et al. (Inf. Process. Lett. 2020) showed that Hop Domination  is NP-hard for bipartite graphs and chordal graphs. The following are the results of this paper.