2016/07/01 by Hu, Jiuhua, Shan, Erfang, Wang, Shaohui +2
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1607.00400
Given a graph G, a total dominating set Dt is a vertex set that every vertex of G is adjacent to some vertices of Dt and let dt(G,i) be the number of all total dominating sets with size i. The total domination polynomial, defined as Dt(G,x)=∑i=1| V(G)| dt(G,i)xi, 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.