  Let $G=(V,E)$ be a finite graph and $M_G$ be the centered Hardy-Littlewood
maximal operator defined there. We find the optimal value $\bf{C}_{G,p}$ such
that the inequality $$\text{Var}_{p}(M_{G}f)\leq
{\textbf{C}}_{G,p}\text{Var}_{p}(f)$$ holds for every $f:V\to \mathbb{R},$
where $\text{Var}_p$ stands for the $p$-variation, when: (i) $G=K_n$ (complete
graph) and $p\in [\frac{\log(4)}{\log(6)},\infty)$ or $G=K_4$ and $p\in
(0,\infty)$; (ii) $G=S_n$ (star graph) and $1\ge p\ge \frac{1}{2}$; $p\in
(0,\frac{1}{2})$ and $n\ge C(p)$ or $G=S_3$ and $p\in (1,\infty).$ We also find
the value of the norm $\|M_{G}\|_{2}$ when: (i) $G=K_n$ and $n\ge 3$; (ii)
$G=S_n$ and $n\ge 3.$
