[1,2][1,2]-domination in graphs

A vertex subset DD of a graph G=(V,E)G=(V,E) is a [1,2][1,2]-set if, 1≤|N(v)∩D|≤21≤|N(v)∩D|≤2 for every vertex v∈V∖Dv∈V∖D, that is, each vertex v∈V∖Dv∈V∖D is adjacent to either one or two vertices in DD. The minimum cardinality of a [1,2][1,2]-set of GG, denoted by γ[1,2](G)γ[1,2](G), is called the [1,2][1,2]-domination number of GG. Chellali et al. (2013) showed that there exist graphs GG of order nn with γ[1,2](G)=nγ[1,2](G)=n. But, the complete characterization of such graphs seems to be a difficult task. As responding to some open questions posed by Chellali et al., we further show that such graphs exist even among some special families of graphs, such as planar graphs, bipartite graphs (triangle-free graphs). It is also shown that for a tree TT of order n≥3n≥3 with kk leaves, if dT(v)≥4dT(v)≥4 for any non-leaf vertex vv, then γ[1,2](T)=n−kγ[1,2](T)=n−k. In addition, Nordhaus–Gaddum-type inequalities are established for the [1,2][1,2]-domination numbers of graphs. Thereby, we solve several open problems posed by Chellali et al.