ﻻ يوجد ملخص باللغة العربية
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 $xin D$ or else $a<x<b$ in $P$ for some $a,bin D$ for every element $x$ in $P$ which is neither maximal nor minimal, and denote by $gamma_{os}(P)$, the least size of an order-sensitive dominating set of $P$. For every graph $G$ and integer $kgeq 2$, we associate a graded poset $mathscr{P}_k(G)$ of height $k$, and prove that $gamma_{os}(mathscr{P}_3(G))=gamma_{text{R}}(G)$ and $gamma_{os}(mathscr{P}_4(G))=2gamma(G)$ hold, where $gamma(G)$ and $gamma_{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.
The closed cone of flag vectors of Eulerian partially ordered sets is studied. It is completely determined up through rank seven. Half-Eulerian posets are defined. Certain limit posets of Billera and Hetyei are half-Eulerian; they give rise to extrem
As a fundamental research object, the minimum edge dominating set (MEDS) problem is of both theoretical and practical interest. However, determining the size of a MEDS and the number of all MEDSs in a general graph is NP-hard, and it thus makes sense
The $k$-power domination problem is a problem in graph theory, which has applications in many areas. However, it is hard to calculate the exact $k$-power domination number since determining k-power domination number of a generic graph is a NP-complet
Unsupervised learning of visual similarities is of paramount importance to computer vision, particularly due to lacking training data for fine-grained similarities. Deep learning of similarities is often based on relationships between pairs or triple
For a graph $G= (V,E)$, a double Roman dominating function (DRDF) is a function $f : V to {0,1,2,3}$ having the property that if $f (v) = 0$, then vertex $v$ must have at least two neighbors assigned $2$ under $f$ or {at least} one neighbor $u$ with