Scholarlink

<p>We consider the augmentation problem of how domination parameters behave when a perfect matching <i>P</i> of the complement is added to the graph. We focus on the case that the graph is a tree, and inter alia show that if <i>T</i> is a tree of even order <i>n</i> that is not a star, then <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10_2025_1196_Article_IEq1.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="48" /> </InlineMediaObject> <EquationSource Format="TEX">\(T+P\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>T</mi> <mo>+</mo> <mi>P</mi> </mrow> </math></EquationSource> </InlineEquation> has domination number at most 2<i>n</i>/5, independent domination number at most <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10_2025_1196_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="57" /> </InlineMediaObject> <EquationSource Format="TEX">\(n/2-1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo stretchy="false">/</mo> <mn>2</mn> <mo>-</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>, and total domination and upper domination number at most <i>n</i>/2. Further, there exists a choice of <i>P</i> such that <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10_2025_1196_Article_IEq1.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="48" /> </InlineMediaObject> <EquationSource Format="TEX">\(T+P\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>T</mi> <mo>+</mo> <mi>P</mi> </mrow> </math></EquationSource> </InlineEquation> has total domination number at most <i>n</i>/3. All these bounds are sharp.</p>

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

Domination parameters and added matchings

  • 期刊论文

  • 发表日期：

    2025年7月23日

查看全文
  • Wayne Goddard,
  • Michael A. Henning

摘要

We consider the augmentation problem of how domination parameters behave when a perfect matching P of the complement is added to the graph. We focus on the case that the graph is a tree, and inter alia show that if T is a tree of even order n that is not a star, then \(T+P\) T + P has domination number at most 2n/5, independent domination number at most \(n/2-1\) n / 2 - 1 , and total domination and upper domination number at most n/2. Further, there exists a choice of P such that \(T+P\) T + P has total domination number at most n/3. All these bounds are sharp.