# American Institute of Mathematical Sciences

• Previous Article
A fourth order implicit symmetric and symplectic exponentially fitted Runge-Kutta-Nyström method for solving oscillatory problems
• NACO Home
• This Issue
• Next Article
Local smooth representation of solution sets in parametric linear fractional programming problems
March  2019, 9(1): 53-69. doi: 10.3934/naco.2019005

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

 1 Institute of Information Engineering, Automation, and Mathematics, FCFT, Slovak Technical University, 812 37 Bratislava, Slovakia 2 Department of Applied Mathematics and Statistics, FMFI, Comenius University, 842 48 Bratislava, Slovakia

* Corresponding author: Daniel Ševčovič

Received  January 2018 Revised  June 2018 Published  October 2018

Fund Project: 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.

Citation: Soña Pavlíková, Daniel Ševčovič. On construction of upper and lower bounds for the HOMO-LUMO spectral gap. Numerical Algebra, Control & Optimization, 2019, 9 (1) : 53-69. doi: 10.3934/naco.2019005
##### References:

show all references

##### References:
A bridged graph $G_C = {\mathcal B}_K(G_A, G_B)$ through a bipartite graph $G_K$.
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).
An example of an invertible graph $F_0$ (left) representing the chemical organic molecule of fulvene (right).
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).
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).
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.
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)
 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)
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)$
 $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)$
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)$
 $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] Bruno Colbois, Alexandre Girouard. The spectral gap of graphs and Steklov eigenvalues on surfaces. Electronic Research Announcements, 2014, 21: 19-27. doi: 10.3934/era.2014.21.19 [2] Damien Thomine. A spectral gap for transfer operators of piecewise expanding maps. Discrete & Continuous Dynamical Systems - A, 2011, 30 (3) : 917-944. doi: 10.3934/dcds.2011.30.917 [3] Ye Tian, Cheng Lu. Nonconvex quadratic reformulations and solvable conditions for mixed integer quadratic programming problems. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1027-1039. doi: 10.3934/jimo.2011.7.1027 [4] Sébastien Gouëzel. An interval map with a spectral gap on Lipschitz functions, but not on bounded variation functions. Discrete & Continuous Dynamical Systems - A, 2009, 24 (4) : 1205-1208. doi: 10.3934/dcds.2009.24.1205 [5] Jean-Pierre Conze, Y. Guivarc'h. Ergodicity of group actions and spectral gap, applications to random walks and Markov shifts. Discrete & Continuous Dynamical Systems - A, 2013, 33 (9) : 4239-4269. doi: 10.3934/dcds.2013.33.4239 [6] Shuang Chen, Jun Shen. Large spectral gap induced by small delay and its application to reduction. Discrete & Continuous Dynamical Systems - A, 2020, 40 (7) : 4533-4564. doi: 10.3934/dcds.2020190 [7] Rostislav Grigorchuk, Volodymyr Nekrashevych. Self-similar groups, operator algebras and Schur complement. Journal of Modern Dynamics, 2007, 1 (3) : 323-370. doi: 10.3934/jmd.2007.1.323 [8] Eric Babson and Dmitry N. Kozlov. Topological obstructions to graph colorings. Electronic Research Announcements, 2003, 9: 61-68. [9] J. William Hoffman. Remarks on the zeta function of a graph. Conference Publications, 2003, 2003 (Special) : 413-422. doi: 10.3934/proc.2003.2003.413 [10] Oded Schramm. Hyperfinite graph limits. Electronic Research Announcements, 2008, 15: 17-23. doi: 10.3934/era.2008.15.17 [11] John Kieffer and En-hui Yang. Ergodic behavior of graph entropy. Electronic Research Announcements, 1997, 3: 11-16. [12] Qinghong Zhang, Gang Chen, Ting Zhang. Duality formulations in semidefinite programming. Journal of Industrial & Management Optimization, 2010, 6 (4) : 881-893. doi: 10.3934/jimo.2010.6.881 [13] Louis Caccetta, Syarifah Z. Nordin. Mixed integer programming model for scheduling in unrelated parallel processor system with priority consideration. Numerical Algebra, Control & Optimization, 2014, 4 (2) : 115-132. doi: 10.3934/naco.2014.4.115 [14] René Henrion, Christian Küchler, Werner Römisch. Discrepancy distances and scenario reduction in two-stage stochastic mixed-integer programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 363-384. doi: 10.3934/jimo.2008.4.363 [15] Elham Mardaneh, Ryan Loxton, Qun Lin, Phil Schmidli. A mixed-integer linear programming model for optimal vessel scheduling in offshore oil and gas operations. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1601-1623. doi: 10.3934/jimo.2017009 [16] Edward S. Canepa, Alexandre M. Bayen, Christian G. Claudel. Spoofing cyber attack detection in probe-based traffic monitoring systems using mixed integer linear programming. Networks & Heterogeneous Media, 2013, 8 (3) : 783-802. doi: 10.3934/nhm.2013.8.783 [17] Mahdi Roozbeh, Saman Babaie–Kafaki, Zohre Aminifard. Two penalized mixed–integer nonlinear programming approaches to tackle multicollinearity and outliers effects in linear regression models. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020128 [18] Zhiguo Feng, Ka-Fai Cedric Yiu. Manifold relaxations for integer programming. Journal of Industrial & Management Optimization, 2014, 10 (2) : 557-566. doi: 10.3934/jimo.2014.10.557 [19] Roy H. Goodman. NLS bifurcations on the bowtie combinatorial graph and the dumbbell metric graph. Discrete & Continuous Dynamical Systems - A, 2019, 39 (4) : 2203-2232. doi: 10.3934/dcds.2019093 [20] Mario Roy, Mariusz Urbański. Random graph directed Markov systems. Discrete & Continuous Dynamical Systems - A, 2011, 30 (1) : 261-298. doi: 10.3934/dcds.2011.30.261

Impact Factor: