Order-sensitive domination in partially ordered sets and graphs
ORDER, cilt.40, sa.1, ss.157-172, 2023 (SCI-Expanded, Scopus)
- Yayın Türü: Makale / Tam Makale
- Cilt numarası: 40 Sayı: 1
- Basım Tarihi: 2023
- Doi Numarası: 10.1007/s11083-022-09599-2
- Dergi Adı: ORDER
- Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, MathSciNet, zbMATH
- Sayfa Sayıları: ss.157-172
- Anahtar Kelimeler: Domination, Partially ordered set, Order-sensitive, Comparability, Roman domination, Biclique Vertex-partition
- Süleyman Demirel Üniversitesi Adresli: Evet
Özet
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∈ 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 to G a graded poset P_k(G) of height k, and prove that γ_os(P_3(G))=γ_R(G) and γ_os(P_4(G))=2γ(G) hold, where γ(G) and γ_R(G) are the domination and Roman domination number of G, respectively. 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.