Harmonic graphs with small number of cycles Original Research Article

Let G be a graph on n vertices v1,v2,…,vn and let d(vi) be the degree (= number of first neighbors) of the vertex vi. If (d(v1),d(v2),…,d(vn))t is an eigenvector of the (0,1)-adjacency matrix of G, then G is said to be harmonic. Earlier all harmonic trees were determined; their number is infinite. We now show that for any c, c>1, the number of connected harmonic graphs with cyclomatic number c is finite. In particular, there are no connected non-regular unicyclic and bicyclic harmonic graphs and there exist exactly four and eighteen connected non-regular tricyclic and tetracyclic harmonic graphs.