|
ABSTRACT:
|
In the first part of the talk, I will give a short
overview of two of my papers dealing with theory of graph spectra: one on bounding
the largest eigenvalue of nonregular graphs and the other on automatic generation
of upper bounds for the largest Laplacian eigenvalue of graphs.
In the second part of the talk, I will present my latest results
dealing with applications of graph spectra: Inspired by the property of an eigenvector
x corresponding to the least eigenvalue of an adjacency matrix of a bipartite
graph, I propose a simple heuristic to produce a cut in an arbitrary graph $G=(V,E)$ by placing vertices with nonnegative x-component
in one part and those with negative x-component in other part of the cut.
While at the moment I know of no approximation guarantee to this heuristic, I
will give some
theoretical support to its performance and provide results of extensive
testing on DIMACS benchmark graphs.
Further, I will relate this heuristic to earlier work of Delorme and Poljak [DP1,DP2,DP3] on an eigenvalue upper bound on the size of the
maximum cut and provide some extensions to their results.
References:
[DP1] C.Delorme, S.Poljak, Laplacian eigenvalues and the maximum cut problem,
Math. Program. 62 (1993), No.3(A), 557-574.
[DP2] C. Delorme, S. Poljak, The performance of an eigenvalue bound on the max-cut
problem in some classes of graphs, Discrete Math. 111 (1993), No.1-3, 145-156.
[DP3] C. Delorme, S. Poljak, Combinatorial
properties and the complexity of a max-cut approximation, Eur. J. Comb. 14
(1993), No.4, 313-333.
|
