Np-completeness and bounds for disjunctive total domination subdivision

Canan Çiftçi () and Aysun Aytaç ()
Additional contact information
Canan Çiftçi: Ordu University
Aysun Aytaç: Ege University

Journal of Combinatorial Optimization, 2025, vol. 49, issue 1, No 10, 10 pages

Abstract: Abstract 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.

Keywords: Disjunctive total domination; Disjunctive total domination subdivision; NP-completeness (search for similar items in EconPapers)
Date: 2025
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-024-01245-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:49:y:2025:i:1:d:10.1007_s10878-024-01245-4

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-024-01245-4

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().