Secure total domination in chain graphs and cographs
Let G = (V,E) be a graph without isolated vertices. A subset D of vertices of G is called a total dominating set of G if for every there exists a vertex such that A total dominating set D of a graph G is called a secure total dominating set of G if for every there exists a vertex such that and is a...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Taylor & Francis Group
2020-09-01
|
| Series: | AKCE International Journal of Graphs and Combinatorics |
| Subjects: | |
| Online Access: | http://dx.doi.org/10.1016/j.akcej.2019.10.005 |
| _version_ | 1818391667149897728 |
|---|---|
| author | Anupriya Jha |
| author_facet | Anupriya Jha |
| author_sort | Anupriya Jha |
| collection | DOAJ |
| description | Let G = (V,E) be a graph without isolated vertices. A subset D of vertices of G is called a total dominating set of G if for every there exists a vertex such that A total dominating set D of a graph G is called a secure total dominating set of G if for every there exists a vertex such that and is a total dominating set of G. The secure total domination number of G, denoted by is the minimum cardinality of a secure total dominating set of G. Given a graph G, the secure total domination problem is to find a secure total dominating set of G with minimum cardinality. In this paper, we first show that the secure total domination problem is linear time solvable on graphs of bounded clique-width. We then propose linear time algorithms for computing the secure total domination number of chain graphs and cographs. |
| first_indexed | 2024-12-14T05:17:10Z |
| format | Article |
| id | doaj.art-adb5521292dc4880b411a1086d2d6de6 |
| institution | Directory Open Access Journal |
| issn | 0972-8600 2543-3474 |
| language | English |
| last_indexed | 2024-12-14T05:17:10Z |
| publishDate | 2020-09-01 |
| publisher | Taylor & Francis Group |
| record_format | Article |
| series | AKCE International Journal of Graphs and Combinatorics |
| spelling | doaj.art-adb5521292dc4880b411a1086d2d6de62022-12-21T23:15:47ZengTaylor & Francis GroupAKCE International Journal of Graphs and Combinatorics0972-86002543-34742020-09-0117382683210.1016/j.akcej.2019.10.0051738888Secure total domination in chain graphs and cographsAnupriya Jha0Indian Institute of Technology (ISM)Let G = (V,E) be a graph without isolated vertices. A subset D of vertices of G is called a total dominating set of G if for every there exists a vertex such that A total dominating set D of a graph G is called a secure total dominating set of G if for every there exists a vertex such that and is a total dominating set of G. The secure total domination number of G, denoted by is the minimum cardinality of a secure total dominating set of G. Given a graph G, the secure total domination problem is to find a secure total dominating set of G with minimum cardinality. In this paper, we first show that the secure total domination problem is linear time solvable on graphs of bounded clique-width. We then propose linear time algorithms for computing the secure total domination number of chain graphs and cographs.http://dx.doi.org/10.1016/j.akcej.2019.10.005total dominationsecure total dominationchain graphscographslinear time algorithm |
| spellingShingle | Anupriya Jha Secure total domination in chain graphs and cographs AKCE International Journal of Graphs and Combinatorics total domination secure total domination chain graphs cographs linear time algorithm |
| title | Secure total domination in chain graphs and cographs |
| title_full | Secure total domination in chain graphs and cographs |
| title_fullStr | Secure total domination in chain graphs and cographs |
| title_full_unstemmed | Secure total domination in chain graphs and cographs |
| title_short | Secure total domination in chain graphs and cographs |
| title_sort | secure total domination in chain graphs and cographs |
| topic | total domination secure total domination chain graphs cographs linear time algorithm |
| url | http://dx.doi.org/10.1016/j.akcej.2019.10.005 |
| work_keys_str_mv | AT anupriyajha securetotaldominationinchaingraphsandcographs |