Scholarlink

Abstract <p> A nonpendant vertex of a graph is called a <i>supportvertex</i> if it is adjacent to any leaf. This paper examines how two classes of extremaltrees among all trees with a prescribed degree sequence can relate to each other: the class of treesminimizing the number of support vertices and the class of trees minimizing the dominationnumber. Two specially defined values play important role here: the Slater number, proposed bySlater as a lower bound on domination number, and the lower bound on the number of thesupport vertices of a tree proposed by Kurnosov. In the paper, the problem of comparing theclasses is completely solved in the case where the maximum of two values is the latter.</p>

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

On Relation between two Classes of Extremal Trees with Prescribed Degree Sequence

  • 期刊论文

  • 发表日期：

    2025年6月1日

查看全文
  • S. A. Krupoderova,
  • A. D. Kurnosov

摘要

Abstract

A nonpendant vertex of a graph is called a supportvertex if it is adjacent to any leaf. This paper examines how two classes of extremaltrees among all trees with a prescribed degree sequence can relate to each other: the class of treesminimizing the number of support vertices and the class of trees minimizing the dominationnumber. Two specially defined values play important role here: the Slater number, proposed bySlater as a lower bound on domination number, and the lower bound on the number of thesupport vertices of a tree proposed by Kurnosov. In the paper, the problem of comparing theclasses is completely solved in the case where the maximum of two values is the latter.