Total Roman {3}-Domination: The Complexity and Linear-Time Algorithm for Trees

Xinyue Liu, Huiqin Jiang, Pu Wu and Zehui Shao
Additional contact information
Xinyue Liu: Institute of Computing Science and Technology, Guangzhou University, Guangzhou 510006, China
Huiqin Jiang: Institute of Computing Science and Technology, Guangzhou University, Guangzhou 510006, China
Pu Wu: Institute of Computing Science and Technology, Guangzhou University, Guangzhou 510006, China
Zehui Shao: Institute of Computing Science and Technology, Guangzhou University, Guangzhou 510006, China

Mathematics, 2021, vol. 9, issue 3, 1-7

Abstract: For a simple graph G = ( V , E ) with no isolated vertices, a total Roman {3}-dominating function(TR3DF) on G is a function f : V ( G ) ? { 0 , 1 , 2 , 3 } having the property that (i) ? w ? N ( v ) f ( w ) ? 3 if f ( v ) = 0 ; (ii) ? w ? N ( v ) f ( w ) ? 2 if f ( v ) = 1 ; and (iii) every vertex v with f ( v ) ? 0 has a neighbor u with f ( u ) ? 0 for every vertex v ? V ( G ) . The weight of a TR3DF f is the sum f ( V ) = ? v ? V ( G ) f ( v ) and the minimum weight of a total Roman {3}-dominating function on G is called the total Roman {3}-domination number denoted by ? t { R 3 } ( G ) . In this paper, we show that the total Roman {3}-domination problem is NP-complete for planar graphs and chordal bipartite graphs. Finally, we present a linear-time algorithm to compute the value of ? t { R 3 } for trees.

Keywords: dominating set; total roman {3}-domination; NP-complete; linear-time algorithm (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/3/293/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/3/293/ (text/html)

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:gam:jmathe:v:9:y:2021:i:3:p:293-:d:491394

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().