首页   按字顺浏览 期刊浏览 卷期浏览 UPPER BOUNDS ON THE LOWER OPEN PACKING NUMBER OF A TREE
UPPER BOUNDS ON THE LOWER OPEN PACKING NUMBER OF A TREE

 

作者: MichaelA. Henning,  

 

期刊: Quaestiones Mathematicae  (Taylor Available online 1998)
卷期: Volume 21, issue 3-4  

页码: 235-245

 

ISSN:1607-3606

 

年代: 1998

 

DOI:10.1080/16073606.1998.9632043

 

出版商: Taylor & Francis Group

 

关键词: 05C70

 

数据来源: Taylor

 

摘要:

LetGbe a graph and letvbe a vertex ofG. The open neigbourhoodN(v)ofvis the set of all vertices adjacent withvinG. An open packing ofGis a set of vertices whose open neighbourhoods are pairwise disjoint. The lower open packing number ofG, denotedρ°L(G), is the minimum cardinality of a maximal open packing ofGwhile the (upper) open packing number ofG, denotedρ°(G), is the maximum cardinality among all open packings ofG. It is known (see [7]) that ifGis a connected graph of order n ≥3, thenρ°(G)≤ 2n/3 and this bound is sharp (even for trees). As a consequence of this result, we know thatρ°L(G)≤ 2n/3. In this paper, we improve this bound whenGis a tree. We show that ifGis a tree of ordernwith radius 3, thenρ°L(G)≤n/2 + 2 √n-1, and this bound is sharp, while ifGis a tree of ordernwith radius at least 4, thenρ°L(G)is bounded above by 2n/3—O√n).

 

点击下载:  PDF (523KB)



返 回