Longest sequence of dominoes
Your problem is NP-hard. Consider an instance of Hamiltonian path graph $G=(V,E)$ in which the degree of each vertex is at most $3$ and we are given a starting vertex $s$ and ending vertex $t$ both of degree at most $2$ (the problem remains hard in this case).
W.l.o.g., let $V=\{3,\dots,k-4\}$, $s=3$, and $t=k-4$.
Create the dominoes $(0,1)$, $(1,2)$, $(2,3)$, $(k-4, k-3)$, $(k-3, k-2)$, and $(k-2, k-1)$. Create one &quot;edge&quot; domino $(a,b)$ for each edge $(a,b) \in E$.
There exists an Hamiltonian path in $G$ if and only if there is a sequence of $k-1$ dominoes.
Indeed, notice that any sequence of dominoes that only uses the dominoes from $E$ traces a (not-necessarily simple) path $P$ in $G$.
But then, all vertices except the endpoints of $P$ must be traversed at most once (since their degree is at most $3$). The two endpoints can extend the path by at most $2$. Then the number of edges of $P$ can be at most $|V|+1 = k-6+1 = k-5$. This implies that a sequence of $k-1$ dominoes must use all &quot;non-edge&quot; dominoes, i.e., the sequence of dominoes must start with $(0,1), \dots, (2,3)$ and end with $(k-4, k-4), \dots, (k-2, k-1)$.
Then, the path induced by the sub-sequence obtained by dropping the &quot;non-edge&quot; dominoes must be simple and traverses $k-1-6 = k-7 = |V|-1$ edges of $G$, i.e., it is an Hamiltonian path in $G$.
Conversely, we can create a sequence of $\ell+6$ dominoes from any simple path of length $\ell$ from $s$ to $t$ in $G$ (simply prepend $(0,1), \dots, (2,3)$ and append  $(k-4, k-4), \dots, (k-2, k-1)$). For an Hamiltoniam path we have $\ell=|V|-1=k-7$, therefore the sequence has length $k-1$.