  Graphs with large spectral gap are important in various fields such as
biology, sociology and computer science. In designing such graphs, an important
question is how the probability of graphs with large spectral gap behaves. A
method based on multicanonical Monte Carlo is introduced to quantify the
behavior of this probability, which enables us to calculate extreme tails of
the distribution. The proposed method is successfully applied to random
3-regular graphs and large deviation probability is estimated.
