论文标题
常见的统治完美图
Common domination perfect graphs
论文作者
论文摘要
图$ g $中的主导集是一个$ s $ s $的顶点，因此每个不属于$ s $的顶点都与$ s $的顶点相邻。 $ g $的支配数字$γ（g）$是$ g $的主要基数的最低基数。 $ g $的共同独立数$α_c（g）$是最大的整数$ r $，因此每个顶点$ g $都属于某些独立的基数至少〜$ r $。共同的独立数是在独立的支配数字$ i（g）$和$ g $的独立$α（g）$之间挤压的，即$γ（g）\ le i（g）\ le i（g）\leα_c（g）\leα（g）$。如果$γ（h）= i（h）$对于每个引起的$ g $ $ g $的$γ（h）= i（h）$，则图形$ g $是完美的。如果$γ（h）=α_c（h）$，我们将图形$ g $定义为普遍的统治，则每个感应的子图$ h $的$ g $。我们根据十个禁止诱发的子图表提供了共同支配完美图的表征。
A dominating set in a graph $G$ is a set $S$ of vertices such that every vertex that does not belong to $S$ is adjacent to a vertex in $S$. The domination number $γ(G)$ of $G$ is the minimum cardinality of a dominating set of $G$. The common independence number $α_c(G)$ of $G$ is the greatest integer $r$ such that every vertex of $G$ belongs to some independent set of cardinality at least~$r$. The common independence number is squeezed between the independent domination number $i(G)$ and the independence number $α(G)$ of $G$, that is, $γ(G) \le i(G) \le α_c(G) \le α(G)$. A graph $G$ is domination perfect if $γ(H) = i(H)$ for every induced subgraph $H$ of $G$. We define a graph $G$ as common domination perfect if $γ(H) = α_c(H)$ for every induced subgraph $H$ of $G$. We provide a characterization of common domination perfect graphs in terms of ten forbidden induced subgraphs.
