Maximization of the Spectral Gap for Chemical Graphs by means of a Solution to a Mixed Integer Semidefinite Program

by

Maximization of the Spectral Gap for Chemical Graphs by means of a Solution to a Mixed Integer Semidefinite Program

Soňa  Pavlíková, Daniel Ševčovič

FCFT, Slovak University of Technology, 812 37 Bratislava, Slovakia, and FMFI, Comenius University, 842 48 Bratislava, Slovakia.

DOI:

https://doi.org/10.7494/cmms.2016.4.0586

Abstract:

In this paper we analyze the spectral gap of a weighted graph which is the difference between the smallest positive and largest negative eigenvalue of its adjacency matrix. Such a graph can represent e.g. a chemical organic molecule. Given two weighted graphs, our goal is to construct a new graph by bridging them over a bipartite graph.  The aim is to maximize the spectral gap with respect to a bridging graph. To this end, we construct a mixed integer semidefinite program for maximization of the spectral gap and compute it numerically.

Cite as:

Pavlíková, S., Ševčovič, D. (2016). Maximization of the Spectral Gap for Chemical Graphs by means of a Solution to a Mixed Integer Semidefinite Program. Computer Methods in Materials Science, 16(4), 169 – 176. https://doi.org/10.7494/cmms.2016.4.0586

Article (PDF):

Keywords:

Chemical molecular graphs, Invertible graph, HOMO-LUMO spectral gap, Bridged graph, Schur complement, Mixed integer semidefinite programming

References:

Aihara, J.I., 1999a, Reduced HOMO-LUMO Gap as an Index ofKinetic Stability for Polycyclic Aromatic Hydrocarbons,J. Phys. Chem. A, 103, 7487-7495.

Aihara, J.I., 1999b, Weighted HOMO-LUMO energy separationas an index of kinetic stability for fullerenes, Theor.Chem. Acta, 102, 134-138.

Bacalis, N.C., Zdetsis, A.D., 2009, Properties of hydrogen terminatedsilicon nanocrystals via a transferable tightbindingHamiltonian, based on ab-initio results, J. Math.Chem., 46, 962-970.

Boyd, S., Vandenberghe, L., 2004, Convex Optimization, CambridgeUniversity Press New York, NY, USA.

Brouwer, A.E., Haemers, W.H., 2012, Spectra of graphs,Springer New York, Dordrecht, Heidelberg, London.

Cvetković, D., Doob, M., Sachs, H., 1980, Spectra of graphs -Theory and application. Academic Press, New York.

Cvetković, D., Hansen, P., Kovačevič-Vučič, V., 2004, On someinterconnections between combinatorial optimizationand extremal graph theory, Yugoslav Journal of OperationsResearch, 14, 147-154.

Fowler, P.W., Hansen, P., Caporosi, G., Soncini, A., 2001,Polyenes with maximum HOMO-LUMO gap, ChemicalPhysics Letters, 342, 105-112.

Fowler, P.V., Pisański, T., 2010, HOMO-LUMO Maps forChemical Graphs, MATCH Commun. Math. Comput.Chem., 64, 373-390.

Godsil, C.D., 1985, Inverses of Trees, Combinatorica, 5, 33-39.

Gutman, I., Rouvray, D.H., 1979, An Aproximate TopologicaIFormula for the HOMO-LUMO Separation in AlternantHydrocarboons, Chemical-Physic Letters, 62, 384-388.

Hückel, E., 1931, Quantentheoretische Beiträge zumBenzolproblem. Zeitschrift für Physik, 70, 204-286.

Löfberg, L., 2004, A toolbox for modeling and optimization inMATLAB. 2004 IEEE international symposium oncomputer aided control systems design (CACSD 2004),September 2-4, 2004, Taipei, 284-289.

Hamala, M., Trnovská, M., 2013, Nonlinear Programming,Theory and Algorithms (in Slovak: Nelineárne programovanie,teória a algoritmy), Epos, Bratislava.

Pavlíková, S., 2017, A note on inverses of labeled graphs. AustralasianJournal on Combinatorics. 67(2), 222-234 (inPress).Pavlíková, S., Ševčovič, D. 2016a, On a Construction of IntegrallyInvertible Graphs and their Spectral Properties,submitted.

Pavlíková, S., Ševčovič, D., 2016b, On Construction of Upperand Lower Bounds for the HOMO-LUMO Spectral Gapby Means of Semidefinite Relaxation Techniques, submitted.Streitwieser, A., 1961, Molecular orbital theory for organicchemists, John Willey & Sons, New York-London.

Ševčovič, D., Trnovská, M., 2015, Solution to the inverse Wulffproblem by means of the enhanced semidefinite relaxationmethod, Journal of Inverse and III-posed Problems,23, 263-285.

Sturm, J.F., 1999, Using SeDuMi 1.02, A Matlab toolbox foroptimization over symmetric cones, Optimization Methodsand Software, 11, 625-653.

Zhang, F., An, C., 1999, Acyclic molecules with greatestHOMO-LUMO separation, Discrete Applied Mathematics,98, 165-171.