Eigenvalues and partitionings of the edges of a graph

Abstract

This paper is concerned with the relationship between geometric properties of a graph and the spectrum of its adjacency matrix. For a given graph G, let α(G) be the smallest partition of the set of edges such that each corresponding subgraph is a clique, β(G) the smallest partition such that each corresponding graph is a complete multipartite graph, and γ(G) the smallest partition such that each corresponding subgraph is a complete bipartite graph. Lower bounds for α, β, γ are given in terms of the spectrum of the adjacency matrix of G. Despite these bounds, it is shown that there can exist two graphs, G1 and G2, with identical spectra such that α(G1) is small, α(G2) is enormous. A similar phenomenon holds for β(G). By contrast, γ(G) is essentially relevant to the spectrum of G, for it is shown that γ(G) is bounded by and bounds a function of the number of eigenvalues each of which is at most - 1. It is also shown that the chromatic number χ(G) is spectrally irrelevant in the sense of the results for α and β described above. © 1972.