On construction of upper and lower bounds for the HOMO-LUMO spectral gap

DOI10.3934/NACO.2019005zbMATH Open1419.05133arXiv1806.00870OpenAlexW2805990982WikidataQ128961841 ScholiaQ128961841MaRDI QIDQ2273100FDOQ2273100

Authors: S. Pavlíková, Daniel Ševčovič 

Publication date: 18 September 2019

Published in: Numerical Algebra, Control and Optimization (Search for Journal in Brave)

Abstract: In this paper we study spectral properties of graphs which are constructed from two given invertible graphs by bridging them over a bipartite graph. We analyze the so-called HOMO-LUMO spectral gap which is the difference between the smallest positive and largest negative eigenvalue of the adjacency matrix of a graph. We investigate its dependence on the bridging bipartite graph and we construct a mixed integer semidefinite program for maximization of the HOMO-LUMO gap with respect to the bridging bipartite graph. We also derive upper and lower bounds for the optimal HOMO-LUMO spectral graph by means of semidefinite relaxation techniques. Several computational examples are also presented in this paper.

Full work available at URL: https://arxiv.org/abs/1806.00870

Recommendations

• A spectral gap estimate and applications
• scientific article; zbMATH DE number 1961223
• Spectral gap for complete graphs: upper and lower estimates
• scientific article; zbMATH DE number 2133155
• scientific article; zbMATH DE number 1098540
• Spectral gap bounds for the simplicial Laplacian and an application to random complexes
• scientific article; zbMATH DE number 5217628
• Lifts, discrepancy and nearly optimal spectral gap
• ON SPECTRAL BOUNDEDNESS
• L p -Spectral Gap and Gromov-Hausdorff Convergence

zbMATH Keywords

bridged graphSchur complementspectral estimatesinvertible graphHOMO-LUMO spectral gapmixed integer semidefinite programming

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Semidefinite programming (90C22) Theory of matrix inversion and generalized inverses (15A09) Mixed integer programming (90C11) Matrices of integers (15B36)

Cites Work

• Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
• Title not available (Why is that?)
• Title not available (Why is that?)
• Spectra of graphs
• A Lagrangian-DNN relaxation: a fast method for computing tight lower bounds for a class of quadratic optimization problems
• Inverses of trees
• Acyclic molecules with greatest HOMO-LUMO separation
• Median eigenvalues and the HOMO-LUMO index of graphs
• HL-index of a graph
• HOMO-LUMO maps for chemical graphs
• Median eigenvalues of bipartite planar graphs
• Note on the HOMO-LUMO index of graphs
• On the inverse and the dual index of a tree
• Title not available (Why is that?)
• Ordering graphs with small index and its application
• Extremal values of matching energies of one class of graphs
• A note on inverses of labeled graphs
• On some interconnections between combinatorial optimization and extremal graph theory
• Properties of hydrogen terminated silicon nanocrystals via a transferable tight-binding Hamiltonian, based on ab-initio results
• Nonlinear programming, theory and algorithms
• On a construction of integrally invertible graphs and their spectral properties
• Solution to the inverse Wulff problem by means of the enhanced semidefinite relaxation method

Cited In (6)

• On the Moore-Penrose pseudo-inversion of block symmetric matrices and its application in the graph theory
• Lifts, discrepancy and nearly optimal spectral gap
• Refined decay bounds on the entries of spectral projectors associated with sparse Hermitian matrices
• On HOMO-LUMO separation of acyclic molecules
• A model for HOMO-LUMO gap and maximum-weight matching
• HOMO-LUMO maps for chemical graphs

Uses Software

• SeDuMi

This page was built for publication: On construction of upper and lower bounds for the HOMO-LUMO spectral gap

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2273100)