Nonisomorphic graphs may have the same domination polynomial. A graph that does not share a domination polynomial with any other nonisomorphic graph is said to be dominating unique (or -unique for short) (Akbari et al. 2010).
The numbers of dominating unique graphs on , 2, ... vertices are 1, 2, 4, 9, 21, 52, 168, 666, 3605, 27513, ... (OEIS A378516), the first few of which are illustrated above. Classes of graphs that are dominating unique include complete graph, cycle graphs, empty graphs, hypercube graphs, pan graphs, star graphs, and wheel graphs.
Graphs that share the same domination polynomial are said to be dominating equivalent, dominating nonunique, or co-dominating graphs.
See also
Dominating Equivalent Graphs, Domination Root, Dominating Set, Domination Polynomial
Explore with Wolfram|Alpha
References
Akbari, S.; Alikhani, S.; and Peng, Y.-H. "Characterization of Graphs Using Domination Polynomials." Eur. J. Combin. 31, 1714-1724, 2010.Sloane, N. J. A. Sequence A378516 in "The On-Line Encyclopedia of Integer Sequences."
Referenced on Wolfram|Alpha
Cite this as:
Weisstein, Eric W. "Dominating Unique Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/DominatingUniqueGraph.html