Volume 185, Issue 3

1. Perfect domination, Roman domination and perfect Roman domination in lexicographic product graphs

A. Cabrera Martinez ; C. Garcia-Gomez ; J. A. Rodriguez-Velazquez.
The aim of this paper is to obtain closed formulas for the perfect dominationnumber, the Roman domination number and the perfect Roman domination number oflexicographic product graphs. We show that these formulas can be obtainedrelatively easily for the case of the first two parameters. The picture isquite different when it concerns the perfect Roman domination number. In thiscase, we obtain general bounds and then we give sufficient and/or necessaryconditions for the bounds to be achieved. We also discuss the case of perfectRoman graphs and we characterize the lexicographic product graphs where theperfect Roman domination number equals the Roman domination number.

2. Coxeter invariants for non-negative unit forms of Dynkin type A

Jesús Arturo Jiménez González.
Two integral quadratic unit forms are called strongly Gram congruent if theirupper triangular Gram matrices are Z-congruent. The paper gives a combinatorialstrong Gram invariant for those unit forms that are non-negative of Dynkin typeA, 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.

3. Nominal Unification and Matching of Higher Order Expressions with Recursive Let

Manfred Schmidt-Schauß ; Temur Kutsia ; Jordi Levy ; Mateu Villaret ; Yunus Kutz.
A sound and complete algorithm for nominal unification of higher-orderexpressions with a recursive let is described, and shown to run innondeterministic polynomial time. We also explore specializations like nominalletrec-matching for expressions, for DAGs, and for garbage-free expressions anddetermine their complexity. We also provide a nominal unification algorithm forhigher-order expressions with recursive let and atom-variables, where we showthat it also runs in nondeterministic polynomial time. In addition we provethat there is a guessing strategy for nominal unification with letrec andatom-variable that is a trade-off between exponential growth andnon-determinism. Nominal matching with variables representing partialletrec-environments is also shown to be in NP.