  The sensitivity conjecture which claims that the sensitivity complexity is
polynomially related to block sensitivity complexity, is one of the most
important and challenging problem in decision tree complexity theory. Despite
of a lot of efforts, the best known upper bound of block sensitivity, as well
as the certificate complexity, are still exponential in terms of sensitivity:
$bs(f)\leq C(f)\leq\max\{2^{s(f)-1}(s(f)-\frac{1}{3}),s(f)\}$. In this paper,
we give a better upper bound of $bs(f)\leq C(f)\leq(\frac{8}{9} +
o(1))s(f)2^{s(f) - 1}$. The proof is based on a deep investigation on the
structure of the sensitivity graph. We also provide a tighter relationship
between $C_0(f)$ and $s_0(f)$ for functions with $s_1(f)=2$.
