Vertex–Edge Roman {2}-Domination

Vertex–Edge Roman {2}-Domination

A vertex–edge Roman <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>{</mo><mn>2</mn><mo>}</mo></mrow></semantics></math></inline-formula>-dom...

Full description

Saved in:

Bibliographic Details
Main Authors:	Ahlam Almulhim, Saiful Rahman Mondal
Format:	Article
Language:	English
Published:	MDPI AG 2025-07-01
Series:	Mathematics
Subjects:	vertex–edge domination Roman domination Roman {2}-domination paths trees
Online Access:	https://www.mdpi.com/2227-7390/13/13/2169
Tags:	Add Tag No Tags, Be the first to tag this record!

Description
Summary:	A vertex–edge Roman <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>{</mo><mn>2</mn><mo>}</mo></mrow></semantics></math></inline-formula>-dominating function on a graph <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>G</mi><mo>=</mo><mo>(</mo><mi>V</mi><mo>,</mo><mi>E</mi><mo>)</mo></mrow></semantics></math></inline-formula> is a function <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>f</mi><mo>:</mo><mi>V</mi><mo>⟶</mo><mo>{</mo><mn>0</mn><mo>,</mo><mn>1</mn><mo>,</mo><mn>2</mn><mo>}</mo></mrow></semantics></math></inline-formula> satisfying that, for every edge <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>u</mi><mi>v</mi><mo>∈</mo><mi>E</mi></mrow></semantics></math></inline-formula> with <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>f</mi><mo>(</mo><mi>v</mi><mo>)</mo><mo>=</mo><mi>f</mi><mo>(</mo><mi>u</mi><mo>)</mo><mo>=</mo><mn>0</mn></mrow></semantics></math></inline-formula>, <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mo>∑</mo><mrow><mi>w</mi><mo>∈</mo><mi>N</mi><mo>(</mo><mi>v</mi><mo>)</mo><mo>∪</mo><mi>N</mi><mo>(</mo><mi>u</mi><mo>)</mo></mrow></msub><mi>f</mi><mrow><mo>(</mo><mi>w</mi><mo>)</mo></mrow><mo>≥</mo><mn>2</mn></mrow></semantics></math></inline-formula>. The weight of the function <i>f</i> is the sum <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mo>∑</mo><mrow><mi>a</mi><mo>∈</mo><mi>V</mi></mrow></msub><mi>f</mi><mrow><mo>(</mo><mi>a</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula>. The vertex–edge Roman <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>{</mo><mn>2</mn><mo>}</mo></mrow></semantics></math></inline-formula>-domination number of <i>G</i>, denoted by <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>γ</mi><mrow><mi>v</mi><mi>e</mi><mi>R</mi><mn>2</mn></mrow></msub><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula>, is the minimum weight of a vertex–edge Roman <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>{</mo><mn>2</mn><mo>}</mo></mrow></semantics></math></inline-formula>-dominating function on <i>G</i>. In this work, we begin the study of vertex–edge Roman <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>{</mo><mn>2</mn><mo>}</mo></mrow></semantics></math></inline-formula>-domination. We determine the exact vertex–edge Roman <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>{</mo><mn>2</mn><mo>}</mo></mrow></semantics></math></inline-formula>-domination number for cycles and paths, and we provide a tight lower bound and a tight upper bound for the vertex–edge Roman <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>{</mo><mn>2</mn><mo>}</mo></mrow></semantics></math></inline-formula>-domination number of trees. In addition, we prove that the decision problem associated with vertex–edge Roman <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>{</mo><mn>2</mn><mo>}</mo></mrow></semantics></math></inline-formula>-domination is NP-complete for bipartite graphs.
ISSN:	2227-7390