期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

The Product of the Restrained Domination Numbers of a Graph and Its Complement

The Product of the Restrained Domination Numbers of a Graph and Its Complement
原文传递
导出
摘要 Let G=（V,E） be a graph.A set S■V is a restrained dominating set if every vertex in V-S is adjacent to a vertex in S and to a vertex in V-S.The restrained domination number of G,denoted γr（G）,is the smallest cardinality of a restrained dominating set of G.In this paper,we show that if G is a graph of order n≥4,then γr（G）γr（G）≤2n.We also characterize the graphs achieving the upper bound. Let G=（V,E） be a graph.A set S■V is a restrained dominating set if every vertex in V-S is adjacent to a vertex in S and to a vertex in V-S.The restrained domination number of G,denoted γr（G）,is the smallest cardinality of a restrained dominating set of G.In this paper,we show that if G is a graph of order n≥4,then γr（G）γr（G）≤2n.We also characterize the graphs achieving the upper bound.
作者 Johannes H.HATTINGH Ernst J.JOUBERT
机构地区 Department of Mathematics Department of Mathematics
出处 《Acta Mathematica Sinica,English Series》 SCIE CSCD 2014年第3期445-452,共8页 数学学报（英文版）
关键词 GRAPH DOMINATION restrained domination Nordhaus-Gaddum upper bound Graph, domination, restrained domination, Nordhaus-Gaddum, upper bound
分类号 O157.5 [理学—基础数学] TP311.13 [自动化与计算机技术—计算机软件与理论]
  • 相关文献

参考文献13

  • 1Dankelmann, P., Day, D., Hattingh, J. H., et al.: On equality in an upper bound for the restrained and total domination numbers of a graph. Discrete Math., 307, 2845-2852 (2007).
  • 2Domke, G. S., Hattingh, J. H., Hedetniemi, S. T., et al.: Restrained domination in graphs. Discrete Math., 203, 61-69 (1999).
  • 3Domke, G. S., Hattingh, J. H., Hedetniemi, S. T., et al.: Restrained domination in trees. Discrete Math., 211, 1-9 (2000).
  • 4Domke, G. S., Hattingh, J. H., Henning, M. A., et al.: Restrained domination in graphs with minimum degree two. J. Combin. Math. Combin. Cornput., 35, 239-254 (2000).
  • 5Hattingh, J. H., Jonck, E., Joubert, E. J., et al.: Nordhaus-Gaddum results for restrained domination and total restrained domination in graphs. Discrete Math., 308, 1080-1087 (2008).
  • 6Hattingh, J. H., Joubert, E. J.: An upper bound for the restrained domination number of a graph with minimum degree at least two in terms of order and minimum degree. Discrete Applied Math., 157, 2846- 2858 (2009).
  • 7Haynes, T. W., Hedetniemi, S. T., Slater, P. J.: Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1997.
  • 8Haynes, T. W., Hedetniemi, S. T., Slater, P. J. (eds): Domination in Graphs: Advanced Topics, Marcel Dekker, New York, 1997.
  • 9Jaeger, F., Payan, C.: Relations du type Nordhaus-Gaddum pour le nombre d'absorption d'un simple. C. R. Acad. Sci. Set. A, 274, 728-730 (1972).
  • 10Karami, H., Khodkar, A., Sheikholeslami, S. M., et al.: Inequalities of Nordhaus-Gaddum type for con- nected domination. Graphs Combin., 28, 123-131 (2012).
Acta Mathematica Sinica,English Series
2014年 第3期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部