<p>Let <i>G</i>(<i>V</i>(<i>G</i>),&#xa0;<i>E</i>(<i>G</i>)) be a nontrivial connected graph and let <InlineEquation ID="IEq1"> <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>. The set <i>D</i> is a dominating set of <i>G</i> if every vertex in <InlineEquation ID="IEq2"> <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> has at least one neighbor in <i>D</i>. Further, if every vertex in <i>D</i> has either zero or at least two neighbors in <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>, then <i>D</i> is a certified dominating set of <i>G</i>. The (certified) domination number of <i>G</i> is the minimum cardinality among all (certified) dominating sets of <i>G</i>. In this article, a constructive characterization of trees with equal domination and certified domination numbers is presented.</p>

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

Trees with equal domination and certified domination numbers

  • Abel Cabrera-Martínez

摘要

Let G(V(G), E(G)) be a nontrivial connected graph and let \(D\subseteq V(G)\) D V ( G ) . The set D is a dominating set of G if every vertex in \(V(G)\setminus D\) V ( G ) \ D has at least one neighbor in D. Further, if every vertex in D has either zero or at least two neighbors in \(V(G)\setminus D\) V ( G ) \ D , then D is a certified dominating set of G. The (certified) domination number of G is the minimum cardinality among all (certified) dominating sets of G. In this article, a constructive characterization of trees with equal domination and certified domination numbers is presented.