A new method for proving dominating uniqueness of graphs

Abstract EN

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Þ n S is adjacent to at least one vertex of S.

The domination polynomial of G is the polynomial DðG; xÞ ¼ Pn i¼cðGÞ dðG; iÞxi, where dðG; iÞ is the number of dominating sets of G of size i, and cð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 ffi 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-Km is dominating unique for each m P 0.

As a by-product, the dominating uniqueness of many families of dense graphs is also determined.