Scholarlink

<p>Inspired by graph domination games, various domination-type vertex sequences have been introduced, including the Grundy double dominating sequence (GDDS) of a graph and its associated parameter, the Grundy double domination number (GDDN). The decision version of the problem of computing the GDDN is known to be NP-complete, even when restricted to split graphs and bipartite graphs. In this paper, we establish general tight bounds for the GDDN. We also describe GDDSs for vertex-removed graphs and for the join of two graphs. Applying these results, we prove that computing the GDDN is linear for <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(P_4\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>P</mi> <mn>4</mn> </msub> </math></EquationSource> </InlineEquation>-tidy graphs, thereby solving an open problem previously posed for cographs by B.&#xa0;Brešar et al. in [Brešar, B., Pandey, A., Sharma, G.: Computational aspects of some vertex sequences of grundy domination-type. Indian J. Discrete Math. <b>8</b>, 21–38 (2022)].</p>

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

Grundy Double Domination Number: Bounds, Graph Operations, and Efficient Computation for \(P_4\)-Tidy Graphs

  • 期刊论文

  • 发表日期：

    2026年2月5日

查看全文
  • Pablo Torres

摘要

Inspired by graph domination games, various domination-type vertex sequences have been introduced, including the Grundy double dominating sequence (GDDS) of a graph and its associated parameter, the Grundy double domination number (GDDN). The decision version of the problem of computing the GDDN is known to be NP-complete, even when restricted to split graphs and bipartite graphs. In this paper, we establish general tight bounds for the GDDN. We also describe GDDSs for vertex-removed graphs and for the join of two graphs. Applying these results, we prove that computing the GDDN is linear for \(P_4\) P 4 -tidy graphs, thereby solving an open problem previously posed for cographs by B. Brešar et al. in [Brešar, B., Pandey, A., Sharma, G.: Computational aspects of some vertex sequences of grundy domination-type. Indian J. Discrete Math. 8, 21–38 (2022)].