Algorithmic complexity of isolate secure domination in graphs
Künye
Kumar, J. P. & Reddy, P. V. S. (2021). Algorithmic complexity of isolate secure domination in graphs. TWMS Journal of Applied and Engineering Mathematics, 11(SI), 188-194.Özet
A dominating set S is an Isolate Dominating Set (IDS) if the induced subgraph G[S] has at least one isolated vertex. In this paper, we initiate the study of new domination parameter called, isolate secure domination. An isolate dominating set S subset of V is an isolate secure dominating set (ISDS), if for each vertex u is an element of V \ S, there exists a neighboring vertex v of u in S such that (S \ {v}) boolean OR {u} is an IDS of G. The minimum cardinality of an ISDS of G is called as an isolate secure domination number, and is denoted by gamma(0s) (G). We give isolate secure domination number of path and cycle graphs. Given a graph G = (V, E) and a positive integer k, the ISDM problem is to check whether G has an isolate secure dominating set of size at most k. We prove that ISDM is NP-complete even when restricted to bipartite graphs and split graphs. We also show that ISDM can be solved in linear time for graphs of bounded tree-width.
Cilt
11Sayı
SIBağlantı
http://belgelik.isikun.edu.tr/xmlui/handle/iubelgelik/3035http://jaem.isikun.edu.tr/web/index.php/archive/109-vol11-special-issue/648
Koleksiyonlar
Aşağıdaki lisans dosyası bu öğe ile ilişkilidir: