Quasi-total Roman reinforcement in graphs
| Autor: | N. Ebrahimi, J. Amjadi, M. Chellali, S.M. Sheikholeslami |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2023 |
| Předmět: | |
| Zdroj: | AKCE International Journal of Graphs and Combinatorics, Vol 20, Iss 1, Pp 1-8 (2023) |
| Druh dokumentu: | article |
| ISSN: | 09728600 2543-3474 0972-8600 |
| DOI: | 10.1080/09728600.2022.2158051 |
| Popis: | AbstractA quasi-total Roman dominating function (QTRD-function) on [Formula: see text] is a function [Formula: see text] such that (i) every vertex x for which f(x) = 0 is adjacent to at least one vertex v for which f(v) = 2, and (ii) if x is an isolated vertex in the subgraph induced by the set of vertices with non-zero values, then f(x) = 1. The weight of a QTRD-function is the sum of its function values over the whole set of vertices, and the quasi-total Roman domination number is the minimum weight of a QTRD-function on G. The quasi-total Roman reinforcement number [Formula: see text] of a graph G is the minimum number of edges that have to be added to G in order to decrease the quasi-total Roman domination number. In this paper, we initiate the study of quasi-total Roman reinforcement in graphs. We first show that the decision problem associated with the quasi-total Roman reinforcement problem is NP-hard even when restricted to bipartite graphs. Then basic properties of the quasi-total Roman reinforcement number are provided. Finally, some sharp bounds for [Formula: see text] are also presented. |
| Databáze: | Directory of Open Access Journals |
| Externí odkaz: |
|