-domination in graphs

详细信息    查看全文

• 作者：Xiaojing Yang ; Baoyindureng Wu ; ^{baoyin@xju.edu.cn" class="auth_mail} ; ^{baoyinwu@gmail.com" class="auth_mail} ; ^{wubaoyin@hotmail.com" class="auth_mail}
• 关键词：[1 ; 2][1 ; 2]-sets ; Domination ; Lexicographic product ; Nordhaus&ndash ; Gaddum ; Restrained domination
• 刊名：Discrete Applied Mathematics
• 出版年：1 October 2014
• 年：2014
• 卷：175
• 期：Complete
• 页码：79-86
• 全文大小：414 K

文摘

A vertex subset D$D$ of a graph G=(V,E)$G=(V,E)$ is a [1,2]$[1,2]$-set if, 1≤|N(v)∩D|≤2$1\le |N\left(v\right)\cap D|\le 2$ for every vertex v∈V鈭朌$v\in V鈭?/mo><mi>D</mi>$, that is, each vertex v∈V鈭朌$v\in V鈭?/mo><mi>D</mi>$ is adjacent to either one or two vertices in D$D$. The minimum cardinality of a [1,2]$[1,2]$-set of G$G$, denoted by 纬_[1,2](G)${纬}_{[1,2]}\left(G\right)$, is called the [1,2]$[1,2]$-domination number of G$G$. Chellali et al. (2013) showed that there exist graphs G$G$ of order n$n$ with 纬_[1,2](G)=n${纬}_{[1,2]}\left(G\right)=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 T$T$ of order n≥3$n\ge 3$ with k$k$ leaves, if d_T(v)≥4$d_T\left(v\right)\ge 4$ for any non-leaf vertex v$v$, then 纬_[1,2](T)=n−k${纬}_{[1,2]}\left(T\right)=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.