树图中度数受限的大导出子图

Large induced subgraph with restricted degrees in trees

有文献提出公开问题:对树T,求最大的集合S∈V(T)使得导出子图T[S]每个点的度为1或0(mod k).证明了,对给定的整数k≥2,每一棵树T都包含一个阶数至少为ck|V(T)|的导出子图使得所有的度为1或0(mod k),这里当k=2时,ck=3/4;当k≥3时ck=2/3,且下界是最好的.这个结果解决了上述问题.

A problem was proposed to determine for a tree T the size of the largest S V(T)such that all vertices in T[S]have either degree 1 or degree 0(mod k).Here it was proved that,for integer k≥2,every tree T contains an induced subgraph of order at least ck|V(T)|with all degrees either equal to 1 or 0(mod k),where ck=3/4 when k=2,and ck=2/3 when k≥3.Moreover,the bounds are best possible.This gives a good answer to the problem.