Abstract

Distance-regular graphs are essentially P-polynomial association schemes. For general graphs, although we cannot expect the existence of such nice structure, we can consider its coherent configuration, which is a generalization of association scheme. In this talk, we show how the coherent configuration relates to the structure of the graph. In particular, we settle an open problem by van Dam and Haemers in 2003 by demonstrating the existence of a reasonable matrix, which corresponds to a particular element in the Bose-Mesner algebra, whose spectrum determines the structure of a random graph.