A locating-dominating set of a graph G is a dominating set C of G such that, for each pair of distinct vertices u and v not in C , the neighborhood of u in C and the neighborhood of v in C are distinct. We study locating-dominating sets of minimum density on the infinite hexagonal grid H k with finite height k. We show optimal solutions for H k , k ≤ 5, and when k is a multiple of 3. We also present an ILP formulation to find periodic locating-dominating sets for H k , which may be solved in reasonable time, when k is not so large. With this approach, we found feasible solutions for k = 7 and k = 8, which are within at most 1.3% of the optimum. Combining these results, we obtain upper bounds for minimum-density locating-dominating sets on H k , for all fixed k ≥ 10, which are within 1% of the optimal solution. For the hexagonal grids, only results for the unrestricted case (unbounded height) have appeared in the literature. Results for H k , k ≥ 2 , presented here have not appeared in the literature.

The 2-Decomposition Conjecture, equivalent to the 3-Decomposition Conjecture stated in 2011 by Hoffmann-Ostenhof, claims that every connected graph G with vertices of degree 2 and 3, and satisfying that G - E(C) is disconnected for every cycle C, admits a decomposition into a spanning tree and a matching. In this work we show that the 2-Decomposition Conjecture holds for graphs whose vertices of degree 3 induce a collection of cacti in which each vertex belongs to a cycle.

We present approximation algorithms for the orthogonal z-oriented three-dimensional packing problem (TPP z ) and analyze their asymptotic performance bound. This problem consists in packing a list of rectangular boxes L=(b 1 ,b 2 ,. . . ,b n ) into a rectangular box B=(l,w,\infty)$, orthogonally and oriented in the z-axis, in such a way that the height of thepacking is minimized. We say that a packing is oriented in the z-axis when the boxes in L are allowed to be rotated (by ninety degrees) around the z-axis. This problem has some nice applications but has been less investigated than the well-known variant of it---denoted by TPP (three-dimensional orthogonal packing problem)---in which rotations of the boxes are not allowed. The problem TPP can be reduced to TPP z . Given an algorithm for TPP z , we can obtain an algorithm for TPP with the same asymptotic bound. We present an algorithm for TPP z , called R, and three other algorithms, called LS, BS, and SS, for special cases of this problem in which the instances are more restricted. The algorithm LS is for the case in which all boxes in L have square bottoms; BS is for the case in which the box B has a square bottom, and SS is for the case in which the box B and all boxes in L have square bottoms. For an algorithm $\wa$, we denote by $r(\wa)$ the asymptotic performance bound of $\wa$. We show that $2.5\leq r(R) < 2.67$, $\ 2.5\leq r(LS)\leq 2.528$,$\ 2.5\leq r(BS)\leq 2.543$, and $\ 2.333\leq r(SS)\leq 2.361$. The algorithms presented here have the same complexity ${\cal O}(n\log n)$ as the other known algorithms for these problems, but they have better asymptotic performance bounds.