“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
Paper IPM / M / 16339  


Abstract:  
Properties of graphs that can be characterized by the spectrum of the adjacency matrix of the graph have been studied systematically recently. Motivated by the complexity of these properties, we show that there are such properties for which testing whether a graph has that property can be NPhard (or belong to other computational complexity classes consisting of even harder problems). In addition, we discuss a possible spectral characterization of some wellknown NPhard properties. In particular, for every integer we construct a pair of regular cospectral graphs, where one graph is Hamiltonian and the other one not.
Download TeX format 

back to top 