DOIAbstract
AbstractWe would like to classify the vertices of a hypergraph in the way that ‘similar’ vertices (those having many incident edges in common) belong to the same cluster. The problem is formulated as follows: given a connected hypergraph on n vertices and fixing the integer k(1<k⩽n), we are looking for k-partition of the set of vertices such that the edges of the corresponding cut-set be as few as possible. We introduce some combinatorial measures characterizing this structural property and give upper and lower bounds for them by means of the k smallest eigenvalues of the hypergraph. For this purpose the notion of spectra of hypergraphs — which is the generalization of C-spectra of graphs — is also introduced together with k-dimensional Euc...
Add to ORKG