Double Roman reinforcement number in graphs

For a graph a double Roman dominating function is a function having the property that if f(v) = 0, then vertex v must have at least two neighbors assigned 2 under f or one neighbor w with f(w) = 3, and if f(v) = 1, then vertex v must have at least one neighbor w with The weight of a double Roman dom...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	J. Amjadi, H. Sadeghi
Formato:	article
Lenguaje:	EN
Publicado:	Taylor & Francis Group 2021
Materias:	double roman domination number double roman reinforcement number complexity Mathematics QA1-939
Acceso en línea:	https://doaj.org/article/891302961fe3473ebd5cfcd180741879
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:891302961fe3473ebd5cfcd180741879
record_format	dspace
spelling	oai:doaj.org-article:891302961fe3473ebd5cfcd1807418792021-11-11T14:23:41ZDouble Roman reinforcement number in graphs0972-86002543-347410.1080/09728600.2021.1997557https://doaj.org/article/891302961fe3473ebd5cfcd1807418792021-10-01T00:00:00Zhttp://dx.doi.org/10.1080/09728600.2021.1997557https://doaj.org/toc/0972-8600https://doaj.org/toc/2543-3474For a graph a double Roman dominating function is a function having the property that if f(v) = 0, then vertex v must have at least two neighbors assigned 2 under f or one neighbor w with f(w) = 3, and if f(v) = 1, then vertex v must have at least one neighbor w with The weight of a double Roman dominating function f is the value The double Roman domination number of a graph G, denoted by equals the minimum weight of a double Roman dominating function on G. The double Roman reinforcement number of a graph G is the minimum number of edges that have to be added to G in order to decrease the double Roman domination number. In this paper, we first show that the decision problem associated to the double Roman reinforcement problem is NP-hard even when restricted to bipartite graphs and then we investigate the properties of double Roman reinforcement number in graphs, and we present some sharp bounds for Next we characterize trees with double Roman reinforcement number greater than one.J. AmjadiH. SadeghiTaylor & Francis Grouparticledouble roman domination numberdouble roman reinforcement numbercomplexityMathematicsQA1-939ENAKCE International Journal of Graphs and Combinatorics, Vol 0, Iss 0, Pp 1-9 (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	double roman domination number double roman reinforcement number complexity Mathematics QA1-939
spellingShingle	double roman domination number double roman reinforcement number complexity Mathematics QA1-939 J. Amjadi H. Sadeghi Double Roman reinforcement number in graphs
description	For a graph a double Roman dominating function is a function having the property that if f(v) = 0, then vertex v must have at least two neighbors assigned 2 under f or one neighbor w with f(w) = 3, and if f(v) = 1, then vertex v must have at least one neighbor w with The weight of a double Roman dominating function f is the value The double Roman domination number of a graph G, denoted by equals the minimum weight of a double Roman dominating function on G. The double Roman reinforcement number of a graph G is the minimum number of edges that have to be added to G in order to decrease the double Roman domination number. In this paper, we first show that the decision problem associated to the double Roman reinforcement problem is NP-hard even when restricted to bipartite graphs and then we investigate the properties of double Roman reinforcement number in graphs, and we present some sharp bounds for Next we characterize trees with double Roman reinforcement number greater than one.
format	article
author	J. Amjadi H. Sadeghi
author_facet	J. Amjadi H. Sadeghi
author_sort	J. Amjadi
title	Double Roman reinforcement number in graphs
title_short	Double Roman reinforcement number in graphs
title_full	Double Roman reinforcement number in graphs
title_fullStr	Double Roman reinforcement number in graphs
title_full_unstemmed	Double Roman reinforcement number in graphs
title_sort	double roman reinforcement number in graphs
publisher	Taylor & Francis Group
publishDate	2021
url	https://doaj.org/article/891302961fe3473ebd5cfcd180741879
work_keys_str_mv	AT jamjadi doubleromanreinforcementnumberingraphs AT hsadeghi doubleromanreinforcementnumberingraphs
_version_	1718438956067979264

Double Roman reinforcement number in graphs

Ejemplares similares