No Detail Found!

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

Author(s)
Piyawat Wongthongcue Department of Mathematics, Faculty of Science, Silpakorn University,Nakhon Pathom,Thailand
Chalermpong Worawannotai Department of Mathematics, Faculty of Science, Silpakorn University,Nakhon Pathom,Thailand
Abstract
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) n 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) n 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 (G). The connected k-domination number of G, denoted by kc(G), is the minimum cardinality of a connected k-dominating set of G. For k = 1, we simply write c(G). It is known that the bounds 2c(G) > (G) + 1 and 2c(G) > c(G) + 1 are sharp. In this research article, we present the necessary condition of the connected graphs G with 2c(G) = (G) + 1 and the necessary condition of the connected graphs G with 2c(G) = c(G) + 1. Moreover, we present a graph construction that takes in any connected graph with r vertices and gives a graph G with 2c(G) = r, c(G) = r 1, and (G) 2 fr 1; r 2g.
Publication Details
Page(s) 28-35
Published Journal: Discrete Mathematics Letters, Volume: 13, Issue: 0, Year: 2024

Request the full text from PASTIC

Keywords
domination, connected domination, k-domination, connected k-domination.
References
Fink J. F.,M. S. Jacobson, J. F.,Chartrand G.,Lick D. R.,Wall C. E.,Lesniak L. M. .1985 .Graph Theory with Applications to Algorithms. , : 283-300.
Hansberg A. .2010 .Bounds on the connected k-domination number in graphs. Discrete Appl. Math, 158 : 1506-1510.
Haynes T. W.,Hedetniemi S.,Slater P. .1998 .. , : .
Ore O. .1962 .. American Mathematical Society, : .
Sampathkumar E.,Walikar H. B. .1979 .The connected domination number of a graph. J. Math. Phy. Sci, 13 : 607-613.
Volkmann L. .2009 .Connected p-domination in graphs, Util. , 79 : 81-90.
0

Citations

0

Downloads

23

Views