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





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) |
|
|||||||
|
|||||||
|
|||||||
|
|||||||
|
|||||||
|
|||||||
|
|||||||
|
|||||||
|
|||||||
|
|||||||
|
|||||||
|
|||||||
|
|||||||
|
|||||||
[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
Other articles
by authors
[Back to Top]