## Abstract

Given an undirected edge weighted graph, the graph partitioning problem consists in determining a partition of the node set of the graph into subsets of

prescribed sizes, so as to maximize the sum of the weights of the edges having

both endpoints in the same subset. We introduce a new class of bounds for

this problem relying on the full spectral information of the weighted adjacency

matrix A. The expression of these bounds involves the eigenvalues and particular geometrical parameters defined using the eigenvectors of A. A connection is established between these parameters and the maximum cut problem. We report computational results showing that the new bounds compare favorably with previous bounds in the literature.

prescribed sizes, so as to maximize the sum of the weights of the edges having

both endpoints in the same subset. We introduce a new class of bounds for

this problem relying on the full spectral information of the weighted adjacency

matrix A. The expression of these bounds involves the eigenvalues and particular geometrical parameters defined using the eigenvectors of A. A connection is established between these parameters and the maximum cut problem. We report computational results showing that the new bounds compare favorably with previous bounds in the literature.

Original language | English |
---|---|

Pages (from-to) | 200-210 |

Number of pages | 11 |

Journal | Discrete Applied Mathematics |

Volume | 269 |

Early online date | 25 Jun 2019 |

DOIs | |

Publication status | Published - 30 Sep 2019 |