Complexity Issues of Perfect Roman Domination in Graphs
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
Given a graph G and a positive integer k, the PRDF problem is to check whether G has a perfect Roman dominating function of weight at most k. In this paper, we first investigate the complexity of PRDF problem for some subclasses of bipartite graphs namely, star convex bipartite graphs and comb convex bi-partite graphs. Then we show that PRDF problem is linear time solvable for bounded tree-width graphs, chain graphs and threshold graphs, a subclass of split graphs.
Abstract
Given a graph G and a positive integer k, the PRDF problem is to check whether G has a perfect Roman dominating function of weight at most k. In this paper, we first investigate the complexity of PRDF problem for some subclasses of bipartite graphs namely, star convex bipartite graphs and comb convex bi-partite graphs. Then we show that PRDF problem is linear time solvable for bounded tree-width graphs, chain graphs and threshold graphs, a subclass of split graphs.
참고문헌 (15)
- B. Courcelle, "The monadic second-order logic of graphs. I. Recognizable sets of finite graphs", Inf. Comput, 85, pp.12~75 (1990)
- C. E. Leiserson, "Introduction to algorithms" (2001), MIT press
- D. B. West, "Introduction to Graph Theory" (2001), Prentice hall
- E. J. Cockayne, "Roman domination in graphs", Discrete Math, 278, pp.11~22 (2004)
- M. Yannakakis, "Node-and edge-deletion np-complete problems", Proceedings of the Tenth Annual ACM Symposium on Theo. of Comp, pp.253~264 (1978), STOC
- M. Lin, "Counting independent sets in tree convex bipartite graphs", Discrete Appl. Math, 218, pp.113~122 (2017)
- M. R. Garey, "Computers and Interactability : A Guide to the Theory of NP-completeness" (1979), Freeman
- M. A. Henning, "Perfect Roman domination in trees", Discrete Appl. Math, 236, pp.235~245 (2018)
- M. Darkooti, "On perfect Roman domination number in trees : complexity and bounds", Journal of Combinatorial Optimization, 38, pp.712~720 (2019)
- N. J. Rad, "Roman domination perfect graphs", An. Stiint. Univ. Ovidius Constanta Ser. Mat, 19, pp.167~174 (2019)
- N. Mahadev, "Threshold graphs and related topics, Annals of Discrete Mathematics" (1995), North Holland
- O. Favaron H. Karami, "On the Roman domination number of a graph", Discrete Math, 309, pp.3447~3451 (2009)
- R. Uehara, "Efficient algorithms for the longest path problem", International symposium on algorithms and computation, pp.871~883 (2004)
- S. Banerjee, "Perfect Roman domination in graphs", Theor. Comput. Sci (2019)
- T. W. Haynes, "Fundamentals of domination in graphs" (1998), CRC Press