Induced subgraphs of a tree with constraint degree

Tao Wang and Baoyindureng Wu

Applied Mathematics and Computation, 2023, vol. 440, issue C

Abstract: For an integer k≥2, a vertex partition (V1,…,Vs) of a graph G is called a k-good partition if dG[Vi](v)≡1 (mod k) for each v∈Vi, i∈{1,…,s}. We characterize all trees with a k-good partition. Let f1,k(G)=max{|V(H)|: H is an induced subgraph H of G with dH(v)≡1 (mod k) for every vertex v}. In 1997, Berman et al. (1997) showed that f1,k(T)≥2⌊n+2k−32k−1⌋ for any tree T of order n. By sacrificing the bound slightly, but with a much simpler way, we are able to show that f1,k(T)≥nk, with equality if and only if T is the balanced double star of order 2k. Let f0,k1(T) be the maximum cardinality of a subset S⊆V(T) with dT[S](v)=1 or dT[S](v)≡0 (mod k) for each v∈S. In addition, we give a short proof of the result, due to Huang and Hou [9], that f0,k1(T)≥2n3 for any tree T and integer k≥3.

Keywords: Induced subgraphs; Degrees; Odd subgraphs (search for similar items in EconPapers)
Date: 2023
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300322007287
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:440:y:2023:i:c:s0096300322007287

DOI: 10.1016/j.amc.2022.127657

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().