k -Components, Clusters and Slicings in Graphs
David W. Matula · SIAM Journal on Applied Mathematics · 1972
Utilizing the edge-connectivity of graphs, certain maximally connected subgraphs of a graph termed k-components and clusters are characterized and their interrelations are investigated. The cohesiveness function is described and shown to be a useful measure of the local intensity of connectivity within a graph. Sequences of cuts totally separating a graph, termed slicings, are shown to be intimately related to the k-components and clusters of a graph. An efficient algorithm is presented for determining k-components and clusters. Applications of these notions to graph coloring and numerical taxonomy are discussed.