On Cubic Graphs with Equal 2-domination and Connected 2-domination Numbers
Abstract
For a graph G= （V，E）, a subset S⊆ V(G) is said to be a 2- dominating set of G if for each vertex u ∈V− S, there exists a vertex v ∈ S such that d (u,v) ≤ 2. The minimum cardinality of 2-dominating sets of G is called the 2-domination number of G and denoted by γ2(G) . A 2-dominating set S is called a connected 2-dominating set of G , if the induced subgraph S is connected, the connected 2-domination number of G , denoted by γ 2c (G) , is the minimum cardinality of connected 2-dominating sets of G . In this paper, we characterize the class cubic graphs for which the 2-domination numbers are equal to the connected 2-domination numbers.
Keywords
2-domination number; Connected 2-domination number; Cubic graph.
Full Text:
PDFReferences
[1]R.B.Allan, and R.Laskar. On domination and independent domination of a graph, Discrete Mathematics. 23 (1978)73-76.
[2]S.Arumugam and J.Paulraj Joseph, On graphs with equal domination and connected domination numbers, Discrete Mathematics. 206 (1999) 45-49.
[3]J.A.Bondy and U.S.Murty, Graph Theory with Applications, the Macmillan Press LTD.,1976.
[4]F.Harary and M.Livingston, Characterization of trees with equal domination and independent domination numbers, Congr. Numer. 55(1986) 121-150.
[5]F.Harary and M.Livingston, Caterpillars with equal domination and independent domination numbers, in: V.R.Kulli (Ed.), Recent Studies in Graph Theory, Vishwa International Publications, Gulbarga, India, (1989) 149-154.
DOI: http://dx.doi.org/10.18686/ahe.v7i30.10971
Refbacks
- There are currently no refbacks.
