Order-sensitive domination in partially ordered sets
share
For a (finite) partially ordered set (poset) P, we call a dominating set D in the comparability graph Comp(P) of P, an order-sensitive dominating set in P if either x∈ D or else a<x<b in P for some a,b∈ 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≥ 2, we associate a graded poset 𝒫_k(G) of height k, and prove that γ_os(𝒫_3(G))=γ_R(G) and γ_os(𝒫_4(G))=2γ(G) hold, where γ(G) and γ_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.
READ FULL TEXT