Advanced Search
Article Contents
Article Contents

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

• * Corresponding author: Daniel Ševčovič

The authors were supported by VEGA grants 1/0142/17(S.P.) and 1/0062/18(D.Š.)

• 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.

Mathematics Subject Classification: Primary: 05C50, 15A09, 15B36; Secondary: 90C11, 90C22.

 Citation:

• Figure 1.  A bridged graph $G_C = {\mathcal B}_K(G_A, G_B)$ through a bipartite graph $G_K$.

Figure 2.  Simple graphs $G_A$ and $G_B$ (left) and the bridged graph $G_C$ with the maximal HOMO-LUMO spectral gap which can be constructed by bridging $G_A$ and $G_B$ over the vertex 1 of $G_B$ ($k_B = 1$) to the vertices of $G_A$ (right).

Figure 3.  An example of an invertible graph $F_0$ (left) representing the chemical organic molecule of fulvene (right).

Figure 4.  Results of optimal bridging of the fulvene graph GB= F0 through the vertices {1,2} to GA=F0 a);through the vertices {1,4} to GA=F0 b);and through the vertices {1,2} to GA=F1 c).

Figure 5.  Results of optimal bridging of the graph $G_B = P_4$ through the vertices $\{1, 3\}$ to $G_A = P_6$ a); through the vertices $\{2, 3\}$ to $G_A = P_6$ b); and through the vertex $\{2\}$ to $G_A = T_4$ c).

Figure 6.  Results of optimal bridging of the graph $G_B = P_4$ through the vertices $\{1, 3\}$ to $G_A = P_6$ a); through the vertices $\{2, 3\}$ to $G_A = P_6$ b); and through the vertex $\{2\}$ to $G_A = T_4$ c); with the constraint of maximal degree equal to 3.

Table 1.  A sample Matlab code for computing mixed integer semidefinite programming problem (12). The output of the program is the optimal value $\Lambda^{opt}_{HL}(G_A, G_B) = \overline{\Lambda}^{sir}_{HL}(G_A, G_B)$.

 mu=sdpvar(1); eta=sdpvar(1); W=intvar(m, m); K=binvar(n, m); ops=sdpsettings('solver', 'bnb', 'bnb.maxiter', bnbmaxiter); Fconstraints=[... [[W, K']; [K, eye(n, n)] ]>=0, ... mu>=0, eta>=0, ... [[eye(n, n)-mu*inv(A), K*inv(B)]; [inv(B)*K', eye(m, m)-mu*inv(B) + inv(B)*W*inv(B)] ] >= 0, ... [[eye(n, n) + eta*inv(A), K*inv(B)]; [inv(B)*K', eye(m, m) + eta*inv(B) + inv(B)*W*inv(B)] ] >= 0, ... sum(K(:, :))==diag(W)', sum(K(:))>=1, ... vec(W(:))>=0, 0 < =vec(K(:)) < =1, ... sum([[A, K]; [K', B]]) < =maxdegree*ones(1, n+m), ..., K*[zeros(kB, m-kB); eye(m-kB, m-kB)] == zeros(n, m-kB), ... ]; solvesdp(Fconstraints, -mu-eta, ops) LambdaSIR = double(mu + eta)

Table 2.  The computational results and comparison of various semidefinite relaxations. The first two columns describe the graph $G_A$ and $G_B$ with the chosen set of bridging vertices. The optimal value $\Lambda_{HL}^{opt} = \overline{\Lambda}_{HL}^{sir}$ is shown in bold in the middle column. The upper $\overline{\Lambda}_{HL}^{sdp}$ and lower bounds $\underline{\Lambda}_{HL}^{sdp}$, $\underline{\Lambda}_{HL}^{sir}$ are also presented together with computational times in seconds computed on Quad core Intel 1.5GHz CPU with 4 GB of memory.

 $G_A$ $G_B$ $\underline{\Lambda}_{HL}^{sdp}$ $\underline{\Lambda}_{HL}^{sir}$ $\Lambda _{HL}^{opt}$=$\bar \Lambda _{HL}^{sir}$ $\overline{\Lambda}_{HL}^{sdp}$ $G_B \mapsto G_A$ $F_0$ $F_0$ $0.233688$ $0.531664$ $\bf 0.74947$ $0.87214$ $1\mapsto 3, 5;\ \ 2\mapsto 6$ $(1, 2)$ $(0.27s)$ $(3.38s)$ $(83s)$ $(2.2s)$ $F_0$ $F_0$ $0.333126$ $0.72678$ $\bf 0.85828$ $0.87214$ $1\mapsto \emptyset;\ \ 4\mapsto 3, 5, 6$ $(1, 4)$ $(0.31s)$ $(4.75s)$ $(36s)$ $(2.2s)$ $F_0$ $F_0$ $0.333126$ $0.719668$ $\bf 0.81389$ $0.87214$ $1\mapsto 4;\ \ 3\mapsto 4$ $(1, 3)$ $(0.31s)$ $(4.27s)$ $(75s)$ $(2.2s)$ $F_1$ $F_0$ $0.163626$ $0.450022$ $\bf 0.56655$ $0.56666$ $1\mapsto \emptyset; \ \ 2\mapsto 9, 11, 12$ $(1, 2)$ $(0.28s)$ $(7.65s)$ $(12470s)$ $(2.2s)$ $P_4$ $P_4$ $0.472136$ $0.86953$ $\bf 1.06418$ $1.23607$ $2\mapsto 2, 4;\ \ 3\mapsto 1, 3$ $(2, 3)$ $(0.27s)$ $(2.18s)$ $(12.6s)$ $(2.2s)$ $P_6$ $P_4$ $0.367365$ $0.811369$ $\bf 0.87366$ $0.89008$ $1\mapsto 4, 6;\ \ 3\mapsto 4, 6$ $(1, 3)$ $(0.26s)$ $(4.6s)$ $(59s)$ $(2.1s)$ $P_6$ $P_4$ $0.367365$ $0.737641$ $\bf 0.87321$ $0.89008$ $2\mapsto 4, 6;\ \ 3\mapsto 1, 3$ $(2, 3)$ $(0.26s)$ $(3.41s)$ $(57s)$ $(2.1s)$ $P_{10}$ $P_4$ $0.252282$ $0.523808$ $\bf 0.56837$ $0.56926$ $2\mapsto 8, 10;\ \ 3\mapsto \emptyset$ $(2, 3)$ $(0.26s)$ $(6.32s)$ $(4109s)$ $(2.6s)$ $T_4$ $P_4$ $0.38832$ $0.73094$ $\bf 0.93258$ $0.95452$ $2\mapsto 3, 8$ $(2)$ $(0.31s)$ $(1.57s)$ $(12s)$ $(2.31s)$

Table 3.  The computational results and comparison of various relaxations. The chosen graphs and description of columns is the same as in Table 2. In this table we present results of optimization when additional constraint of the maximal degree 3 has been imposed.

 $G_A$ $G_B$ $\underline{\Lambda}_{HL}^{sdp}$ $\underline{\Lambda}_{HL}^{sir}$ $\Lambda_{HL}^{opt}=\overline{\Lambda}_{HL}^{sir}$ $\overline{\Lambda}_{HL}^{sdp}$ $G_B \mapsto G_A$ $F_0$ $F_0$ $0.233688$ $0.507678$ $\bf 0.720830$ $0.87214$ $1\mapsto \emptyset;\ 2\mapsto 6$ $(1, 2)$ $(0.31s)$ $(2.73s)$ $(7.1s)$ $(2.9s)$ $F_0$ $F_0$ $0.233688$ $0.468053$ $\bf0.720830$ $0.87214$ $1\mapsto6;4\mapsto\emptyset$ $(1, 4)$ $(0.31s)$ $(1.1s)$ $(2.33s)$ $(2.85s)$ $F_0$ $F_0$ $0.333126$ $0.706635$ $\bf0.776875$ $0.87214$ $1\mapsto6;3\mapsto6$ $(1, 3)$ $(0.35s)$ $(2.45s)$ $(8.4s)$ $(2.82s)$ $F_1$ $F_0$ $0.163626$ $0.389941$ $\bf0.493727$ $0.566658$ $1\mapsto6;2\mapsto\emptyset$ $(1, 2)$ $(0.38s)$ $(3.67s)$ $(13.4s)$ $(2.83s)$ $P_4$ $P_4$ $0.472136$ $0.869530$ $\bf0.954520$ $1.23607$ $3\mapsto\emptyset;2\mapsto2$ $(2, 3)$ $(0.31s)$ $(1.86s)$ $(7.8s)$ $(2.86s)$ $P_6$ $P_4$ $0.367365$ $0.811369$ $\bf0.828427$ $0.89008$ $1\mapsto4, 6;3\mapsto2$ $(1, 3)$ $(0.36s)$ $(3.35s)$ $(22.9s)$ $(2.83s)$ $P_6$ $P_4$ $0.367365$ $0.737641$ $\bf0.820751$ $0.89008$ $2\mapsto5;3\mapsto2$ $(2, 3)$ $(0.33)$ $(2.73s)$ $(9.21s)$ $(2.87s)$ $P_{10}$ $P_4$ $0.252282$ $0.523808$ $\bf0.559046$ $0.56926$ $2\mapsto\emptyset;3\mapsto11$ $(2, 3)$ $(0.33s)$ $(4.78s)$ $(13.87s)$ $(2.86s)$ $T_4$ $P_4$ $0.38832$ $0.692266$ $\bf0.890084$ $0.95452$ $2\mapsto4$ $(2)$ $(0.31s)$ $(0.88s)$ $(1.5s)$ $(2.11s)$
•  [1] J. I. Aihara, Reduced HOMO-LUMO Gap as an Index of Kinetic Stability for Polycyclic Aromatic Hydrocarbons, J. Phys. Chem. A, 103 (1999), 7487-7495. [2] J. I. Aihara, Weighted HOMO-LUMO energy separation as an index of kinetic stability for fullerenes, Theor. Chem. Acta, 102 (1999), 134-138. [3] N. C. Bacalis and A. D. Zdetsis, Properties of hydrogen terminated silicon nanocrystals via a transferable tight-binding Hamiltonian, based on ab-initio results, J. Math. Chem., 26 (2009), 962-970.  doi: 10.1007/s10910-009-9557-x. [4] S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press New York, NY, USA, 2004. doi: 10.1017/CBO9780511804441. [5] A. E. Brouwer and W. H. Haemers, Spectra of Graphs, Springer New York, Dordrecht, Heidelberg, London, 2012. doi: 10.1007/978-1-4614-1939-6. [6] D. Cvetković, M. Doob and H. Sachs, Spectra of Graphs - Theory and Application, Academic Press, New York, 1980. [7] D. Cvetković, P. Hansen and V. Kovačevič-Vučič, On some interconnections between combinatorial optimization and extremal graph theory, Yugoslav Journal of Operations Research, 14 (2004), 147-154.  doi: 10.2298/YJOR0402147C. [8] P. W. Fowler, P. Hansen, G. Caporosi and A. Soncini, Polyenes with maximum HOMO-LUMO gap, Chemical Physics Letters, 342 (2001), 105-112. [9] P. V. Fowler, HOMO-LUMO maps for chemical graphs, MATCH Commun. Math. Comput. Chem., 64 (2010), 373-390. [10] C. D. Godsil, Inverses of trees, Combinatorica, 5 (1985), 33-39.  doi: 10.1007/BF02579440. [11] I. Gutman and D. H. Rouvray, An Aproximate TopologicaI Formula for the HOMO-LUMO Separation in Alternant Hydrocarboons, Chemical-Physic Letters, 72 (1979), 384-388. [12] E. Hückel, Quantentheoretische Beiträge zum Benzolproblem, Zeitschrift für Physik, 30 (1931), 204-286. [13] G. Jaklić, HL-index of a graph, Ars Mathematica Contemporanea, 5 (2012), 99-105. [14] S. Kim, M. Kojima and K. Toh, A Lagrangian-DNN relaxation: a fast method for computing tight lower bounds for a class of quadratic optimization problems, Mathematical Programming, 156 (2016), 161-187.  doi: 10.1007/s10107-015-0874-5. [15] Xueliang Li, Yiyang Li, Yongtang Shi and I. Gutman, Note on the HOMO-LUMO index of graphs, MATCH Commun. Math. Comput. Chem., 70 (2013), 85-96. [16] Chen Lin and Jinfeng Liu, Extremal values of matching energies of one class of graphs, Applied Mathematics and Computation, 273 (2016), 976-992.  doi: 10.1016/j.amc.2015.10.025. [17] L. Löfberg, A toolbox for modeling and optimization in MATLAB, 2004 IEEE internationalsymposium on computer aided control systems design (CACSD 2004), September 2-4, 2004, Taipei, 284-289. [18] M. Hamala and M. Trnovská, Nonlinear Programming, Theory and Algorithms (in Slovak), Epos, Bratislava, 2013. [19] B. Mohar, Median eigenvalues of bipartite planar graphs, MATCH Commun. Math. Comput. Chem., 70 (2013), 79-84. [20] M. Mohar, Median eigenvalues and the HOMO-LUMO index of graphs, Journal of Combinatorial Theory, Series B, 112 (2015), 78-92.  doi: 10.1016/j.jctb.2014.12.001. [21] S. Pavlíková and J. Krč-Jediný, On the inverse and dual index of a tree, Linear and Multilinear Algebra, 28 (1990), 93-109.  doi: 10.1080/03081089008818034. [22] S. Pavlíková, A note on inverses of labeled graphs, Australasian Journal on Combinatorics, 67 (2017), 222-234. [23] S. Pavlíková and D. Ševčovič, On a construction of integrally invertible graphs and their spectral properties, Linear Algebra and its Applications, 532 (2017), 512-533.  doi: 10.1016/j.laa.2017.07.005. [24] S. Pavlíková and D. Ševčovič, Maximization of the spectral gap for chemical graphs by means of a solution to a mixed integer semidefinite program, Computer Methods in Materials Science, 4 (2016), 169-176. [25] D. Ševčovič and M. Trnovská, Solution to the inverse Wulff problem by means of the enhanced semidefinite relaxation method, Journal of Inverse and Ⅲ-posed Problems, 23 (2015), 263-285.  doi: 10.1515/jiip-2013-0069. [26] J. F. Sturm, Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones, Optimization Methods and Software, 11 (1999), 625-653.  doi: 10.1080/10556789908805766. [27] F. Zhang and Z. Chen, Ordering graphs with small index and its application, Discrete Applied Mathematics, 121 (2002), 295-306.  doi: 10.1016/S0166-218X(01)00302-X. [28] F. Zhang and C. An, Acyclic molecules with greatest HOMOLUMO separation, Discrete Applied Mathematics, 98 (1999), 165-171.  doi: 10.1016/S0166-218X(99)00119-5.

Figures(6)

Tables(3)

## Article Metrics

HTML views(837) PDF downloads(200) Cited by(0)

## Other Articles By Authors

• on this site
• on Google Scholar

### Catalog

/

DownLoad:  Full-Size Img  PowerPoint