Some necessary conditions for graphs with extremal connected 2-domination number

被引:0
作者
Wongthongcue, Piyawat [1 ]
Worawannotai, Chalermpong [1 ]
机构
[1] Silpakorn Univ, Dept Math, Fac Sci, Bangkok, Nakhon Pathom, Thailand
关键词
domination; connected domination; k-domination; connected k-domination;
D O I
10.47443/dml.2023.230
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
Let G be a graph with no multiple edges and loops. A subset S of the vertex set of G is a dominating set of G if every vertex in V (G)\S is adjacent to at least one vertex of S. A connected k-dominating set of G is a subset S of the vertex set V (G) such that every vertex in V (G) \ S has at least k neighbors in S and the subgraph G[S] is connected. The domination number of G is the number of vertices in a minimum dominating set of G, denoted by gamma(G). The connected k-domination number of G, denoted by gamma(c)(k) (G), is the minimum cardinality of a connected k-dominating set of G. For k = 1, we simply write gamma(c)(G). It is known that the bounds gamma(c)(2)(G) >= gamma(G) + 1 and gamma(c)(2)(G) >= gamma(c)(G) + 1 are sharp. In this research article, we present the necessary condition of the connected graphs G with gamma(c)(2)(G) = gamma(G) + 1 and the necessary condition of the connected graphs G with gamma(c)(2)(G) = gamma(c)(G)+1. Moreover, we present a graph construction that takes in any connected graph with r vertices and gives a graph G with gamma(c)(2)(G) = r, gamma(c)(G) = r - 1, and gamma(G) is an element of {r - 1, r - 2}.
引用
收藏
页码:28 / 35
页数:8
相关论文
共 6 条
  • [1] Fink J.F., 1985, GRAPH THEORY APPL AL, P283
  • [2] Bounds on the connected k-domination number in graphs
    Hansberg, Adriana
    [J]. DISCRETE APPLIED MATHEMATICS, 2010, 158 (14) : 1506 - 1510
  • [3] Haynes T.W., 1998, PURE APPL MATH, V208, DOI 10.1201/9781482246582
  • [4] Ore O., 1962, Theory of graphs, V38
  • [5] Sampathkumar E, 1979, J. Math. Phys. Sci., V16, P607
  • [6] Volkmann L, 2009, UTILITAS MATHEMATICA, V79, P81