Page 329 - 8th European Congress of Mathematics ∙ 20-26 June 2021 ∙ Portorož, Slovenia ∙ Book of Abstracts
P. 329
SPECTRAL GRAPH THEORY (MS-46)
Eigenvalues and [a, b]-factors in regular graphs
Suil O, suil.o@sunykorea.ac.kr
SUNY Korea, Republic of Korea
For positive integers, r ≥ 3, h ≥ 1, and k ≥ 1, Bollobás, Saito, and Wormald proved some
sufficient conditions for an h-edge-connected r-regular graph to have a k-factor in 1985. Lu
gave an upper bound for the third-largest eigenvalue in a connected r-regular graph to have
a k-factor in 2010. Gu found an upper bound for certain eigenvalues in an h-edge-connected
r-regular graph to have a k-factor in 2014.
For positive integers a ≤ b, an even (or odd) [a, b]-factor of a graph G is a spanning subgraph
H such that for each vertex v ∈ V (G), dH(v) is even (or odd) and a ≤ dH(v) ≤ b. In this talk,
we provide best upper bounds (in terms of a, b, and r) for certain eigenvalues (in terms of a, b, r,
and h) in an h-edge-connected r-regular graph G to guarantee the existence of an even [a, b]-
factor or an odd [a, b]-factor. This result extends the one of Bollbás, Saito, and Wormald, the
one of Lu, and the one of Gu.
Construction of upper bounds of the HOMO-LUMO spectral gaps by
semidefinite relaxation techniques
Sonˇa Pavlíková, sona.pavlikova@stuba.sk
Slovak University of Technology, Slovakia
An important application of graph theory in quantum chemistry is based on the fact that the en-
ergy of the highest occupied molecular orbital (HOMO) and of the lowest unoccupied molecular
orbital (LUMO) of a molecule correspond, respectively, to the smallest positive and the largest
negative eigenvalue of a graph representing the molecule; the difference of these eigenvalues is
known as the HOMO-LUMO spectral gap.
In our contribution we study the HOMO - LUMO spectral gap of weighted graphs. In par-
ticular, we focus constructions of new graphs from old by ‘bridging’ two input graphs over a
common bipartite subgraph, with the aim to maximize the spectral gap with respect to the struc-
ture of the ingredients. Among the tools we use estimates of the spectrum of the inverse of a
block matrix consisting of adjacency matrices of input graphs on its block diagonal and the adja-
cency matrix of the bridging graph as off-diagonal blocks; maximization of the HOMO-LUMO
gap turns out to be equivalent to minimization of the sum of largest and smallest eigenvalues of
the inverse of the block matrix. An upper bound on the gap is then be obtained by semidefinite
programming.
This a joint work with Daniel Sevcovic.
Acknowledgment: This research was supported by the APVV Research Grants 17-0428 and
19-0308, as well as from the VEGA Research Grants 1/0238/19 and 1/0206/20.
327
Eigenvalues and [a, b]-factors in regular graphs
Suil O, suil.o@sunykorea.ac.kr
SUNY Korea, Republic of Korea
For positive integers, r ≥ 3, h ≥ 1, and k ≥ 1, Bollobás, Saito, and Wormald proved some
sufficient conditions for an h-edge-connected r-regular graph to have a k-factor in 1985. Lu
gave an upper bound for the third-largest eigenvalue in a connected r-regular graph to have
a k-factor in 2010. Gu found an upper bound for certain eigenvalues in an h-edge-connected
r-regular graph to have a k-factor in 2014.
For positive integers a ≤ b, an even (or odd) [a, b]-factor of a graph G is a spanning subgraph
H such that for each vertex v ∈ V (G), dH(v) is even (or odd) and a ≤ dH(v) ≤ b. In this talk,
we provide best upper bounds (in terms of a, b, and r) for certain eigenvalues (in terms of a, b, r,
and h) in an h-edge-connected r-regular graph G to guarantee the existence of an even [a, b]-
factor or an odd [a, b]-factor. This result extends the one of Bollbás, Saito, and Wormald, the
one of Lu, and the one of Gu.
Construction of upper bounds of the HOMO-LUMO spectral gaps by
semidefinite relaxation techniques
Sonˇa Pavlíková, sona.pavlikova@stuba.sk
Slovak University of Technology, Slovakia
An important application of graph theory in quantum chemistry is based on the fact that the en-
ergy of the highest occupied molecular orbital (HOMO) and of the lowest unoccupied molecular
orbital (LUMO) of a molecule correspond, respectively, to the smallest positive and the largest
negative eigenvalue of a graph representing the molecule; the difference of these eigenvalues is
known as the HOMO-LUMO spectral gap.
In our contribution we study the HOMO - LUMO spectral gap of weighted graphs. In par-
ticular, we focus constructions of new graphs from old by ‘bridging’ two input graphs over a
common bipartite subgraph, with the aim to maximize the spectral gap with respect to the struc-
ture of the ingredients. Among the tools we use estimates of the spectrum of the inverse of a
block matrix consisting of adjacency matrices of input graphs on its block diagonal and the adja-
cency matrix of the bridging graph as off-diagonal blocks; maximization of the HOMO-LUMO
gap turns out to be equivalent to minimization of the sum of largest and smallest eigenvalues of
the inverse of the block matrix. An upper bound on the gap is then be obtained by semidefinite
programming.
This a joint work with Daniel Sevcovic.
Acknowledgment: This research was supported by the APVV Research Grants 17-0428 and
19-0308, as well as from the VEGA Research Grants 1/0238/19 and 1/0206/20.
327
