Loading...
Please wait, while we are loading the content...
Similar Documents
New Bounds on the Rainbow Domination Subdivision Number
| Content Provider | Semantic Scholar |
|---|---|
| Author | Falahat, Mohyedin Sheikholeslami, Seyed Mahmoud Volkmann, Lutz |
| Copyright Year | 2014 |
| Abstract | A 2-rainbow dominating function (2RDF) of a graph G is a function f from the vertex set V(G) to the set of all subsets of the set {1, 2} such that for any vertex v ∈ V(G) with f (v) = ∅ the condition ⋃ u∈N(v) f (u) = {1, 2} is fulfilled, where N(v) is the open neighborhood of v. The weight of a 2RDF f is the value ω( f ) = ∑ v∈V | f (v)|. The 2-rainbow domination number of a graph G, denoted by γr2(G), is the minimum weight of a 2RDF of G. The 2-rainbow domination subdivision number sdγr2(G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the 2-rainbow domination number. In this paper we prove that for every simple connected graph G of order n ≥ 3, sdγr2 (G) ≤ 3 + min{d2(v) | v ∈ V and d(v) ≥ 2} where d2(v) is the number of vertices of G at distance 2 from v. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.doiserbia.nb.rs/img/doi/0354-5180/2014/0354-51801403615F.pdf |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Connectivity (graph theory) Dominating set Emoticon Graph (discrete mathematics) Graph - visual representation Minimum weight Subdivision surface Vertex |
| Content Type | Text |
| Resource Type | Article |
