About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Linear Algebra and Its Applications
Paper
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.