Connected domination value in graphs
Abstract
In a connected graph G = (V,E), a set D ⊂ V is a connected dominating set if for every vertex v ∈ V \ D, there exists u ∈ D such that u and v are adjacent, and the subgraph〈D〉induced by D in G is connected. A connected dominating set of minimum cardinality is called a γc-set of G. For each vertex v ∈ V, we define the connected domination value of v to be the number of γc-sets of G to which v belongs. In this paper, we study the properties of connected domination value of a connected graph G and its relation to other parameters of a connected graph. Finally, we compute the connected domination value and number of γc-sets for a few well-known family of graphs.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2021.9.1.11
References
E.J. Cockayne, R.M. Dawes, and S.T. Hedetniemi, Total domination in graphs, Networks 10 (3) (1980), 211–219.
E.J. Cockayne, M.A. Henning, and C.M. Mynhardt, Vertices contained in all or in no minimum total dominating set of a tree, Discrete Math. 260 (2003), 37–44.
A. Das, R.C. Laskar, and N.J. Rad, On -domination in graphs, Graphs Combin. 34 (2018), 193–205.
A. Das, Partial domination in graphs, Iran. J. Sci. Technol. Trans. A Sci. 43 (2019),1713–1718.
A. Das, Coefficient of domination in graph, Discrete Math. Algorithms Appl. 9(2) (2017), 1750018.
I.S. Hamid, S. Balamurugan, and A. Navaneethakrishnan, A note on isolate domination, Electron. J. Graph Theory Appl. 4 (1) (2016), 94–100.
T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of domination in graphs, Marcel Dekker Inc., 1998.
T.W. Haynes, S.T. Hedetniemi, and P.J. Slater (eds), Domination in Graphs: Advanced Topics, Marcel Dekker Inc., 1998.
C.X. Kang, Total domination value in graphs, Util. Math. 95 (2014), 263–279.
N. Meddah and M. Blidia, Vertices contained in all or in no minimum k-dominating set of a tree, AKCE Int. J. Graphs Comb. 11 (1) (2014), 105–113.
D.A. Mojdeh, S.R. Musawi, and E. Nazari, On the distance domination number of bipartite graphs, Electron. J. Graph Theory Appl. 8 (2) (2020), 353–364.
C.M. Mynhardt, Vertices contained in every minimum dominating set of a tree, J. Graph Theory 31 (1999), 163–177.
E. Sampathkumar, and H.B. Walikar, The connected domination number of a graph, J. Math. Phy. Sci. 13 (6) (1979), 607–613.
D.B. West, Introduction to Graph Theory, Prentice Hall, 2001.
E. Yi, Domination value in graphs, Contrib. Discrete Math. 7 (2) (2012), 30–43.
E. Yi: Domination value in P2Pn and P2Cn, J. Combin. Math. Combin. Comput. 82 (2012), 59–75.
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.