论文标题
订单敏感的统治在部分排序的集合中
Order-sensitive domination in partially ordered sets
论文作者
论文摘要
For a (finite) partially ordered set (poset) $P$, we call a dominating set $D$ in the comparability graph of $P$, an order-sensitive dominating set in $P$ if either $x\in D$ or else $a<x<b$ in $P$ for some $a,b\in D$ for every element $x$ in $P$ which is neither maximal nor minimal, and denote by $γ_{OS}（p）$，$ p $的订单敏感的主导集的最小尺寸。对于每个图$ g $和Integer $ k \ geq 2 $，我们将分级的poset $ \ mathscr {p} _k（g）$ of height $ k $ of $ k $，并证明$γ_{os}（\ mathscr {p} _3（g）_3（g）_3（g） $γ_{OS}（\ Mathscr {p} _4（g））=2γ（g）$ hold，其中$γ（g）$和$γ_ {\ text {r}}（g）$分别是$ g $的统治和罗马支配数量。除此之外，我们还介绍了Helly Poset的概念，并证明当$ P $是Helly Poset时，可以将订单敏感的统治数的计算$ P $解释为图形的加权集合分区编号，$ p $的中间图。此外，我们表明，poset $ p $的订单敏感性统治数完全对应于$ p $的相关两部分变换的biclique顶点分区。最后，我们证明，在任意高度的POSET上，订单敏感的统治的决策问题是NP组件，这是通过使用等于-3 $ -SAT问题的减少来获得的。
For a (finite) partially ordered set (poset) $P$, we call a dominating set $D$ in the comparability graph of $P$, an order-sensitive dominating set in $P$ if either $x\in D$ or else $a<x<b$ in $P$ for some $a,b\in D$ for every element $x$ in $P$ which is neither maximal nor minimal, and denote by $γ_{os}(P)$, the least size of an order-sensitive dominating set of $P$. For every graph $G$ and integer $k\geq 2$, we associate a graded poset $\mathscr{P}_k(G)$ of height $k$, and prove that $γ_{os}(\mathscr{P}_3(G))=γ_{\text{R}}(G)$ and $γ_{os}(\mathscr{P}_4(G))=2γ(G)$ hold, where $γ(G)$ and $γ_{\text{R}}(G)$ are the domination and Roman domination number of $G$, respectively. Apart from these, we introduce the notion of a Helly poset, and prove that when $P$ is a Helly poset, the computation of order-sensitive domination number of $P$ can be interpreted as a weighted clique partition number of a graph, the middle graph of $P$. Moreover, we show that the order-sensitive domination number of a poset $P$ exactly corresponds to the biclique vertex-partition number of the associated bipartite transformation of $P$. Finally, we prove that the decision problem of order-sensitive domination on posets of arbitrary height is NP-complete, which is obtained by using a reduction from EQUAL-$3$-SAT problem.
