Article ID Journal Published Year Pages File Type
4647098 Discrete Mathematics 2014 5 Pages PDF
Abstract

Let k≥2k≥2, l≥2l≥2 and m≥0m≥0 be integers, and let GG be a connected graph. If there exists a subgraph XX of GG such that for every vertex vv of GG, the distance between vv and XX is at most mm, then we say that Xm-dominates GG. Define αl(G)=max{|S|:S⊆V(G),dG(x,y)≥lαl(G)=max{|S|:S⊆V(G),dG(x,y)≥l for all distinct x,y∈S}x,y∈S}, where dG(x,y)dG(x,y) denotes the distance between xx and yy in GG. We prove the following theorem and show that the condition is sharp. If α2(m+1)(G)≤kα2(m+1)(G)≤k, then GG has a tree that has at most kk leaves and mm-dominates GG. This is a generalization of some related results.

Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,