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)
返 回