Total domination polynomials of graphs

MaRDI QIDQ6275161zbMATH OpenFDO

Authors Jiuhua Hu, Erfang Shan, Shaohui Wang, Chunxiang Wang, Bing Wei

Publication date 1 July 2016

Abstract: Given a graph $G$, a total dominating set $D_t$ is a vertex set that every vertex of $G$ is adjacent to some vertices of $D_t$ and let $d_t(G,i)$ be the number of all total dominating sets with size $i$. The total domination polynomial, defined as $D_t(G,x)=sumlimit{s}_{i=1}^{|V(G)|}{d}_t(G,i)x^i$, recently has been one of the considerable extended research in the field of domination theory. In this paper, we obtain the vertex-reduction and edge-reduction formulas of total domination polynomials. As consequences, we give the total domination polynomials for paths and cycles. Additionally, we determine the sharp upper bounds of total domination polynomials for trees and characterize the corresponding graphs attaining such bounds. Finally, we use the reduction-formulas to investigate the relations between vertex sets and total domination polynomials in $G$.

This page was built for publication: Total domination polynomials of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6275161)