Given a graph G equals (V,E), a subset S subset of V is a dominating set if every vertex in V minus 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.
翻译：给定图 G = (V,E)，若子集 S ⊆ V 满足 V \ S 中的每个顶点都与 S 中的某个顶点相邻，则称 S 为支配集。具有最小基数 γ 的支配集称为 γ-集，通常称为最小支配集。图 G 的支配集数量，记作 ζ(G)，即其所有 γ-集的数目。本文建立了这两个看似不同参数之间的一些关系。特别地，我们给出了路径、某些环图以及任意两个图的联图的支配集数量。
相关内容
Arxiv
0+阅读 · 2025年12月30日
Arxiv
0+阅读 · 2025年12月28日
Arxiv
0+阅读 · 2025年12月25日
相关VIP内容
相关资讯
微信扫码咨询专知VIP会员