论文标题
在图形上的统治数等于色度和统治者色数的图表上
On graphs whose domination number is equal to chromatic and dominator chromatic numbers
论文作者
论文摘要
对于图$ g =（v（g），e（g））$，一个主导集$ d $是$ v（g）$的顶点子集，其中每个顶点的$ v（g）\ setminus d $均与$ d $的顶点相邻。 $ g $的支配数是$ g $的主要基数的最低基数，并用$γ（g）$表示。 $ g $的着色是一个分区$ c =（v_ {1}，...，v_ {k}）$，使得独立集中的$ v_ {i} $中的每一个。色度是$ g $的所有颜色中的最小$ k $ $ c =（v_ {1}，...，v_ {k}）$，并用$χ（g）$表示。 $ c =（v_ {1}，...，v_ {k}）$被认为是统治者，如果对于所有$ v_ {i} $，每个顶点$ v \ in v_ {i} $ in v_ {i} $ in $ v_ {i} $ in $ v_ {i} $或与每个顶点相邻$ v_} $ v_ {j} $ { $ g $的Dominator色度数是$ G $的所有Dominator着色的最低$ K $，并用$χ_{D}（G）$表示。此外，如果$γ（g）=χ（g）=χ_{d}（g）= k $，则图$ g $是$ d（k）$。在本文中，对于$ n \ geq 4k -3 $，我们证明始终存在$ d（k）$图$ n $的图。我们进一步证明，当$ k \ in \ {3，4 \} $时，没有平面$ d（k）$ graph。也就是说，我们证明，对于非平凡的平面图$ g $，图$ g $是$ d（k）$，并且仅当$ g $ as $ k_ {2，q} $中，其中$ q \ geq 2 $。
For a graph $G = (V(G), E(G))$, a dominating set $D$ is a vertex subset of $V(G)$ in which every vertex of $V(G) \setminus D$ is adjacent to a vertex in $D$. The domination number of $G$ is the minimum cardinality of a dominating set of $G$ and is denoted by $γ(G)$. A coloring of $G$ is a partition $C = (V_{1}, ... ,V_{k})$ such that each of $V_{i}$ in an independent set. The chromatic number is the smallest $k$ among all colorings $C = (V_{1}, ... ,V_{k})$ of $G$ and is denoted by $χ(G)$. A coloring $C = (V_{1}, ... ,V_{k})$ is said to be dominator if, for all $V_{i}$, every vertex $v \in V_{i}$ is singleton in $V_{i}$ or is adjacent to every vertex of $V_{j}$. The dominator chromatic number of $G$ is the minimum $k$ of all dominator colorings of $G$ and is denoted by $χ_{d}(G)$. Further, a graph $G$ is $D(k)$ if $γ(G) = χ(G) = χ_{d}(G) = k$. In this paper, for $n \geq 4k - 3$, we prove that there always exists a $D(k)$ graph of order $n$. We further prove that there is no planar $D(k)$ graph when $k \in \{3, 4\}$. Namely, we prove that, for a non-trivial planar graph $G$, the graph $G$ is $D(k)$ if and only if $G$ is $K_{2, q}$ where $q \geq 2$.
