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
Zehui Shao, Aleksander Vesel · IET Communications · 2013
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 1 , k 2 , … , k n with k 1 > k 2 >⋯> k n an L ( k 1 , k 2 , … , 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 , k 2 ,…, k n ‐number of G is the minimum span over all L ( k 1 , k 2 , … , k n )‐labellings of G . In this study, an integer linear programming model and a satisfiability test reduction for an L ( k 1 , k 2 , … , 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.