TOPICS
Search

Dominating Equivalent Graphs


Nonisomorphic graphs may have the same domination polynomial. Such graphs are said to be dominating equivalent, dominating nonunique, or co-dominating graphs.

DominatingNonuniqueGraphs

The numbers of dominating nonunique graphs on n=1, 2, ... vertices are 0, 0, 0, 2, 13, 104, 876, 11680, 271063, 11977655, ... (OEIS A378517). The 15 Dominating nonunique graphs on five or fewer vertices are illustrated above.

A graph that does not share a domination polynomial with any other nonisomorphic graph is said to be a dominating unique graph (Akbari et al. 2010).


See also

Domination Root, Dominating Set, Dominating Unique Graphs, 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 A378517 in "The On-Line Encyclopedia of Integer Sequences."

Cite this as:

Weisstein, Eric W. "Dominating Equivalent Graphs." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/DominatingEquivalentGraphs.html

Subject classifications