The aim of this paper is to obtain closed formulas for the perfect domination
number, the Roman domination number and the perfect Roman domination number of
lexicographic product graphs. We show that these formulas can be obtained
relatively easily for the case of the first two parameters. The picture is
quite different when it concerns the perfect Roman domination number. In this
case, we obtain general bounds and then we give sufficient and/or necessary
conditions for the bounds to be achieved. We also discuss the case of perfect
Roman graphs and we characterize the lexicographic product graphs where the
perfect Roman domination number equals the Roman domination number.
Two integral quadratic unit forms are called strongly Gram congruent if their
upper triangular Gram matrices are Z-congruent. The paper gives a combinatorial
strong Gram invariant for those unit forms that are non-negative of Dynkin type
A, within the framework introduced in [Fundamenta Informaticae 184(1):49-82,
2021], and uses it to determine all corresponding Coxeter polynomials and
(reduced) Coxeter numbers.
A sound and complete algorithm for nominal unification of higher-order
expressions with a recursive let is described, and shown to run in
nondeterministic polynomial time. We also explore specializations like nominal
letrec-matching for expressions, for DAGs, and for garbage-free expressions and
determine their complexity. We also provide a nominal unification algorithm for
higher-order expressions with recursive let and atom-variables, where we show
that it also runs in nondeterministic polynomial time. In addition we prove
that there is a guessing strategy for nominal unification with letrec and
atom-variable that is a trade-off between exponential growth and
non-determinism. Nominal matching with variables representing partial
letrec-environments is also shown to be in NP.