Lollipop graphs and their partitions based on Laplacian matrices

Abstract

The lollipop graph ???? ,defined in this paper is the coalescence of a complete graph ?? and a path ?? with a pendent vertex. Lollipop graph defined as a coalescence of a cycle and a path is already studied from the view point of their spectrum and their cospectral properties [1]. However, among various connected, finite graphs, we are interested in partitioning techniques. Spectral clustering methods use eigenvalues and eigenvectors of associated matrices of graphs, where Laplacian matrices play a vital role in finding clusters. There are some other non-deterministic polynomial-time hard techniques to find clusters in a graph. Minimum normalized cut is the one, which is widely used in image segmentation. But there are some differences between the partitions generated by these techniques. We are interested in finding graphs, which perform poorly on spectral clustering methods. The lollipop graph is one of the counter example graphs.