  For a random walk on a network, the mean first-passage time from a node $i$
to another node $j$ chosen stochastically according to the equilibrium
distribution of Markov chain representing the random walk is called Kemeny
constant, which is closely related to the navigability on the network. Thus,
the configuration of a network that provides optimal or suboptimal navigation
efficiency is a question of interest. It has been proved that complete graphs
have the exact minimum Kemeny constant over all graphs. In this paper, by using
another method we first prove that complete graphs are the optimal networks
with a minimum Kemeny constant, which grows linearly with the network size.
Then, we study the Kemeny constant of a class of sparse networks that exhibit
remarkable scale-free and fractal features as observed in many real-life
networks, which cannot be described by complete graphs. To this end, we
determine the closed-form solutions to all eigenvalues and their degeneracies
of the networks. Employing these eigenvalues, we derive the exact solution to
the Kemeny constant, which also behaves linearly with the network size for some
particular cases of networks. We further use the eigenvalue spectra to
determine the number of spanning trees in the networks under consideration,
which is in complete agreement with previously reported results. Our work
demonstrates that scale-free and fractal properties are favorable for efficient
navigation, which could be considered when designing networks with high
navigation efficiency.
