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

Np-completeness and bounds for disjunctive total domination subdivision

  • Canan Çiftçi,
  • Aysun Aytaç

摘要

A subset \( S\subseteq V(G) \) S V ( G ) , where V(G) is the vertex set of a graph G, is a disjunctive total dominating set of G if each vertex has a neighbour in S or has at least two vertices in S at distance two from it. The minimum cardinality of such a set is the disjunctive total domination number. There are some graph modifications on the edge or vertex of a graph, one of which is subdividing an edge. The disjunctive total domination subdivision number of G is the minimum number of edges which must be subdivided (each edge in G can be subdivided exactly once) to increase the disjunctive total domination number. Firstly, we prove that the disjunctive total domination subdivision problem is NP-complete in bipartite graphs. We next establish some bounds on disjunctive total domination subdivision.