<p>For a graph <i>G</i>, let <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\gamma (G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>γ</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> and <i>core</i>(<i>G</i>) denote the cardinality of a minimum dominating set of <i>G</i>,&#xa0; and the intersection of all the minimum dominating sets of <i>G</i>,&#xa0; respectively. In this paper, we prove that if <i>G</i> is a <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(2K_2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>2</mn> <msub> <mi>K</mi> <mn>2</mn> </msub> </mrow> </math></EquationSource> </InlineEquation>-free graph with <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(\gamma (G)\ge 3\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>γ</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>≥</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation> and without isolated vertices, then <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(v\in core(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>v</mi> <mo>∈</mo> <mi>c</mi> <mi>o</mi> <mi>r</mi> <mi>e</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> if and only if <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(\gamma (G-v)&gt; \gamma (G);\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>γ</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo>-</mo> <mi>v</mi> <mo stretchy="false">)</mo> <mo>&gt;</mo> <mi>γ</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>;</mo> </mrow> </math></EquationSource> </InlineEquation> moreover, we give an example to answer an open question proposed by Samodivkin whether there is a connected graph <i>G</i> such that <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(core(G)\ne \emptyset \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>c</mi> <mi>o</mi> <mi>r</mi> <mi>e</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>≠</mo> <mi mathvariant="normal">∅</mi> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(\gamma (G-v)=\gamma (G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>γ</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo>-</mo> <mi>v</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mi>γ</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> for each vertex <i>v</i> of <i>G</i>. We also prove that for every <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(\{claw,Z_2\}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">{</mo> <mi>c</mi> <mi>l</mi> <mi>a</mi> <mi>w</mi> <mo>,</mo> <msub> <mi>Z</mi> <mn>2</mn> </msub> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation>-free graph <i>G</i> without isolated vertices, <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(v\in core(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>v</mi> <mo>∈</mo> <mi>c</mi> <mi>o</mi> <mi>r</mi> <mi>e</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> if and only if <InlineEquation ID="IEq10"> <EquationSource Format="TEX">\(\gamma (G-v)&gt; \gamma (G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>γ</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo>-</mo> <mi>v</mi> <mo stretchy="false">)</mo> <mo>&gt;</mo> <mi>γ</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>.</p>

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

The Core of Minimum Dominating Sets in Two Classes of Graphs

  • Xiaodong Chen,
  • Wenyue Zhang,
  • Shou-Jun Xu

摘要

For a graph G, let \(\gamma (G)\) γ ( G ) and core(G) denote the cardinality of a minimum dominating set of G,  and the intersection of all the minimum dominating sets of G,  respectively. In this paper, we prove that if G is a \(2K_2\) 2 K 2 -free graph with \(\gamma (G)\ge 3\) γ ( G ) 3 and without isolated vertices, then \(v\in core(G)\) v c o r e ( G ) if and only if \(\gamma (G-v)> \gamma (G);\) γ ( G - v ) > γ ( G ) ; moreover, we give an example to answer an open question proposed by Samodivkin whether there is a connected graph G such that \(core(G)\ne \emptyset \) c o r e ( G ) and \(\gamma (G-v)=\gamma (G)\) γ ( G - v ) = γ ( G ) for each vertex v of G. We also prove that for every \(\{claw,Z_2\}\) { c l a w , Z 2 } -free graph G without isolated vertices, \(v\in core(G)\) v c o r e ( G ) if and only if \(\gamma (G-v)> \gamma (G)\) γ ( G - v ) > γ ( G ) .