Dominating sets inducing large components

详细信息    查看全文

• 作者：José ; D. Alvarado^a ; ^{josealvarado.mat17@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Simone Dantas^a ; ^{sdantas@im.uff.br" class="auth_mail" title="E-mail the corresponding author} ; Dieter Rautenbach^b ; ^{dieter.rautenbach@uni-ulm.de" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Domination ; Total domination
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 November 2016
• 年：2016
• 卷：339
• 期：11
• 页码：2715-2720
• 全文大小：387 K

文摘

As a common generalization of the domination number and the total domination number of a graph d20dfb" title="Click to view the MathML source">G$G$, we study the k$k$-component domination number γ_k(G)${\gamma }_k\left(G\right)$ of d20dfb" title="Click to view the MathML source">G$G$ defined as the minimum cardinality of a dominating set 37d754e1fe8" title="Click to view the MathML source">D$D$ of d20dfb" title="Click to view the MathML source">G$G$ for which each component of the subgraph G[D]$G\left[D\right]$ of d20dfb" title="Click to view the MathML source">G$G$ induced by 37d754e1fe8" title="Click to view the MathML source">D$D$ has order at least k$k$.

We show that for every positive integer k$k$, and every graph d20dfb" title="Click to view the MathML source">G$G$ of order n$n$ at least k+1$k+1$ and without isolated vertices, we have ${\gamma }_k\left(G\right)\le \frac{kn}{k+1}$. Furthermore, we characterize all extremal graphs. We propose two conjectures concerning graphs of minimum degree 2$2$, and prove a related result.