| Summary: | This paper is devoted to the study of the quasi-total strong differential of a graph, and it is a contribution to the Special Issue “<i>Theoretical computer science and discrete mathematics</i>” of <i>Symmetry</i>. Given a vertex <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>x</mi><mo>∈</mo><mi>V</mi><mo>(</mo><mi>G</mi><mo>)</mo></mrow></semantics></math></inline-formula> of a graph <i>G</i>, the neighbourhood of <i>x</i> is denoted by <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>N</mi><mo>(</mo><mi>x</mi><mo>)</mo></mrow></semantics></math></inline-formula>. The neighbourhood of a set <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>X</mi><mo>⊆</mo><mi>V</mi><mo>(</mo><mi>G</mi><mo>)</mo></mrow></semantics></math></inline-formula> is defined to be <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>N</mi><mrow><mo>(</mo><mi>X</mi><mo>)</mo></mrow><mo>=</mo><msub><mo>⋃</mo><mrow><mi>x</mi><mo>∈</mo><mi>X</mi></mrow></msub><mi>N</mi><mrow><mo>(</mo><mi>x</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula>, while the external neighbourhood of <i>X</i> is defined to be <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>N</mi><mi>e</mi></msub><mrow><mo>(</mo><mi>X</mi><mo>)</mo></mrow><mo>=</mo><mi>N</mi><mrow><mo>(</mo><mi>X</mi><mo>)</mo></mrow><mo>∖</mo><mi>X</mi></mrow></semantics></math></inline-formula>. Now, for every set <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>X</mi><mo>⊆</mo><mi>V</mi><mo>(</mo><mi>G</mi><mo>)</mo></mrow></semantics></math></inline-formula> and every vertex <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>x</mi><mo>∈</mo><mi>X</mi></mrow></semantics></math></inline-formula>, the external private neighbourhood of <i>x</i> with respect to <i>X</i> is defined as the set <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>P</mi><mi>e</mi></msub><mrow><mo>(</mo><mi>x</mi><mo>,</mo><mi>X</mi><mo>)</mo></mrow><mo>=</mo><mrow><mo>{</mo><mi>y</mi><mo>∈</mo><mi>V</mi><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow><mo>∖</mo><mi>X</mi><mo>:</mo><mspace width="0.166667em"></mspace><mi>N</mi><mrow><mo>(</mo><mi>y</mi><mo>)</mo></mrow><mo>∩</mo><mi>X</mi><mo>=</mo><mrow><mo>{</mo><mi>x</mi><mo>}</mo></mrow><mo>}</mo></mrow><mo>.</mo></mrow></semantics></math></inline-formula> Let <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>X</mi><mi>w</mi></msub><mo>=</mo><mrow><mo>{</mo><mi>x</mi><mo>∈</mo><mi>X</mi><mo>:</mo><mspace width="0.166667em"></mspace><msub><mi>P</mi><mi>e</mi></msub><mrow><mo>(</mo><mi>x</mi><mo>,</mo><mi>X</mi><mo>)</mo></mrow><mo>≠</mo><mo>⌀</mo><mo>}</mo></mrow></mrow></semantics></math></inline-formula>. The strong differential of <i>X</i> is defined to be <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mo>∂</mo><mi>s</mi></msub><mrow><mrow><mo>(</mo><mi>X</mi><mo>)</mo></mrow><mo>=</mo><mo>|</mo></mrow><msub><mi>N</mi><mi>e</mi></msub><mrow><mrow><mo>(</mo><mi>X</mi><mo>)</mo></mrow><mo>|</mo><mo>−</mo><mo>|</mo></mrow><msub><mi>X</mi><mi>w</mi></msub><mrow><mo>|</mo></mrow></mrow></semantics></math></inline-formula>, while the quasi-total strong differential of <i>G</i> is defined to be <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mo>∂</mo><msup><mi>s</mi><mo>*</mo></msup></msub><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow><mo>=</mo><mo movablelimits="true" form="prefix">max</mo><mrow><mo>{</mo><msub><mo>∂</mo><mi>s</mi></msub><mrow><mo>(</mo><mi>X</mi><mo>)</mo></mrow><mo>:</mo><mi>X</mi><mo>⊆</mo><mi>V</mi><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow><mspace width="4.pt"></mspace><mi>and</mi><mspace width="4.pt"></mspace><msub><mi>X</mi><mi>w</mi></msub><mo>⊆</mo><mi>N</mi><mrow><mo>(</mo><mi>X</mi><mo>)</mo></mrow><mo>}</mo></mrow><mo>.</mo></mrow></semantics></math></inline-formula> We show that the quasi-total strong differential is closely related to several graph parameters, including the domination number, the total domination number, the 2-domination number, the vertex cover number, the semitotal domination number, the strong differential, and the quasi-total Italian domination number. As a consequence of the study, we show that the problem of finding the quasi-total strong differential of a graph is NP-hard.
|
|---|