Roach type of graphs and the characteristics of their partitioning

Abstract

The goal of the graph partitioning problem is to find groups such that entities within the same group are similar and different groups are dissimilar. Spectral clustering methods use eigenvalues and eigenvectors of matrices associated with graphs and are widely used in graph-partitioning problems. In this presentation, results concerning spectral clustering properties of roach type of graphs ( and are the number of vertices in the upper and lower paths of the graph) will be presented. The concrete formula for the minimum normalized cut of has already been presented, (Perera & Mizoguchi, 2013). The normalized cut is used to minimize the disassociation between partitions of graphs and maximize the association within partitions. Here we find the characteristic polynomials for the normalized Laplacian matrix of weighted path and roach type of graphs using Chebyshev polynomials and properties of tridiagonal matrices. Subsequently, we find conditions for and , based on which spectral methods perform poorly compared with the minimum normalized cut.