Algorithmic Complexity and Bounds for Domination Subdivision Numbers of Graphs

Let <a:math xmlns:a="http://www.w3.org/1998/Math/MathML" id="M1"><a:mi>G</a:mi><a:mo>=</a:mo><a:mfenced open="(" close=")" separators="|"><a:mrow><a:mi>V</a:mi><a:mo>,</a:mo><a:mi>E</a:mi></a:mrow></a:mfenced></a:math> be a simple graph. A subset <f:math xmlns:f="http://www.w3.org/1998/Math/MathML" id="M2"><f:mi>D</f:mi><f:mo>⊆</f:mo><f:mi>V</f:mi></f:math> is a dominating set if every vertex not in <h:math xmlns:h="http://www.w3.org/1998/Math/MathML" id="M3"><h:mi>D</h:mi></h:math> is adjacent to a vertex in <j:math xmlns:j="http://www.w3.org/1998/Math/MathML" id="M4"><j:mi>D</j:mi></j:math> . The domination number of <l:math xmlns:l="http://www.w3.org/1998/Math/MathML" id="M5"><l:mi>G</l:mi></l:math> , denoted by <n:math xmlns:n="http://www.w3.org/1998/Math/MathML" id="M6"><n:mi>γ</n:mi><n:mfenced open="(" close=")" separators="|"><n:mrow><n:mi>G</n:mi></n:mrow></n:mfenced></n:math> , is the smallest cardinality of a dominating set of <s:math xmlns:s="http://www.w3.org/1998/Math/MathML" id="M7"><s:mi>G</s:mi></s:math> . The domination subdivision number <u:math xmlns:u="http://www.w3.org/1998/Math/MathML" id="M8"><u:msub><u:mrow><u:mtext>sd</u:mtext></u:mrow><u:mrow><u:mi>γ</u:mi></u:mrow></u:msub><u:mfenced open="(" close=")" separators="|"><u:mrow><u:mi>G</u:mi></u:mrow></u:mfenced></u:math> of <z:math xmlns:z="http://www.w3.org/1998/Math/MathML" id="M9"><z:mi>G</z:mi></z:math> is the minimum number of edges that must be subdivided (each edge can be subdivided at most once) in order to increase the domination number. In 2000, Haynes et al. showed that <bb:math xmlns:bb="http://www.w3.org/1998/Math/MathML" id="M10"><bb:msub><bb:mrow><bb:mtext>sd</bb:mtext></bb:mrow><bb:mrow><bb:mi>γ</bb:mi></bb:mrow></bb:msub><bb:mfenced open="(" close=")" separators="|"><bb:mrow><bb:mi>G</bb:mi></bb:mrow></bb:mfenced><bb:mo>≤</bb:mo><bb:msub><bb:mrow><bb:mi>d</bb:mi></bb:mrow><bb:mrow><bb:mi>G</bb:mi></bb:mrow></bb:msub><bb:mfenced open="(" close=")" separators="|"><bb:mrow><bb:mi>v</bb:mi></bb:mrow></bb:mfenced><bb:mo>+</bb:mo><bb:msub><bb:mrow><bb:mi>d</bb:mi></bb:mrow><bb:mrow><bb:mi>G</bb:mi></bb:mrow></bb:msub><bb:mfenced open="(" close=")" separators="|"><bb:mrow><bb:mi>v</bb:mi></bb:mrow></bb:mfenced><bb:mo>−</bb:mo><bb:mn>1</bb:mn></bb:math> for any edge <mb:math xmlns:mb="http://www.w3.org/1998/Math/MathML" id="M11"><mb:mi>u</mb:mi><mb:mi>v</mb:mi><mb:mo>∈</mb:mo><mb:mi>E</mb:mi><mb:mfenced open="(" close=")" separators="|"><mb:mrow><mb:mi>G</mb:mi></mb:mrow></mb:mfenced></mb:math> with <rb:math xmlns:rb="http://www.w3.org/1998/Math/MathML" id="M12"><rb:msub><rb:mrow><rb:mi>d</rb:mi></rb:mrow><rb:mrow><rb:mi>G</rb:mi></rb:mrow></rb:msub><rb:mfenced open="(" close=")" separators="|"><rb:mrow><rb:mi>u</rb:mi></rb:mrow></rb:mfenced><rb:mo>≥</rb:mo><rb:mn>2</rb:mn></rb:math> and <wb:math xmlns:wb="http://www.w3.org/1998/Math/MathML" id="M13"><wb:msub><wb:mrow><wb:mi>d</wb:mi></wb:mrow><wb:mrow><wb:mi>G</wb:mi></wb:mrow></wb:msub><wb:mfenced open="(" close=")" separators="|"><wb:mrow><wb:mi>v</wb:mi></wb:mrow></wb:mfenced><wb:mo>≥</wb:mo><wb:mn>2</wb:mn></wb:math> where <bc:math xmlns:bc="http://www.w3.org/1998/Math/MathML" id="M14"><bc:mi>G</bc:mi></bc:math> is a connected graph with order no less than 3. In this paper, we improve the above bound to <dc:math xmlns:dc="http://www.w3.org/1998/Math/MathML" id="M15"><dc:msub><dc:mrow><dc:mtext>sd</dc:mtext></dc:mrow><dc:mrow><dc:mi>γ</dc:mi></dc:mrow></dc:msub><dc:mfenced open="(" close=")" separators="|"><dc:mrow><dc:mi>G</dc:mi></dc:mrow></dc:mfenced><dc:mo>≤</dc:mo><dc:msub><dc:mrow><dc:mi>d</dc:mi></dc:mrow><dc:mrow><dc:mi>G</dc:mi></dc:mrow></dc:msub><dc:mfenced open="(" close=")" separators="|"><dc:mrow><dc:mi>u</dc:mi></dc:mrow></dc:mfenced><dc:mo>+</dc:mo><dc:msub><dc:mrow><dc:mi>d</dc:mi></dc:mrow><dc:mrow><dc:mi>G</dc:mi></dc:mrow></dc:msub><dc:mfenced open="(" close=")" separators="|"><dc:mrow><dc:mi>v</dc:mi></dc:mrow></dc:mfenced><dc:mo>−</dc:mo><dc:mrow><dc:mfenced open="|" close="|" separators="|"><dc:mrow><dc:msub><dc:mrow><dc:mi>N</dc:mi></dc:mrow><dc:mrow><dc:mi>G</dc:mi></dc:mrow></dc:msub><dc:mrow><dc:mfenced open="(" close=")" separators="|"><dc:mrow><dc:mi>u</dc:mi></dc:mrow></dc:mfenced></dc:mrow><dc:mo>∩</dc:mo><dc:msub><dc:mrow><dc:mi>N</dc:mi></dc:mrow><dc:mrow><dc:mi>G</dc:mi></dc:mrow></dc:msub><dc:mrow><dc:mfenced open="(" close=")" separators="|"><dc:mrow><dc:mi>v</dc:mi></dc:mrow></dc:mfenced></dc:mrow></dc:mrow></dc:mfenced></dc:mrow><dc:mo>−</dc:mo><dc:mn>1</dc:mn></dc:math> , and furthermore, we show the decision problem for determining whether <xc:math xmlns:xc="http://www.w3.org/1998/Math/MathML" id="M16"><xc:msub><xc:mrow><xc:mtext>sd</xc:mtext></xc:mrow><xc:mrow><xc:mi>γ</xc:mi></xc:mrow></xc:msub><xc:mfenced open="(" close=")" separators="|"><xc:mrow><xc:mi>G</xc:mi></xc:mrow></xc:mfenced><xc:mo>=</xc:mo><xc:mn>1</xc:mn></xc:math> is NP-hard. Moreover, we show some bounds or exact values for domination subdivision numbers of some graphs.