Let $G{m}_{n}$ be a simple, connected and finite graph. Suppose $\phi: \mathbb{N}\to \mathbb{R^{+}}$ is a positive and increasing function. We consider the action of generalized maximal operator $M^{\phi}_{G^{m}_{n}}$ on $\ell^{p}$ spaces and find optimal bound for the quasi norm $\|M^{\phi}_{G^{m}_{n}}\|_{p}$ for the case $0<p\leq 1$. In addition we find bounds for the norm $\|M^{\phi}_{G^{m}_{n}}\|_{p}$ for the case $1<p<\infty$. We also prove some general results for $0<p\leq 1$.