关键词: 树, 导出子图, 度

Abstract: A problem was proposed to determine for a tree T the size of the largest SV(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.

Key words: tree, induced subgraph, degree