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

Previous Article
Local smooth representation of solution sets in parametric linear fractional programming problems
NACO Home
This Issue
Next Article
A fourth order implicit symmetric and symplectic exponentially fitted Runge-Kutta-Nyström method for solving oscillatory 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 & 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]	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]	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
[7]	Eric Babson and Dmitry N. Kozlov. Topological obstructions to graph colorings. Electronic Research Announcements, 2003, 9: 61-68.
[8]	Oded Schramm. Hyperfinite graph limits. Electronic Research Announcements, 2008, 15: 17-23. doi: 10.3934/era.2008.15.17
[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]	John Kieffer and En-hui Yang. Ergodic behavior of graph entropy. Electronic Research Announcements, 1997, 3: 11-16.
[11]	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
[12]	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
[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]	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
[15]	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
[16]	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
[17]	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
[18]	Dominique Zosso, Braxton Osting. A minimal surface criterion for graph partitioning. Inverse Problems & Imaging, 2016, 10 (4) : 1149-1180. doi: 10.3934/ipi.2016036
[19]	Mario Jorge Dias Carneiro, Rafael O. Ruggiero. On the graph theorem for Lagrangian minimizing tori. Discrete & Continuous Dynamical Systems - A, 2018, 38 (12) : 6029-6045. doi: 10.3934/dcds.2018260
[20]	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

Impact Factor:

Tools

Metrics

Tools

Article outline

Figures and Tables

Impact Factor:

Tools

Figures and Tables

Impact Factor:

American Institute of Mathematical Sciences