×

Dominion of some graphs. (English) Zbl 1469.05076

Summary: Given a graph \(G=(V,E)\), a subset \(S\subseteq V\) is a dominating set if every vertex in \(V\setminus S\) is adjacent to some vertex in \(S\). The dominating set with the least cardinality, \(\gamma\), is called a \(\gamma\)-set which is commonly known as a minimum dominating set. The dominion of a graph \(G\), denoted by \(\zeta(G)\), is the number of its \(\gamma\)-sets. Some relations between these two seemingly distinct parameters are established. In particular, we present the dominions of paths, some cycles and the join of any two graphs.

MSC:

05C30 Enumeration in graph theory
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Keywords:

domination; dominion
PDFBibTeX XMLCite
Full Text: Link