Order-sensitive domination in partially ordered sets and graphs

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Combinatorics of partially ordered sets (06A07) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: 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 i n D

or else

a < x < b

in

P

for some

a, b i n D

for every element

x

in

P

which is neither maximal nor minimal, and denote by

g a m m a_{o s} (P)

, the least size of an order-sensitive dominating set of

P

. For every graph

G

and integer

k g e q 2

, we associate a graded poset

m a t h s c r P_{k} (G)

of height

k

, and prove that

g a m m a_{o s} (m a t h s c r P_{3} (G)) = g a m m a_{e x t R} (G)

and

g a m m a_{o s} (m a t h s c r P_{4} (G)) = 2 g a m m a (G)

hold, where

g a m m a (G)

and

g a m m a_{e x t 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.

Recommendations

Cites work

Cited in

(2)

This page was built for publication: Order-sensitive domination in partially ordered sets and graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6105038)