Journal of University of Science and Technology of China ›› 2019, Vol. 49 ›› Issue (8): 603-605.DOI: 10.3969/j.issn.0253-2778.2019.08.001

    Next Articles

Large induced subgraph with restricted degrees in trees

  

  1. HUANG Ziyang, HOU Xinmin
  • Received:2018-07-15 Revised:2018-10-10 Online:2019-08-31 Published:2019-08-31
  • Contact: HOU Xinmin
  • About author:HUANG Ziyang, male, born in 1993, master. Research field: Combinatorics and graph theory. E-mail: zyh16@mail.ustc.edu.cn

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