New methods for maximizing the smallest eigenvalue of the grounded Laplacian matrix

Anaqreh, Ahmad T. and G.-Tóth, Boglárka and Vinkó, Tamás (2024) New methods for maximizing the smallest eigenvalue of the grounded Laplacian matrix. ANNALES MATHEMATICAE ET INFORMATICAE, 60. pp. 10-18. ISSN 1787-6117

Preview

Text AMI_60_from10to18.pdf - Published Version Download (813kB) | Preview

Abstract

Maximizing the smallest eigenvalue of the grounded Laplacian matrix is an NP-hard problem that involves identifying the Laplacian matrix’s (n − k) × (n − k) principal submatrix obtained after removing k rows and corresponding columns. The challenge is to determine optimally the rows and columns to be deleted. Our proposed approach, motivated by the Gershgorin circle theorem, is used together with the degree centrality of the corresponding graph. Moreover, integer linear programming for the vertex cover problem has been employed as an additional method of solving the problem. The efficiency of the methods is demonstrated on real-world graphs.

Actions (login required)

Edit Item