Let G=(V, E) be a connected finite graph and let M_{\alpha, G} be the fractional Hardy-Littlewood maximal operator on the graph G. In this talk, we shall introduce some results on sharp constants for M_{\alpha, G} on Lebesgue spaces when G is the complete graph or the star graph.