Total Roman domination for proper interval graphs
<p>A function <em>f</em>:<em>V</em> → {0,1,2} is a total Roman dominating function (TRDF) on a graph <em>G</em>=(<em>V,E</em>) if for every vertex <em>v</em> ∈ <em>V</em> with <em>f</em>(<em>v</em>)...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Indonesian Combinatorial Society (InaCombS); Graph Theory and Applications (GTA) Research Centre; University of Newcastle, Australia; Institut Teknologi Bandung (ITB), Indonesia
2020-10-01
|
| Series: | Electronic Journal of Graph Theory and Applications |
| Subjects: | |
| Online Access: | https://www.ejgta.org/index.php/ejgta/article/view/952 |
| _version_ | 1828218839242899456 |
|---|---|
| author | Abolfazl Poureidi |
| author_facet | Abolfazl Poureidi |
| author_sort | Abolfazl Poureidi |
| collection | DOAJ |
| description | <p>A function <em>f</em>:<em>V</em> → {0,1,2} is a total Roman dominating function (TRDF) on a graph <em>G</em>=(<em>V,E</em>) if for every vertex <em>v</em> ∈ <em>V</em> with <em>f</em>(<em>v</em>) = 0 there is a vertex <em>u</em> adjacent to <em>v</em> with <em>f</em>(<em>u</em>) = 2 and for every vertex <em>v </em>∈<em> V</em> with <em>f</em>(<em>v</em>) > 0 there exists a vertex <em>u</em> ∈ <em>N</em><sub><em>G</em>(<em>v</em>)</sub> with <em>f</em>(<em>u</em>) > 0. The weight of a total Roman dominating function <em>f</em> on <em>G</em> is equal to <em>f</em>(<em>V</em>)=Σ<sub>v ∈ V</sub><em>f</em>(<em>v</em>). The minimum weight of a total Roman dominating function on <em>G</em> is called the total Roman domination number of <em>G</em>. In this paper, we give an algorithm to compute the total Roman domination number of a given proper interval graph <em>G</em>=(<em>V,E</em>) in <em>O</em>(|<em>V</em>|) time.</p> |
| first_indexed | 2024-04-12T16:08:40Z |
| format | Article |
| id | doaj.art-24865818ae874f17a84c87e8a1ca52a5 |
| institution | Directory Open Access Journal |
| issn | 2338-2287 |
| language | English |
| last_indexed | 2024-04-12T16:08:40Z |
| publishDate | 2020-10-01 |
| publisher | Indonesian Combinatorial Society (InaCombS); Graph Theory and Applications (GTA) Research Centre; University of Newcastle, Australia; Institut Teknologi Bandung (ITB), Indonesia |
| record_format | Article |
| series | Electronic Journal of Graph Theory and Applications |
| spelling | doaj.art-24865818ae874f17a84c87e8a1ca52a52022-12-22T03:25:57ZengIndonesian Combinatorial Society (InaCombS); Graph Theory and Applications (GTA) Research Centre; University of Newcastle, Australia; Institut Teknologi Bandung (ITB), IndonesiaElectronic Journal of Graph Theory and Applications2338-22872020-10-018240141310.5614/ejgta.2020.8.2.16192Total Roman domination for proper interval graphsAbolfazl Poureidi0Faculty of Mathematical Sciences, Shahrood University of Technology, Shahrood, Iran<p>A function <em>f</em>:<em>V</em> → {0,1,2} is a total Roman dominating function (TRDF) on a graph <em>G</em>=(<em>V,E</em>) if for every vertex <em>v</em> ∈ <em>V</em> with <em>f</em>(<em>v</em>) = 0 there is a vertex <em>u</em> adjacent to <em>v</em> with <em>f</em>(<em>u</em>) = 2 and for every vertex <em>v </em>∈<em> V</em> with <em>f</em>(<em>v</em>) > 0 there exists a vertex <em>u</em> ∈ <em>N</em><sub><em>G</em>(<em>v</em>)</sub> with <em>f</em>(<em>u</em>) > 0. The weight of a total Roman dominating function <em>f</em> on <em>G</em> is equal to <em>f</em>(<em>V</em>)=Σ<sub>v ∈ V</sub><em>f</em>(<em>v</em>). The minimum weight of a total Roman dominating function on <em>G</em> is called the total Roman domination number of <em>G</em>. In this paper, we give an algorithm to compute the total Roman domination number of a given proper interval graph <em>G</em>=(<em>V,E</em>) in <em>O</em>(|<em>V</em>|) time.</p>https://www.ejgta.org/index.php/ejgta/article/view/952total roman domination, algorithm, proper interval graph |
| spellingShingle | Abolfazl Poureidi Total Roman domination for proper interval graphs Electronic Journal of Graph Theory and Applications total roman domination, algorithm, proper interval graph |
| title | Total Roman domination for proper interval graphs |
| title_full | Total Roman domination for proper interval graphs |
| title_fullStr | Total Roman domination for proper interval graphs |
| title_full_unstemmed | Total Roman domination for proper interval graphs |
| title_short | Total Roman domination for proper interval graphs |
| title_sort | total roman domination for proper interval graphs |
| topic | total roman domination, algorithm, proper interval graph |
| url | https://www.ejgta.org/index.php/ejgta/article/view/952 |
| work_keys_str_mv | AT abolfazlpoureidi totalromandominationforproperintervalgraphs |