Dominating sets inducing large components

详细信息    查看全文

• 作者：Jos&eacute ; D. Alvaradoup>aup>up> ; up>up>josealvarado.mat17@gmail.com" class="auth_mail" title="E-mail the corresponding authorup> ; Simone Dantasup>aup>up> ; up>up>sdantas@im.uff.br" class="auth_mail" title="E-mail the corresponding authorup> ; Dieter Rautenbachup>bup>up> ; up>up>dieter.rautenbach@uni-ulm.de" class="auth_mail" title="E-mail the corresponding authorup>
• 关键词：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 ulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16301613&_mathId=si1.gif&_user=111111111&_pii=S0012365X16301613&_rdoc=1&_issn=0012365X&md5=e039b2ded7a5916da779413673d20dfb" title="Click to view the MathML source">G$G$, we study the ulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16301613&_mathId=si2.gif&_user=111111111&_pii=S0012365X16301613&_rdoc=1&_issn=0012365X&md5=ae24b0a33db559fb4e3686dfa757589c" title="Click to view the MathML source">k$k$-component domination number ulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16301613&_mathId=si3.gif&_user=111111111&_pii=S0012365X16301613&_rdoc=1&_issn=0012365X&md5=c8e8e080e29e8de7b4c857f85f92479d" title="Click to view the MathML source">γub>kub>(G) of ulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16301613&_mathId=si1.gif&_user=111111111&_pii=S0012365X16301613&_rdoc=1&_issn=0012365X&md5=e039b2ded7a5916da779413673d20dfb" title="Click to view the MathML source">G$G$ defined as the minimum cardinality of a dominating set ulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16301613&_mathId=si5.gif&_user=111111111&_pii=S0012365X16301613&_rdoc=1&_issn=0012365X&md5=d88c4ee33a4513b83b5d737d754e1fe8" title="Click to view the MathML source">D$D$ of ulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16301613&_mathId=si1.gif&_user=111111111&_pii=S0012365X16301613&_rdoc=1&_issn=0012365X&md5=e039b2ded7a5916da779413673d20dfb" title="Click to view the MathML source">G$G$ for which each component of the subgraph ulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16301613&_mathId=si7.gif&_user=111111111&_pii=S0012365X16301613&_rdoc=1&_issn=0012365X&md5=7acb9da03506c9b01598b0eedde769d9" title="Click to view the MathML source">G[D]$G\left[D\right]$ of ulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16301613&_mathId=si1.gif&_user=111111111&_pii=S0012365X16301613&_rdoc=1&_issn=0012365X&md5=e039b2ded7a5916da779413673d20dfb" title="Click to view the MathML source">G$G$ induced by ulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16301613&_mathId=si5.gif&_user=111111111&_pii=S0012365X16301613&_rdoc=1&_issn=0012365X&md5=d88c4ee33a4513b83b5d737d754e1fe8" title="Click to view the MathML source">D$D$ has order at least ulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16301613&_mathId=si2.gif&_user=111111111&_pii=S0012365X16301613&_rdoc=1&_issn=0012365X&md5=ae24b0a33db559fb4e3686dfa757589c" title="Click to view the MathML source">k$k$.

We show that for every positive integer ulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16301613&_mathId=si2.gif&_user=111111111&_pii=S0012365X16301613&_rdoc=1&_issn=0012365X&md5=ae24b0a33db559fb4e3686dfa757589c" title="Click to view the MathML source">k$k$, and every graph ulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16301613&_mathId=si1.gif&_user=111111111&_pii=S0012365X16301613&_rdoc=1&_issn=0012365X&md5=e039b2ded7a5916da779413673d20dfb" title="Click to view the MathML source">G$G$ of order ulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16301613&_mathId=si13.gif&_user=111111111&_pii=S0012365X16301613&_rdoc=1&_issn=0012365X&md5=c0224a75467241a33a7009a38ac55058" title="Click to view the MathML source">n$n$ at least ulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16301613&_mathId=si14.gif&_user=111111111&_pii=S0012365X16301613&_rdoc=1&_issn=0012365X&md5=6a6b1dde4fc3df8f7c0579b0114d85c1" title="Click to view the MathML source">k+1$k+1$ and without isolated vertices, we have urce" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16301613&_mathId=si15.gif&_user=111111111&_pii=S0012365X16301613&_rdoc=1&_issn=0012365X&md5=384a101f062eb4595b378c3d7cb4b84f">urce" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0012365X16301613-si15.gif">. Furthermore, we characterize all extremal graphs. We propose two conjectures concerning graphs of minimum degree ulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16301613&_mathId=si16.gif&_user=111111111&_pii=S0012365X16301613&_rdoc=1&_issn=0012365X&md5=9df61c18adbd6d8698eccffe5f32b96d" title="Click to view the MathML source">2$2$, and prove a related result.