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

• Autorzy: Pavlíková S. , Ševčovič D.

Warianty tytułu

PL

Maksymalizacja przerwy widmowej dla grafów chemicznych poprzez rozwiązanie zadania mieszanego całkowitoliczbowego-pólokreślonego programowania

• Języki publikacji: EN

Abstrakty

EN

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.

PL

W pracy analizowano przerwę widmową ważonego grafu, która jest różnicą pomiędzy najmniejszą dodatnią i największą ujemną wartością własną macierzy sąsiedztwa. Taki graf może reprezentować np. chemiczne molekuły organiczne. Głównym zadaniem pracy było skonstruowanie nowego grafu połączeniem poprzez mosty dwóch znanych ważonych grafów tworząc graf dwudzielny. Celem była maksymalizacja szerokości przerwy widmowej względem grafu łączącego. Skonstruowany został mieszany całkowitoliczbowy-półokreślony program dla maksymalizacji przerwy widmowej, która została obliczona numerycznie.

Słowa kluczowe

EN

chemical molecular graphs; invertible graph; HOMO-LUMO spectral gap; Bridged graph; Schur complement; mixed integer semidefinite programming

• Wydawca: Wydawnictwa AGH
• Czasopismo: Computer Methods in Materials Science
• Rocznik: 2016
• Tom: Vol. 16, No. 4
• Strony: 169--176
• Opis fizyczny: Bibliogr. 21 poz., rys.

Twórcy

autor

Pavlíková S.

• FCFT, Slovak Technical University, 812 37 Bratislava, Slovakia
• FMFI, Comenius University, 842 48 Bratislava, Slovakia

autor

Ševčovič D.

• FCFT, Slovak Technical University, 812 37 Bratislava, Slovakia
• FMFI, Comenius University, 842 48 Bratislava, Slovakia

Bibliografia

• Aihara, J.I., 1999a, Reduced HOMO-LUMO Gap as an Index of Kinetic Stability for Polycyclic Aromatic Hydrocarbons, J. Phys. Chem. A, 103, 7487-7495.
• Aihara, J.I., 1999b, Weighted HOMO-LUMO energy separation as an index of kinetic stability for fullerenes, Theor. Chem. Acta, 102, 134-138.
• Bacalis, N.C. & Zdetsis, A.D., 2009, Properties of hydrogen terminated silicon nanocrystals via a transferable tight-binding Hamiltonian, based on ab-initio results, J. Math. Chem., 46, 962-970.
• Boyd, S. & Vandenberghe, L., 2004, Convex Optimization, Cambridge University 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 some interconnections between combinatorial optimization and extremal graph theory, Yugoslav Journal of Operations Research, 14, 147-154.
• Fowler, P.W., Hansen, P., Caporosi, G., Soncini, A., 2001, Polyenes with maximum HOMOLUMO gap, Chemical Physics Letters, 342, 105-112.
• Fowler, P.V. & Pisański,T., 2010, HOMO-LUMO Maps for Chemical 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 TopologicaI Formula for the HOMOLUMO Separation in Alternant Hydrocarboons, Chemical-Physic Letters, 62, 384-388.
• Hückel, E., 1931, Quantentheoretische Beiträge zum Benzolproblem. Zeitschrift für Physik, 70, 204-286.
• Löfberg, L., 2004, A toolbox for modeling and optimization in MATLAB. 2004 IEEE international symposium on computer 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., 2016, A note on inverses of labeled graphs. to appear in: Australasian Journal on Combinatorics. s
• Pavlíková, S. & Ševčovič, D. 2016a, On a Construction of Integrally Invertible Graphs and their Spectral Properties, submitted.
• Pavlíková, S. & Ševčovič, D., 2016b, On Construction of Upper and Lower Bounds for the HOMO-LUMO Spectral Gap by Means of Semidefinite Relaxation Techniques, submitted.
• Streitwieser, A., 1961, Molecular orbital theory for organic chemists, John Willey & Sons, New York-London.
• Ševčovič, D. & Trnovská, M., 2015, Solution to the inverse Wulff problem by means of the enhanced semidefinite relaxation method, Journal of Inverse and III-posed Problems, 23, 263-285.
• Sturm, J.F., 1999, Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones, Optimization Methods and Software, 11, 625-653.
• Zhang, F. & An, C., 1999, Acyclic molecules with greatest HOMO-LUMO separation, Discrete Applied Mathematics, 98, 165-171.

Uwagi

PL

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).