Scholarlink

<p>An (unrooted) <i>d</i>-<i>ary tree</i> is a tree in which every internal vertex has degree <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="13370_2025_1360_Article_IEq1.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="38" /> </InlineMediaObject> <EquationSource Format="TEX">\(d+1\)</EquationSource> </InlineEquation>. In this paper, we show for every fixed <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="13370_2025_1360_Article_IEq2.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="41" /> </InlineMediaObject> <EquationSource Format="TEX">\(d\ge 2\)</EquationSource> </InlineEquation> that <i>d</i>-ary caterpillars have the minimum number of dominating sets among <i>d</i>-ary trees of a given order. We also determine the maximum number of dominating sets in binary trees (the special case <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="13370_2025_1360_Article_IEq3.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="40" /> </InlineMediaObject> <EquationSource Format="TEX">\(d=2\)</EquationSource> </InlineEquation>) and classify the extremal trees, which are also unique.</p>

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

The number of dominating sets in d-ary trees

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年8月20日

查看全文
  • Opeyemi Oyewumi,
  • Adriana Roux,
  • Stephan Wagner

摘要

An (unrooted) d-ary tree is a tree in which every internal vertex has degree \(d+1\) . In this paper, we show for every fixed \(d\ge 2\) that d-ary caterpillars have the minimum number of dominating sets among d-ary trees of a given order. We also determine the maximum number of dominating sets in binary trees (the special case \(d=2\) ) and classify the extremal trees, which are also unique.