# 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] Huiying Fan, Tao Ma. Parabolic equations involving Laguerre operators and weighted mixed-norm estimates. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5487-5508. doi: 10.3934/cpaa.2020249 [2] Yahia Zare Mehrjerdi. A new methodology for solving bi-criterion fractional stochastic programming. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020054 [3] Weisong Dong, Chang Li. Second order estimates for complex Hessian equations on Hermitian manifolds. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020377 [4] Alberto Bressan, Wen Shen. A posteriori error estimates for self-similar solutions to the Euler equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 113-130. doi: 10.3934/dcds.2020168 [5] Juan Pablo Pinasco, Mauro Rodriguez Cartabia, Nicolas Saintier. Evolutionary game theory in mixed strategies: From microscopic interactions to kinetic equations. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2020051 [6] Jie Zhang, Yuping Duan, Yue Lu, Michael K. Ng, Huibin Chang. Bilinear constraint based ADMM for mixed Poisson-Gaussian noise removal. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020071 [7] Kihoon Seong. Low regularity a priori estimates for the fourth order cubic nonlinear Schrödinger equation. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5437-5473. doi: 10.3934/cpaa.2020247 [8] Ahmad Z. Fino, Wenhui Chen. A global existence result for two-dimensional semilinear strongly damped wave equation with mixed nonlinearity in an exterior domain. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5387-5411. doi: 10.3934/cpaa.2020243 [9] Shenglan Xie, Maoan Han, Peng Zhu. A posteriori error estimate of weak Galerkin fem for second order elliptic problem with mixed boundary condition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020340

Impact Factor: