首页   按字顺浏览 期刊浏览 卷期浏览 The ratio of the distance irredundance and domination numbers of a graph
The ratio of the distance irredundance and domination numbers of a graph

 

作者: Johannes H. Hattingh,   Michael A. Henning,  

 

期刊: Journal of Graph Theory  (WILEY Available online 1994)
卷期: Volume 18, issue 1  

页码: 1-9

 

ISSN:0364-9024

 

年代: 1994

 

DOI:10.1002/jgt.3190180102

 

出版商: Wiley Subscription Services, Inc., A Wiley Company

 

数据来源: WILEY

 

摘要:

AbstractLetn≥ 1 be an integer and letGbe a graph. A setDof vertices inGis defined to be ann‐dominating set ofGif every vertex ofGis within distancenfrom some vertex ofD. The minimum cardinality among alln‐dominating sets of G is called the n‐domination numberofGand is denoted by γn(G). A set / of vertices inGisn‐irredundant if for every vertexx∈ / there exists a vertexythat is within distancenfromxbut at distance greater thannfrom every vertex of / ‐ {x}. The n‐irredundance number of G, denoted byirn(G), is the minimum cardinality taken over all maximaln‐irredundant sets of vertices ofG. We show that inf{irn(G)/γn(G) |Gis an arbitrary finite undirected graph with neither loops nor multiple edges} = 1/2 with the infimum not being attained. Subsequently, we show that 2/3 is a lower bound on all quotientsirn(T)/γn(T) in whichTis a tree. Furthermore, we show that, forn≥ 2, this bound is sharp. These results extend those of R. B. Allan and R.C. Laskar [“On Domination and Some Related Concepts in Graph Theory,”Utilitas Mathematica, Vol. 21 (1978), pp. 43–56], B. Bollobás and E. J. Cockayne [“Graph‐Theoretic Parameters Concerning Domination, Independence and Irredundance,”Journal of Graph Theory, Vol. 3 (1979), pp. 241–249], and P. Damaschke [Irredundance Number versus Domination Number,Discrete Math

 

点击下载:  PDF (419KB)



返 回