Total dominating sequences in graphs

详细信息    查看全文

• 作者：Bo&scaron ; tjan Bre&scaron ; ar^a ; ^b ; ^{Bostjan.Bresar@um.si" class="auth_mail" title="E-mail the corresponding author} ; Michael A. Henning^c ; ^{mahenning@uj.ac.za" class="auth_mail" title="E-mail the corresponding author} ; Douglas F. Rall^d ; ^{doug.rall@furman.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Total domination ; Edge cover ; Grundy total domination number
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 June 2016
• 年：2016
• 卷：339
• 期：6
• 页码：1665-1676
• 全文大小：445 K

文摘

A vertex in a graph totally dominates another vertex if they are adjacent. A sequence of vertices in a graph 322e6fdb7e078e4d37c58a" title="Click to view the MathML source">G$G$ is called a total dominating sequence if every vertex v$v$ in the sequence totally dominates at least one vertex that was not totally dominated by any vertex that precedes v$v$ in the sequence, and at the end all vertices of 322e6fdb7e078e4d37c58a" title="Click to view the MathML source">G$G$ are totally dominated. While the length of a shortest such sequence is the total domination number of 322e6fdb7e078e4d37c58a" title="Click to view the MathML source">G$G$, in this paper we investigate total dominating sequences of maximum length, which we call the Grundy total domination number, ${\gamma }_{\mathrm{gr}}^t\left(G\right)$, of 322e6fdb7e078e4d37c58a" title="Click to view the MathML source">G$G$. We provide a characterization of the graphs 322e6fdb7e078e4d37c58a" title="Click to view the MathML source">G$G$ for which ${\gamma }_{\mathrm{gr}}^t\left(G\right)=\left|V\left(G\right)\right|$ and of those for which ${\gamma }_{\mathrm{gr}}^t\left(G\right)=2$. We show that if T$T$ is a nontrivial tree of order n$n$ with no vertex with two or more leaf-neighbors, then ${\gamma }_{\mathrm{gr}}^t\left(T\right)\ge \frac{2}{3}(n+1)$, and characterize the extremal trees. We also prove that for k≥3$k\ge 3$, if 322e6fdb7e078e4d37c58a" title="Click to view the MathML source">G$G$ is a connected k$k$-regular graph of order n$n$ different from K_k,k$K_{k,k}$, then ${\gamma }_{\mathrm{gr}}^t\left(G\right)\ge (n+\lceil \frac{k}{2}\rceil -2)/(k-1)$ if 322e6fdb7e078e4d37c58a" title="Click to view the MathML source">G$G$ is not bipartite and ${\gamma }_{\mathrm{gr}}^t\left(G\right)\ge (n+2\lceil \frac{k}{2}\rceil -4)/(k-1)$ if 322e6fdb7e078e4d37c58a" title="Click to view the MathML source">G$G$ is bipartite. The Grundy total domination number is proven to be bounded from above by two times the Grundy domination number, while the former invariant can be arbitrarily smaller than the latter. Finally, a natural connection with edge covering sequences in hypergraphs is established, which in particular yields the NP-completeness of the decision version of the Grundy total domination number.