  We propose the total staggered quantum walk model and the total tessellation
cover of a graph. This model uses the concept of total tessellation cover to
describe the motion of the walker who is allowed to hop both to vertices and
edges of the graph, in contrast with previous models in which the walker hops
either to vertices or edges. We establish bounds on $T_t(G)$, which is the
smallest number of tessellations required in a total tessellation cover of $G$.
We highlight two of these lower bounds $T_t(G) \geq \omega(G)$ and $T_t(G)\geq
is(G)+1$, where $\omega(G)$ is the size of a maximum clique and $is(G)$ is the
number of edges of a maximum induced star subgraph. Using these bounds, we
define the good total tessellable graphs with either $T_t(G)=\omega(G)$ or
$T_t(G)=is(G)+1$. The $k$-total tessellability problem aims to decide whether a
given graph $G$ has $T_t(G) \leq k$. We show that $k$-total tessellability is
in $\mathcal{P}$ for good total tessellable graphs. We establish the
$\mathcal{NP}$-completeness of the following problems when restricted to the
following classes: ($is(G)+1$)-total tessellability for graphs with $\omega(G)
= 2$; $\omega(G)$-total tessellability for graphs $G$ with $is(G)+1 = 3$;
$k$-total tessellability for graphs $G$ with $\max\{\omega(G), is(G)+1\}$ far
from $k$; and $4$-total tessellability for graphs $G$ with $\omega(G) = is(G)+1
= 4$. As a consequence, we establish hardness results for bipartite graphs,
line graphs of triangle-free graphs, universal graphs, planar graphs, and
$(2,1)$-chordal graphs.
