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

Soña Pavlíková; Daniel Ševčovič

doi:10.3934/naco.2019005

Article Contents

2019, Volume 9, Issue 1: 53-69. Doi: 10.3934/naco.2019005

This issue Previous Article Local smooth representation of solution sets in parametric linear fractional programming problems Next Article A fourth order implicit symmetric and symplectic exponentially fitted Runge-Kutta-Nyström method for solving oscillatory problems

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

Soña Pavlíková^1, and
Daniel Ševčovič^2, ,

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č
* Corresponding author: Daniel Ševčovič

Received: January 2018

Revised: June 2018

Published: March 2019

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

Abstract Full Text(HTML) Figure(6) / Table(3) Related Papers Cited by

Abstract

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.

Keywords:

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

Citation:

FullText(HTML)

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

Figure 4. Results of optimal bridging of the fulvene graph G_B= F₀ through the vertices {1,2} to G_A=F₀ a);through the vertices {1,4} to G_A=F₀ b);and through the vertices {1,2} to G_A=F₁ c).

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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.

Download: Full-size image PowerPoint slide

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)-muinv(A), Kinv(B)];
[inv(B)K', eye(m, m)-muinv(B) + inv(B)Winv(B)]
] >= 0, ...
[[eye(n, n) + etainv(A), Kinv(B)];
[inv(B)K', eye(m, m) + etainv(B) + inv(B)Winv(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)

| Show Table

DownLoad: CSV

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)$

| Show Table

DownLoad: CSV

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)$

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

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