Trace formulas for d-regular graphs are derived and used to express the spectral density in terms of the periodic walks on the graphs under consideration. The trace formulas depend on a parameter (w) which can be tuned continuously to assign different weights to different periodic orbit contributions. At the special value w = 1, the only periodic orbits which contribute are the non back-scattering orbits, and the smooth part in the trace formula coincides with the Kesten-McKay expression. As (w) deviates from unity, non vanishing weights are assigned to the periodic walks with back-scatter, and the smooth part is modified in a consistent way. The trace formulas presented in this talk can be used as tools for showing the connection between the spectral properties of d-regular graphs and the theory of random matrices.