A new method for proving dominating uniqueness of graphs

Let G be a graph of order n . A subset S of V ( G ) is a dominating set of G if every vertex in V ( G ) ⧹ S is adjacent to at least one vertex of S . The domination polynomial of G is the polynomial D ( G , x ) = ∑ i = γ ( G ) n d ( G , i ) x i , where d ( G , i ) is the number of dominating sets of G of size i , and γ ( G ) is the size of a smallest dominating set of G , called the domination number of G . We say two graphs G and H are dominating equivalent if D ( G , x ) = D ( H , x ) . A graph G is said to be dominating unique , or simply D -unique, if D ( H , x ) = D ( G , x ) implies that H ≅ G . The goal of this paper is to find a new approach to determine the dominating uniqueness of graphs. In this paper, we define a new graph polynomial, called star polynomial, and introduced an analogy notion of star uniqueness of graphs. As an application, if G is a graph without isolated vertices, we show that a graph G is star unique if and only if G ‾ ∨ K m is dominating unique for each m ⩾ 0 . As a by-product, the dominating uniqueness of many families of dense graphs is also determined.