Best constants for the Hardy-Littlewood maximal operator on finite graphs

We study the behavior of averages for functions defined on finite graphs $G$, in terms of the Hardy-Littlewood maximal operator $M_G$. We explore the relationship between the geometry of a graph and its maximal operator and prove that $M_G$ completely determines $G$ (even though embedding properties for the graphs do not imply pointwise inequalities for the maximal operators). Optimal bounds for the $p$-(quasi)norm of a general graph $G$ in the range $0<p\le 1$ are given, and it is shown that the complete graph $K_n$ and the star graph $S_n$ are the extremal graphs attaining, respectively, the lower and upper estimates. Finally, we study weak-type estimates and some connections with the dilation and overlapping indices of a graph.