Computational Complexity of Outer-Independent Total and Total Roman Domination Numbers in Trees
An outer-independent total dominating set (OITDS) of a graph G is a set D of vertices of G such that every vertex of G has a neighbor in D, and the set V (G) \ D is independent. The outer-independent total domination number of a graph G, denoted by γ<sub>oit</sub>(G), is the m...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2018-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/8401493/ |
| _version_ | 1819171929013092352 |
|---|---|
| author | Zepeng Li Zehui Shao Fangnian Lang Xiaosong Zhang Jia-Bao Liu |
| author_facet | Zepeng Li Zehui Shao Fangnian Lang Xiaosong Zhang Jia-Bao Liu |
| author_sort | Zepeng Li |
| collection | DOAJ |
| description | An outer-independent total dominating set (OITDS) of a graph G is a set D of vertices of G such that every vertex of G has a neighbor in D, and the set V (G) \ D is independent. The outer-independent total domination number of a graph G, denoted by γ<sub>oit</sub>(G), is the minimum cardinality of an OITDS of G. An outer-independent total Roman dominating function (OITRDF) on a graph G is a function f : V(G) → {0, 1, 2} satisfying the conditions that every vertex u with f (u) = 0 is adjacent to at least one vertex v with f (v) = 2, every vertex x with f (x) ≥ 1 is adjacent to at least one vertex y with f (y) ≥ 1, and any two different vertices a, b with f (a) = f (b) = 0 are not adjacent. The minimum weight ω( f) = Σ<sub>v∈V(G)</sub> f (v) of any OITRDF f for G is the outer-independent total Roman domination number of G, denoted by γ<sub>oitR</sub>(G). A graph G is called an outer-independent total Roman graph (OIT-Roman graph) if γ<sub>oitR</sub>(G) = 2γ<sub>oit</sub>(G). In this paper, we propose dynamic programming algorithms to compute the outer-independent total domination number and the outer-independent total Roman domination number of a tree, respectively. Moreover, we characterize all OIT-Roman graphs and give a linear time algorithm for recognizing an OIT-Roman graph. |
| first_indexed | 2024-12-22T19:59:05Z |
| format | Article |
| id | doaj.art-72b553d5574f48d1a2fb4855a16eb6ba |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-12-22T19:59:05Z |
| publishDate | 2018-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-72b553d5574f48d1a2fb4855a16eb6ba2022-12-21T18:14:19ZengIEEEIEEE Access2169-35362018-01-016355443555010.1109/ACCESS.2018.28519728401493Computational Complexity of Outer-Independent Total and Total Roman Domination Numbers in TreesZepeng Li0Zehui Shao1https://orcid.org/0000-0003-0764-4135Fangnian Lang2Xiaosong Zhang3Jia-Bao Liu4https://orcid.org/0000-0002-9620-7692School of Information Science and Engineering, Lanzhou University, Lanzhou, ChinaInstitute of Computing Science and Technology, Guangzhou University, Guangzhou, ChinaSchool of Information Science and Engineering, Chengdu University, Chengdu, ChinaCenter for Cyber Security, University of Electronic Science and Technology of China, Chengdu, ChinaSchool of Mathematics and Physics, Anhui Jianzhu University, Hefei, ChinaAn outer-independent total dominating set (OITDS) of a graph G is a set D of vertices of G such that every vertex of G has a neighbor in D, and the set V (G) \ D is independent. The outer-independent total domination number of a graph G, denoted by γ<sub>oit</sub>(G), is the minimum cardinality of an OITDS of G. An outer-independent total Roman dominating function (OITRDF) on a graph G is a function f : V(G) → {0, 1, 2} satisfying the conditions that every vertex u with f (u) = 0 is adjacent to at least one vertex v with f (v) = 2, every vertex x with f (x) ≥ 1 is adjacent to at least one vertex y with f (y) ≥ 1, and any two different vertices a, b with f (a) = f (b) = 0 are not adjacent. The minimum weight ω( f) = Σ<sub>v∈V(G)</sub> f (v) of any OITRDF f for G is the outer-independent total Roman domination number of G, denoted by γ<sub>oitR</sub>(G). A graph G is called an outer-independent total Roman graph (OIT-Roman graph) if γ<sub>oitR</sub>(G) = 2γ<sub>oit</sub>(G). In this paper, we propose dynamic programming algorithms to compute the outer-independent total domination number and the outer-independent total Roman domination number of a tree, respectively. Moreover, we characterize all OIT-Roman graphs and give a linear time algorithm for recognizing an OIT-Roman graph.https://ieeexplore.ieee.org/document/8401493/Outer-independent total dominationouter-independent total Roman dominationouter-independent total Roman graphtreealgorithm |
| spellingShingle | Zepeng Li Zehui Shao Fangnian Lang Xiaosong Zhang Jia-Bao Liu Computational Complexity of Outer-Independent Total and Total Roman Domination Numbers in Trees IEEE Access Outer-independent total domination outer-independent total Roman domination outer-independent total Roman graph tree algorithm |
| title | Computational Complexity of Outer-Independent Total and Total Roman Domination Numbers in Trees |
| title_full | Computational Complexity of Outer-Independent Total and Total Roman Domination Numbers in Trees |
| title_fullStr | Computational Complexity of Outer-Independent Total and Total Roman Domination Numbers in Trees |
| title_full_unstemmed | Computational Complexity of Outer-Independent Total and Total Roman Domination Numbers in Trees |
| title_short | Computational Complexity of Outer-Independent Total and Total Roman Domination Numbers in Trees |
| title_sort | computational complexity of outer independent total and total roman domination numbers in trees |
| topic | Outer-independent total domination outer-independent total Roman domination outer-independent total Roman graph tree algorithm |
| url | https://ieeexplore.ieee.org/document/8401493/ |
| work_keys_str_mv | AT zepengli computationalcomplexityofouterindependenttotalandtotalromandominationnumbersintrees AT zehuishao computationalcomplexityofouterindependenttotalandtotalromandominationnumbersintrees AT fangnianlang computationalcomplexityofouterindependenttotalandtotalromandominationnumbersintrees AT xiaosongzhang computationalcomplexityofouterindependenttotalandtotalromandominationnumbersintrees AT jiabaoliu computationalcomplexityofouterindependenttotalandtotalromandominationnumbersintrees |