Project 174033

Graph theory and mathematical programming with applications to chemistry and computer science

Leader: Slobodan Simić, Research Professor


The subject of this research consists of selected topics in graph theory and mathematical programming and some of their interactions. Important part of the research will be devoted to the theory of graph spectra, structural graph theory, non-linear programming and global optimization. The unifying discipline for graph theory and mathematical programming 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. Applications in chemistry include the study of mathematical properties of molecular structure descriptors, especially those based on graph spectra and graph metrics. Applications in computer science are related to the internet topology and search engines, multiprocessor interconnection networks and quantum computing. In all areas a special attention is paid to the design of algorithms and the study of their complexity. The development and the use of relevant sophisticated software has a special role in this project so that it has all characteristics of a theoretical-experimental project. The project has about 30 researchers and represents a continuation of similar projects from last few decades. Considerable attention is paid to the work with doctoral students (there are 11 doctoral students in the team).

Keywords: graph theory, mathematical programming, spectra of graphs, theoretical chemistry, computer science

Research description

The following mutually interrelated research areas will be studied:

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". In the period 2006-2010 the project No. 144015G of basic research "Graph theory and mathematical programming with applications to chemistry and engineering" has been carried out (

Our research group has published in the past also the following monographs on which the current research is carried out to a great extent:

Expected results

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 positive trends will be continued, such as publishing monographs by international scientific publishers, organizing international conferences, giving invited lectures at international conferences, research visits abroad and other activities, in a good deal financed by foreign partners.
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. New trends involving parallelization and hybridization of exact and meta-heuristic optimization methods will be applied to various combinatorial and global optimization problems. An international cooperation will be practiced by engaging coauthors from abroad.
An important objective will be application of research results, which has, e.g., motivated plans for software development.
In spectral graph theory we expect the result relate to all subjects quoted in the research description and especially results in relation with extremal problems with eigenvalues for the adjacency, Laplacian and signless Laplacian natrix. We shall continue the work on further development of spectral graph theory based on the signless Laplacian matrix. A number of problems with integral graphs will be solved.
We expect a great number of papers in chemical graph theory: problems with graph energy, Randić and Wiener index will be treated among others. Graph with extremal values of structural descriptors will be studied.
A new monograph on application of graph spectra as well as a monograph on the spectral graph theory based on the segnless Laplacian will be published.

Research relevance

Spectral Graph Theory is an important multidisciplinary area of Science that uses the methods of Linear Algebra to solve problems in Graph Theory and, on the other hand, it has been used to model and treat problems in Chemistry, Computer Science, Physics, Operational Research, Combinatorial Optimization, Biology, Bioinformatics, Geography, Economics and Social Sciences , among others.
Besides classical and well documented applications to Chemistry, we are witnesses of the appearance of graph eigenvalues and eigenvectors in Computer Science in various investigations.
One of the main applications of graph spectra to Chemistry is the application in a theory of unsaturated conjugated hydrocarbons known as the Huckel molecular orbital theory.
It was recognized in about last ten years that graph spectra have several important applications in computer science. Graph spectra appear in internet technologies, pattern recognition, computer vision, data mining, multiprocessor systems, statistical databases and in many other areas. There are thousands of such scientific papers.
It should be noted that spectra of several graph matrices appear in applications. The adjacency matrix and Laplacian appear most frequently but also the signless Laplacian as well as normalized versions of these matrices. Incidence, distance and other matrices can be found as well. Sometimes the considerations move from graph matrices to general ones; equivalently, weighted graphs appear instead of graphs. In some cases we encounter digraphs and hypergraphs as well.
Of course, mathematicians should react on the explosion of the number of papers in computer science which use graph spectra by selecting for their own research some subjects from or inspired by such applications.
A monograph with a comprehensive treatment of applications of graphs spectra is missing at the present. Our investigations can trace the way to the creation of such a monograph.