论文部分内容阅读
研究图在点度数限制下的导出子图的大小是一个非常有趣的图论问题。Berman等人在树上得到了一系列优美的结果,并进一步提出了如下问题:对于树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。这个界是紧的。从而解决了Berman提出的问题。