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 b43c2b996bb409bc4d8a297acf355" title="Click to view the MathML source">G$G$ is a graph with minimum degree at least three, then e6f49bc831db7fa1a8b8ce3" title="Click to view the MathML source">γ_t(G)≤α^′(G)+(pc(G)−1)∕2${\gamma }_t\left(G\right)\le {\alpha }^{\prime }\left(G\right)+(\mathrm{pc}\left(G\right)-1)∕2$ and this bound is tight, where b02abf428c7d5fb13d981" title="Click to view the MathML source">γ_t(G)${\gamma }_t\left(G\right)$ is the total domination number of b43c2b996bb409bc4d8a297acf355" title="Click to view the MathML source">G$G$, α^′(G)${\alpha }^{\prime }\left(G\right)$ the matching number of b43c2b996bb409bc4d8a297acf355" title="Click to view the MathML source">G$G$ and e6b2ddf75c55396e75dedbc5" title="Click to view the MathML source">pc(G)$\mathrm{pc}\left(G\right)$ the path covering number of b43c2b996bb409bc4d8a297acf355" title="Click to view the MathML source">G$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 b43c2b996bb409bc4d8a297acf355" title="Click to view the MathML source">G$G$ is a connected graph on at least six vertices, then γ_nt(G)≤α^′(G)+pc(G)∕2${\gamma }_{\mathrm{nt}}\left(G\right)\le {\alpha }^{\prime }\left(G\right)+\mathrm{pc}\left(G\right)∕2$ and this bound is tight, where b316bf0a9ca911e0eaf83fc62a3c" title="Click to view the MathML source">γ_nt(G)${\gamma }_{\mathrm{nt}}\left(G\right)$ denotes the neighborhood total domination number of b43c2b996bb409bc4d8a297acf355" title="Click to view the MathML source">G$G$. We observe that every graph b43c2b996bb409bc4d8a297acf355" title="Click to view the MathML source">G$G$ of order e66388b7" title="Click to view the MathML source">n$n$ satisfies a58d47229118ad4af73cb16529f5" title="Click to view the MathML source">α^′(G)+pc(G)∕2≥n∕2${\alpha }^{\prime }\left(G\right)+\mathrm{pc}\left(G\right)∕2\ge n∕2$, and we characterize the trees achieving equality in this bound.