Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4647098 | Discrete Mathematics | 2014 | 5 Pages |
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
Mikio Kano, Masao Tsugaki, Guiying Yan,