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

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

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č

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.

Keywords: Invertible graph; bridged graph, Schur complement, mixed integer semidefinite programming, spectral estimates, HOMO-LUMO spectral gap.

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

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

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.

show all references

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.

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

Figure Options

Download full-size image

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

Figure Options

Download full-size image

Download as PowerPoint slide

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

Figure Options

Download full-size image

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

Figure Options

Download full-size image

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

Figure Options

Download full-size image

Download as 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.

Figure Options

Download full-size image

Download as 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)

Table Options

Download as excel

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)

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 Options

Download as excel

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

Table Options

Download as excel

$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]	Rui Wang, Rundong Zhao, Emily Ribando-Gros, Jiahui Chen, Yiying Tong, Guo-Wei Wei. HERMES: Persistent spectral graph software. Foundations of Data Science, 2021, 3 (1) : 67-97. doi: 10.3934/fods.2021006
[2]	Lu Yang, Guangsheng Wei, Vyacheslav Pivovarchik. Direct and inverse spectral problems for a star graph of Stieltjes strings damped at a pendant vertex. Inverse Problems and Imaging, 2021, 15 (2) : 257-270. doi: 10.3934/ipi.2020063
[3]	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
[4]	Damien Thomine. A spectral gap for transfer operators of piecewise expanding maps. Discrete and Continuous Dynamical Systems, 2011, 30 (3) : 917-944. doi: 10.3934/dcds.2011.30.917
[5]	Ye Tian, Cheng Lu. Nonconvex quadratic reformulations and solvable conditions for mixed integer quadratic programming problems. Journal of Industrial and Management Optimization, 2011, 7 (4) : 1027-1039. doi: 10.3934/jimo.2011.7.1027
[6]	Sébastien Gouëzel. An interval map with a spectral gap on Lipschitz functions, but not on bounded variation functions. Discrete and Continuous Dynamical Systems, 2009, 24 (4) : 1205-1208. doi: 10.3934/dcds.2009.24.1205
[7]	Jean-Pierre Conze, Y. Guivarc'h. Ergodicity of group actions and spectral gap, applications to random walks and Markov shifts. Discrete and Continuous Dynamical Systems, 2013, 33 (9) : 4239-4269. doi: 10.3934/dcds.2013.33.4239
[8]	Shuang Chen, Jun Shen. Large spectral gap induced by small delay and its application to reduction. Discrete and Continuous Dynamical Systems, 2020, 40 (7) : 4533-4564. doi: 10.3934/dcds.2020190
[9]	Luís Simão Ferreira. A lower bound for the spectral gap of the conjugate Kac process with 3 interacting particles. Kinetic and Related Models, 2022, 15 (1) : 91-117. doi: 10.3934/krm.2021045
[10]	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
[11]	Qinghong Zhang, Gang Chen, Ting Zhang. Duality formulations in semidefinite programming. Journal of Industrial and Management Optimization, 2010, 6 (4) : 881-893. doi: 10.3934/jimo.2010.6.881
[12]	Eric Babson and Dmitry N. Kozlov. Topological obstructions to graph colorings. Electronic Research Announcements, 2003, 9: 61-68.
[13]	Oded Schramm. Hyperfinite graph limits. Electronic Research Announcements, 2008, 15: 17-23. doi: 10.3934/era.2008.15.17
[14]	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
[15]	John Kieffer and En-hui Yang. Ergodic behavior of graph entropy. Electronic Research Announcements, 1997, 3: 11-16.
[16]	Roberto De Leo, James A. Yorke. The graph of the logistic map is a tower. Discrete and Continuous Dynamical Systems, 2021, 41 (11) : 5243-5269. doi: 10.3934/dcds.2021075
[17]	René Henrion, Christian Küchler, Werner Römisch. Discrepancy distances and scenario reduction in two-stage stochastic mixed-integer programming. Journal of Industrial and Management Optimization, 2008, 4 (2) : 363-384. doi: 10.3934/jimo.2008.4.363
[18]	Louis Caccetta, Syarifah Z. Nordin. Mixed integer programming model for scheduling in unrelated parallel processor system with priority consideration. Numerical Algebra, Control and Optimization, 2014, 4 (2) : 115-132. doi: 10.3934/naco.2014.4.115
[19]	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 and Management Optimization, 2017, 13 (4) : 1601-1623. doi: 10.3934/jimo.2017009
[20]	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 and Heterogeneous Media, 2013, 8 (3) : 783-802. doi: 10.3934/nhm.2013.8.783

Impact Factor:

Tools

Metrics

Tools

Article outline

Figures and Tables

Impact Factor:

Tools

Figures and Tables

Impact Factor:

American Institute of Mathematical Sciences

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

References:

References:

Tools

Metrics

Other articles
by authors

Tools

Tools

Tools

Metrics

Other articles
by authors

American Institute of Mathematical Sciences

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

References:

References:

Tools

Metrics

Other articlesby authors

Tools

Tools

Tools

Metrics

Other articlesby authors

Other articles
by authors

Other articles
by authors