Mathematics

CLC number: O157.5

A Brief Proof of Spanning Trees with a Bounded Number of Leaves in a Claw-Free Graph

无爪图中具有有限个叶子生成树的一个简单证明

School of Mathematical Sciences, Tianjin Normal University, Tianjin 300387, China

^† Corresponding author. E-mail: This email address is being protected from spambots. You need JavaScript enabled to view it.

Received: 30 September 2023

Abstract

For a graph $G$ and an positive integer $k$, let ${\sigma }_k\left(G\right)$ denote the minimum degree sum of $k$ independent vertices of $G$. It has beenproved that if a connected claw-free graph $G$ satisfies ${\sigma }_{k+\mathrm{1}}\left(G\right)\ge \left|G\right|-k$, then $G$ has a spanning $k$-ended tree. We also know that the lower bound $\left|G\right|-k$ is sharp. In this paper, we give a simple proof of this theorem by using another $t$-ended system.

摘要

对于图$G$和正整数$k$，我们用${\sigma }_k\left(G\right)$表示$G$中$k$个独立顶点的最小度和。Kano等人证明了如果一个连通的无爪图$G$满足${\sigma }_{k+\mathrm{1}}\left(G\right)\ge \left|G\right|-k$，那么图$G$有一个生成$k$-端树，同时证明了这个下界是紧的。在本文中，我们使用另一个$t$-端系统给出了该定理的一个简单证明。