K-WAY GRAPH PARTITIONING

Abstract

A partition on a graph with small number of vertices and edges does not require any complex procedure. Technically, one can find such graph partition by using the eigenvalues of Laplacian matrices given by such graph. The eigenvector corresponding to the second smallest eigenvalue is then used to find the sign of our eigenvector. Later on, these eigenvector is called the Fiedler vector. Furthermore for k-partition graph, we enlarge the concept by finding the third, fourth or bigger eigenvector to obtain three, four or more partitions but in fact there is always used only the second eigenvector.