Let <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$w_k(T)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>w</mi> <mi>k</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> be the number of walks of length k in a tree T. Täubig, Weihmann, Kosub, Hemmecke, and Mayr in 2013 proposed the following conjecture (the TWKHM conjecture) that if T is a tree, then for <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$k\ge 1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>≥</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>, <Equation ID="Equ8"> <EquationSource Format="TEX">$\begin{aligned} w_0(T)w_{k+1}(T)-w _1(T)w_{k}(T)\ge 0. \end{aligned}$</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mrow> <mtable> <mtr> <mtd columnalign="right"> <mrow> <msub> <mi>w</mi> <mn>0</mn> </msub> <mrow> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mrow> <msub> <mi>w</mi> <mrow> <mi>k</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> <mrow> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mrow> <mo>-</mo> <msub> <mi>w</mi> <mn>1</mn> </msub> <mrow> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mrow> <msub> <mi>w</mi> <mi>k</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mrow> <mo>≥</mo> <mn>0</mn> <mo>.</mo> </mrow> </mtd> </mtr> </mtable> </mrow> </math></EquationSource> </Equation>In this paper, using the recurrence relations among the number of walks starting at different vertices, and analyzing the structure of a tree, we prove that the TWKHM conjecture holds if T satisfies one of the following conditions: <OrderedList> <ListItem> <ItemNumber>(i)</ItemNumber> <ItemContent> The diameter of T is at most 4; </ItemContent> </ListItem> <ListItem> <ItemNumber>(ii)</ItemNumber> <ItemContent> Each 2-degree vertex of T is adjacent to a pendent vertex; </ItemContent> </ListItem> <ListItem> <ItemNumber>(iii)</ItemNumber> <ItemContent> T is a spider without odd-length twigs; </ItemContent> </ListItem> <ListItem> <ItemNumber>(iv)</ItemNumber> <ItemContent> T is a spider with more than one 1-twigs and more than two long twigs; </ItemContent> </ListItem> <ListItem> <ItemNumber>(v)</ItemNumber> <ItemContent> T is a quasi-spider, i.e., it “looks like” a spider and does not have any twig of size greater than half of the tree. </ItemContent> </ListItem> </OrderedList>

The TWKHM conjecture on the number of walks in trees

期刊论文
发表日期：

2026年2月20日

查看全文

Dongxiu Cai,
Jiasheng Zeng,
Xiao-Dong Zhang

摘要

Let $w_k(T)$ $w_{k} (T)$ be the number of walks of length k in a tree T. Täubig, Weihmann, Kosub, Hemmecke, and Mayr in 2013 proposed the following conjecture (the TWKHM conjecture) that if T is a tree, then for $k\ge 1$ $k \geq 1$ , $\begin{aligned} w_0(T)w_{k+1}(T)-w _1(T)w_{k}(T)\ge 0. \end{aligned}$ $\begin{matrix} w_{0} (T) w_{k + 1} (T) - w_{1} (T) w_{k} (T) \geq 0 . \end{matrix}$ In this paper, using the recurrence relations among the number of walks starting at different vertices, and analyzing the structure of a tree, we prove that the TWKHM conjecture holds if T satisfies one of the following conditions: (i)

The diameter of T is at most 4;

(ii)

Each 2-degree vertex of T is adjacent to a pendent vertex;

(iii)

T is a spider without odd-length twigs;

(iv)

T is a spider with more than one 1-twigs and more than two long twigs;

(v)

T is a quasi-spider, i.e., it “looks like” a spider and does not have any twig of size greater than half of the tree.