Integer linear programming model and satisfiability test reduction for distance constrained labellings of graphs: the case of L(3,2,1)labelling for products of paths and cycles

Let u and v be vertices of a graph G = (V, E) and d(u, v) be the distance between u and v in G. For positive integers k₁, k₂, ..., k_n with $k_1 gt k_2 gt cdots gt k_n $k₁>k₂>⋯>k_n an L(k₁, k₂, ..., k_n)-labelling of G is a function f: V(G)→{0, 1, ...} such that for every u, v ∈ V(G) and for all 1 ≤ i ≤ n, |f(u)- f(v)| ≥ k_i if d(u, v) = i. The span of f is the difference between the largest and the smallest numbers in f(V(G)). The $lambda _{k_1 comma k_2 comma ldots comma k_n } $λk₁,k₂,...,k_n-number of G is the minimum span over all L(k₁, k₂, ..., k_n)-labellings of G. In this study, an integer linear programming model and a satisfiability test reduction for an L(k₁, k₂, ..., k_n)-labelling are proposed. Both approaches are used for studying the λ_3,2,1-numbers of strong, Cartesian and direct products of paths and cycles.