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

Large induced subgraph with restricted degrees in trees

作　　者：黄子扬 侯新民[1] HUANG Ziyang;HOU Xinmin(Wu Wen-Tsun Key Laboratory of Mathematics, School of Mathematical Sciences, University of Science and Technology of China, Hefei 230026, China)

机构地区：[1]中科院吴文俊数学重点实验室,中国科学技术大学数学科学学院,安徽合肥230026

出　　处：《中国科学技术大学学报》2019年第8期603-605,共3页JUSTC

基　　金：NNSF of China(11671376);NNSF of Anhui Province(1708085MA18);Anhui Initiative in Quantum Information Technologies(AHY150200)。

摘　　要：有文献提出公开问题:对树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.

关 键 词：树 导出子图 度 

分 类 号：O157.5[理学—数学]