  The trapping problem on graph (or network) as a typical focus of great
interest has attracted more attention from various science fields, including
applied mathematics and theoretical computer science, in the past. Here, we
first study this problem on an arbitrary graph and obtain the closed-form
formula for calculating the theoretical lower bound of average trapping time
($ATT$), a quantity that evaluates trapping efficiency of graph in question,
using methods from spectral graph theory. The results show that the choice of
the trap's location has a significant influence on determining parameter $ATT$.
As a result, we consider the problem on star-type graphs, a special graph
family which will be introduced shortly, with a single trap $\theta$ and then
derive using probability generating functions the exact solution to quantity
$ATT$. Our results suggest that all star-type graphs have most optimal trapping
efficiency by achieving the corresponding theoretical lower bounds of $ATT$.
More importantly, we further find that a given graph is most optimal only if
its underlying structure is star-type when considering the trapping problem. At
meantime, we also provide the upper bounds for $ATT$ of several graphs in terms
of well-known Holder inequality, some of which are sharp. By using all the
consequences obtained, one may be able to design better control scheme for
complex networks from respect of trapping efficiency, to some extent, which are
in well agreement with many other previous thoughts.
