The subject of this research consists of selected topics in graph theory and mathematical programming and some of their interactions. Graph theory is listed in priority topics of Discrete Mathematics and mathematical programming belongs to priority topics of Numerical Mathematics (OR and Optimization). Important part of the research will be devoted to the theory of graph spectra and to linear and semidefinite programming. The unifying discipline is combinatorial optimization where attention will be paid to interactions of graph spectra and semidefinite programming. Significant part of the research will be devoted to applications of graph theory in mathematical chemistry, computer science and engineering.
Investigations in the field of the theory of graph spectra will include the following topics: extremal problems with the largest eigenvalue; graphs with bounded second largest eigenvalue; graphs with least eigenvalue -2; integral graphs; study of eigenspaces of graphs, especially graph angles; the star complement technique; hereditary graph properties; graph invariants that can be used as structure descriptors (in chemistry and elsewhere); a study of the energy of a graph and other spectrally based invariants; investigations in graph theory related to previous but from the point of view of Laplacian spectrum and distances in graphs; spectral properties of fullerenes; development and the usage of suitable research software (package newGRAPH).
The main research topics in mathematical programming will be: phenomenon of ill-conditionedness in interior-point methods and implementation of stabilization procedures; exact and heuristic methods for global optimization; interior-point methods for semidefinite programming; stabilization of weighted least squares method.
In combinatorial optimization special attention will be paid to the traveling salesman problem due to its importance in theory (it is on the list of 10 most important mathematical problems) and practice. In particular, the research would address semidefinite relaxations of the traveling salesman problem and related branch-and-bound and branch-and-cut methods. Branch-and-bound methods will also be used in transportation when dealing with the problem of optimal traffic control at signalized intersections. Special attention will be paid to metaheuristics , in particular, to the variable neighborhood search and genetic algorithms as well as to applications of metaheuristics and spectral techniques to the parallelization of computing processes.
The use of decomposition theorems for graphs to obtain polynomial time optimization algorithms for the given classes of graphs, such as finding the size of a largest clique, the size of a largest stable set or the chromatic number of a graph. All these problems are NP-complete in general, but for example for perfect graphs, it is shown that they can be solved in polynomial time by making use of the ellipsoid method. It is of great interest to see whether the same optimization problems can be solved for perfect graphs by polynomial time purely combinatorial algorithms.
The planned investigations are natural extension of successful research and international cooperation in the past. In particular, this group of researchers acted in the period 2001-2005 within the project No. 1389 of basic research "Graph theory and mathematical programming with applications to chemistry and transportation. It is expected that positive trends will be continued, such as publishing monographs by international scientific publishers, organizing international conferences, giving invited lectures at international conferences, study visits abroad and other activities, in a good deal financed by foreign partners.All planned investigations will have original character, which will be verified by publication in refereed scientific journals, proceedings and monographs. The main research goal is publication of a large number of high quality papers and certain number of monographs. It is expected that this will confirm high international position of the group of researchers working in the theory of graph spectra and applications in mathematical chemistry. Quality of the researchers working in mathematical programming will also be confirmed. An important objective will be application of research results, which has, e.g., motivated plans for software development.