Graphs with Large Italian Domination Number

被引:0
作者
Teresa W. Haynes
Michael A. Henning
Lutz Volkmann
机构
[1] East Tennessee State University,Department of Mathematics and Statistics
[2] University of Johannesburg,Department of Mathematics and Applied Mathematics
[3] RWTH Aachen University,Lehrstuhl II für Mathematik
来源
Bulletin of the Malaysian Mathematical Sciences Society | 2020年 / 43卷
关键词
Domination; Italian domination; Roman domination; Roman ; -domination; 05C69;
D O I
暂无
中图分类号
学科分类号
摘要
An Italian dominating function on a graph G with vertex set V(G) is a function f:V(G)→{0,1,2}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f :V(G) \rightarrow \{0,1,2\}$$\end{document} having the property that for every vertex v with f(v)=0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f(v) = 0$$\end{document}, at least two neighbors of v are assigned 1 under f or at least one neighbor of v is assigned 2 under f. The weight of an Italian dominating function f is the sum of the values assigned to all the vertices under f. The Italian domination number of G, denoted by γI(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\gamma _{I}(G)$$\end{document}, is the minimum weight of an Italian dominating of G. It is known that if G is a connected graph of order n≥3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n \ge 3$$\end{document}, then γI(G)≤34n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\gamma _{I}(G) \le \frac{3}{4}n$$\end{document}. Further, if G has minimum degree at least 2, then γI(G)≤23n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\gamma _{I}(G) \le \frac{2}{3}n$$\end{document}. In this paper, we characterize the connected graphs achieving equality in these bounds. In addition, we prove Nordhaus–Gaddum inequalities for the Italian domination number.
引用
收藏
页码:4273 / 4287
页数:14
相关论文
共 29 条
  • [1] Chambers EW(2009)Extremal problems for Roman domination SIAM J. Discrete Math. 23 1575-1586
  • [2] Kinnersley B(2016)Roman Discrete Appl. Math. 204 22-28
  • [3] Prince N(2004)-domination Discrete Math. 278 11-22
  • [4] West DB(2017)Roman domination in graphs Discrete Appl. Math. 217 557-564
  • [5] Chellali M(2018)Italian domination in trees Discrete Appl. Math. 236 235-245
  • [6] Haynes TW(2012)Perfect Roman domination in trees SIAM J. Discrete Math. 26 193-205
  • [7] Hedetniemi ST(2012)Roman domination on 2-connected graphs Discrete Math. 312 1386-1391
  • [8] McRae AA(1956)Upper bounds on Roman domination numbers of graphs Am. Math. Monthly 63 175-177
  • [9] Cockayne EJ(2018)On complementary graphs Discrete Appl. Math. 236 408-414
  • [10] Dreyer PA(1997)Independent Roman Johns Hopkins Mag. 49 40-594