The subject of this research are 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 nonlinear 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 and transportation.
Investigations in the field of the theory of graph spectra will include the following topics: 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.
The main research topics in mathematical programming will be: phenomenon of ill-conditionedness in interior-point methods and implementation of stabilization procedures; stepŠ-size algorithms in nonlinear programming; exact and heuristic methods for global optimization; interior-point methods for semidefinite programming; stabilization of weighted least squares method; symbolic implementation of nonlinear programming methods; applications of the tent theory to optimal control problems. 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. Problems of optimal packing and cutting will also be considered.
The planned investigations are natural extension of successful research and international cooperation in the past. 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.
The theory of graph spectra has come into existence in seventies by uniting some relevant, similar, but to that time disjoint, results from graph theory, quantum chemistry and numerical mathematics into a coherent theory. Academicians Cvetković and Gutman have given great contributions to the creation and further development of this theory. This has been achieved through Cvetković’s doctoral dissertation “Graphs and their spectra” (1971) and monograph “Spectra of Graphs and Applications” (1980) by Cvetković, Doob and Sachs, and by a great number of papers in which the theory of graph spectra is applied to the Huckel theory of non-saturated hydrocarbons by Gutman. The number of published papers in scientific journals of different branches of science can be estimated as several thousands. The number of citations can also be counted in thousands. According to Citation Index, Cvetković is cited over 1000 times and Gutman over 4000 times. The theory of graph spectra is being further developed, judging on the basis of the number of papers, monographs and conferences devoted to it. The principal directions of progress in mathematical programming can be seen from the program of the 17th International Symposium on Mathematical Programming held in August 2000 in Atlanta and attended by 1000 participants. Sections with the largest number of papers were Combinatorial Optimization, Integer Programming, Semidefinite Programming, Interior-Point Methods, Networks and Nonlinear Programming.
In Serbia the theory of graph spectra is the main research discipline for about 10 researchers and about 10 others occasionally take part in investigations. Titles of the researchers in the theory of graph spectra are distributed from assistants to academicians and they are located in all larger university centers (Belgrade, Novi Sad, Nis, Kragujevac). According to the evidence in literature the theory of graph spectra is being investigated throughout the world by several hundreds of researchers. By our knowledge the largest concentration of specialists in the theory of graph spectra is in Serbia.
Mathematical programming is the main research discipline for about 20 researchers in Serbia and this project couples together the most active ones. Mathematical programming group is a subset of much larger group working in operations research (about 100 researchers in Serbia).
The project is interdisciplinary and both by title and by research plan indicates possible applications. The planned research topics in the theory of graph spectra have great applicability in mathematical chemistry since some graph invariants can be used as molecule structure descriptors. In the case of non-saturated hydrocarbons eigenvalues of the corresponding graphs are energy levels of electrons. Closely related is the invariant called the energy of a graph, which is defined as the sum of eigenvalues moduli. The planned investigations of weighted graphs have direct application in transportation. Other possible applications could be telecommunication and computer networks, transmission networks, etc. The project plan includes investigation of stable algorithms for large-scale linear programming problems and development of fast heuristics for global optimization and the traveling salesman problem. Efficient solution of these problems is fundamental for development of future technologies.
Graph invariants which can serve as molecule structure descriptors (topological indices) are related to such physical characteristics as boiling point, molar volume, refraction index, vaporization heat and have direct application in pharmacology.
Graph models of signalized intersections have direct application in traffic control systems. Algorithms, heuristics and software for the traveling salesman problem can be used in the control of electrical power systems. Heuristics and software for global optimization have direct application in radar polyphase code design.