<p>Let <i>G</i> be a connected graph of order at least three. A set <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(D\subseteq V(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>D</mi> <mo>⊆</mo> <mi>V</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> is called a total outer-independent dominating set of <i>G</i> if every vertex of <i>G</i> is adjacent to at least one vertex in <i>D</i>, and <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(V(G){\setminus } D\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>V</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo lspace="0.15em" rspace="0.15em" stretchy="false">\</mo> <mi>D</mi> </mrow> </math></EquationSource> </InlineEquation> is an independent set of <i>G</i>. The total outer-independent domination number of <i>G</i>, denoted by <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(\gamma _t^{oi}(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mi>γ</mi> <mi>t</mi> <mrow> <mi mathvariant="italic">oi</mi> </mrow> </msubsup> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, is the minimum cardinality among all total outer-independent dominating sets of <i>G</i>. In this article, we study the total outer-independent domination number of subdivision graphs <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(\texttt{S}(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="monospace">S</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> of connected graphs <i>G</i>. We establish several combinatorial results concerning this parameter in the context of this well-known graph operator, expressed in terms of some invariants of <i>G</i>, which improves for the case of trees. Finally, we derive closed formulas on <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(\gamma _t^{oi}(\texttt{S}(G))\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mi>γ</mi> <mi>t</mi> <mrow> <mi mathvariant="italic">oi</mi> </mrow> </msubsup> <mrow> <mo stretchy="false">(</mo> <mi mathvariant="monospace">S</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> for some well-known families of graphs <i>G</i>.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On the total outer-independent domination number of subdivision graphs

  • Abel Cabrera-Martínez,
  • Ismael Rios-Villamar,
  • Omar Rosario Cayetano,
  • José M. Sigarreta

摘要

Let G be a connected graph of order at least three. A set \(D\subseteq V(G)\) D V ( G ) is called a total outer-independent dominating set of G if every vertex of G is adjacent to at least one vertex in D, and \(V(G){\setminus } D\) V ( G ) \ D is an independent set of G. The total outer-independent domination number of G, denoted by \(\gamma _t^{oi}(G)\) γ t oi ( G ) , is the minimum cardinality among all total outer-independent dominating sets of G. In this article, we study the total outer-independent domination number of subdivision graphs \(\texttt{S}(G)\) S ( G ) of connected graphs G. We establish several combinatorial results concerning this parameter in the context of this well-known graph operator, expressed in terms of some invariants of G, which improves for the case of trees. Finally, we derive closed formulas on \(\gamma _t^{oi}(\texttt{S}(G))\) γ t oi ( S ( G ) ) for some well-known families of graphs G.