Matchings, path covers and domination

详细信息    查看全文

• 作者：Michael A. Henning ^{mahenning@uj.ac.za" class="auth_mail" title="E-mail the corresponding author} ; Kirsti Wash ; ^{kirsti.wash@trincoll.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Matching ; Path cover ; Total domination ; Neighborhood total domination
• 刊名：Discrete Mathematics
• 出版年：2017
• 出版时间：6 January 2017
• 年：2017
• 卷：340
• 期：1
• 页码：3207-3216
• 全文大小：468 K

文摘

We show that if class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302412&_mathId=si10.gif&_user=111111111&_pii=S0012365X16302412&_rdoc=1&_issn=0012365X&md5=de3b43c2b996bb409bc4d8a297acf355" title="Click to view the MathML source">Gclass="mathContainer hidden">class="mathCode">$G$ is a graph with minimum degree at least three, then class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302412&_mathId=si11.gif&_user=111111111&_pii=S0012365X16302412&_rdoc=1&_issn=0012365X&md5=ae84df3fde6f49bc831db7fa1a8b8ce3" title="Click to view the MathML source">γ_t(G)≤α^′(G)+(pc(G)−1)∕2class="mathContainer hidden">class="mathCode">${\gamma }_t\left(G\right)\le {\alpha }^{\prime }\left(G\right)+(\mathrm{pc}\left(G\right)-1)∕2$ and this bound is tight, where class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302412&_mathId=si12.gif&_user=111111111&_pii=S0012365X16302412&_rdoc=1&_issn=0012365X&md5=241a6c5eb95b02abf428c7d5fb13d981" title="Click to view the MathML source">γ_t(G)class="mathContainer hidden">class="mathCode">${\gamma }_t\left(G\right)$ is the total domination number of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302412&_mathId=si10.gif&_user=111111111&_pii=S0012365X16302412&_rdoc=1&_issn=0012365X&md5=de3b43c2b996bb409bc4d8a297acf355" title="Click to view the MathML source">Gclass="mathContainer hidden">class="mathCode">$G$, class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302412&_mathId=si14.gif&_user=111111111&_pii=S0012365X16302412&_rdoc=1&_issn=0012365X&md5=0e55084169e5df4e12290d1beb74d1b7" title="Click to view the MathML source">α^′(G)class="mathContainer hidden">class="mathCode">${\alpha }^{\prime }\left(G\right)$ the matching number of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302412&_mathId=si10.gif&_user=111111111&_pii=S0012365X16302412&_rdoc=1&_issn=0012365X&md5=de3b43c2b996bb409bc4d8a297acf355" title="Click to view the MathML source">Gclass="mathContainer hidden">class="mathCode">$G$ and class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302412&_mathId=si16.gif&_user=111111111&_pii=S0012365X16302412&_rdoc=1&_issn=0012365X&md5=74f37885e6b2ddf75c55396e75dedbc5" title="Click to view the MathML source">pc(G)class="mathContainer hidden">class="mathCode">$\mathrm{pc}\left(G\right)$ the path covering number of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302412&_mathId=si10.gif&_user=111111111&_pii=S0012365X16302412&_rdoc=1&_issn=0012365X&md5=de3b43c2b996bb409bc4d8a297acf355" title="Click to view the MathML source">Gclass="mathContainer hidden">class="mathCode">$G$ which is the minimum number of vertex disjoint paths such that every vertex belongs to a path in the cover. We show that if class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302412&_mathId=si10.gif&_user=111111111&_pii=S0012365X16302412&_rdoc=1&_issn=0012365X&md5=de3b43c2b996bb409bc4d8a297acf355" title="Click to view the MathML source">Gclass="mathContainer hidden">class="mathCode">$G$ is a connected graph on at least six vertices, then class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302412&_mathId=si19.gif&_user=111111111&_pii=S0012365X16302412&_rdoc=1&_issn=0012365X&md5=a6d1430000090710644078da4eae1b83" title="Click to view the MathML source">γ_nt(G)≤α^′(G)+pc(G)∕2class="mathContainer hidden">class="mathCode">${\gamma }_{\mathrm{nt}}\left(G\right)\le {\alpha }^{\prime }\left(G\right)+\mathrm{pc}\left(G\right)∕2$ and this bound is tight, where class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302412&_mathId=si20.gif&_user=111111111&_pii=S0012365X16302412&_rdoc=1&_issn=0012365X&md5=f961b316bf0a9ca911e0eaf83fc62a3c" title="Click to view the MathML source">γ_nt(G)class="mathContainer hidden">class="mathCode">${\gamma }_{\mathrm{nt}}\left(G\right)$ denotes the neighborhood total domination number of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302412&_mathId=si10.gif&_user=111111111&_pii=S0012365X16302412&_rdoc=1&_issn=0012365X&md5=de3b43c2b996bb409bc4d8a297acf355" title="Click to view the MathML source">Gclass="mathContainer hidden">class="mathCode">$G$. We observe that every graph class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302412&_mathId=si10.gif&_user=111111111&_pii=S0012365X16302412&_rdoc=1&_issn=0012365X&md5=de3b43c2b996bb409bc4d8a297acf355" title="Click to view the MathML source">Gclass="mathContainer hidden">class="mathCode">$G$ of order class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302412&_mathId=si23.gif&_user=111111111&_pii=S0012365X16302412&_rdoc=1&_issn=0012365X&md5=8cc3809fd938d18098980da0e66388b7" title="Click to view the MathML source">nclass="mathContainer hidden">class="mathCode">$n$ satisfies class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302412&_mathId=si24.gif&_user=111111111&_pii=S0012365X16302412&_rdoc=1&_issn=0012365X&md5=fee3a58d47229118ad4af73cb16529f5" title="Click to view the MathML source">α^′(G)+pc(G)∕2≥n∕2class="mathContainer hidden">class="mathCode">${\alpha }^{\prime }\left(G\right)+\mathrm{pc}\left(G\right)∕2\ge n∕2$, and we characterize the trees achieving equality in this bound.