Project 174033

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

Leader: Slobodan Simić, Research Professor

Abstract

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:

1) Spectral graph theory (research leader S. Simić),
2) Chemical graph theory (research leader I. Gutman),
3) Mathematical programming (research leader V. Vujčić),
4) Structural graph theory (research leader K. Vušković),
5) Graph spectra in computer science (research leader D. Stevanović).

1) Spectral graph theory
A spectral graph theory is a theory in which graphs are studied by means of eigenvalues of a matrix M which is in a prescribed way defined for any graph. This theory is called M - theory. Frequently used graph matrices are the adjacency matrix A, the Laplacian L and the signless Laplacian Q=D+A, where D is a diagonal matrix of vertex degrees. Some other graph matrices are used as well. The spectral graph theory includes all these particular theories together with interaction tools.
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 the previous topic but from the point of view of Laplacian and signless Laplacian spectrum and distances in graphs; limit points for specified eigenvalues within some classes of graphs; perturbation problems related to the largest (least) eigenvalue; the Laplacian and the signless Laplacian spectrum (relations between the corresponding spectra); determination of graphs by various graph spectra; development and the usage of suitable research software (package newGRAPH, smallGRAPHS, ugrading Mathematica).

2) Chemical graph theory
Graphs provide a natural mathematical model of molecules, and are much used in chemical researches. Pertinently chosen graph invariants (known under the name "molecular structure descriptors" or "topological indices") reflect certain details of molecular structure, and are applied in mathematical modeling of physico-chemical, pharmacologic, toxicological, and other properties of chemical compounds. Our researches will be concerned with the study of mathematical properties of molecular structure descriptors, especially those based on graph spectra and graph metrics, and with chemical applications of the results obtained.

3) Mathematical programming
Within the topic Mathematical Programming the following research is planned: mathematical modeling of various optimization problems with development of algorithms for combinatorial optimization, nonlinear programming and global optimization problems.
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.
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.

4) Structural graph theory
Developing efficient algorithms for solving combinatorial problems has been of great importance to the modern technological society, due to applications in diverse areas such as transportation, telecommunication, molecular biology, industrial engineering, etc. Many of these applications can be modeled with graphs, and the problems reduce to optimizing certain parameters, such as graph coloring or finding a maximum clique in a graph. These problems are intractable in general, but can become tractable in special classes of graphs, especially hereditary classes. We propose to investigate the structure of several hereditary classes of graphs, trying to develop general techniques for exploiting structure in construction of efficient combinatorial optimization algorithms.

5) Graph spectra in computer science
Spectral properties of graphs are among the most important graph invariants which can be calculated in polynomial time. In this subproject, we will study the meaning and the possibilities for using the eigenvectors and eigenspaces in several problems of computer science:

- topological characteristics of complex networks: expansibility, topological and functional bottlenecks, organization of clusters, global communicability...
- quantum computing: quantum state transfer, controllability and Hamiltonian estimation in network models represented by adjacency and Laplacian matrices of graphs
- multiprocessor connection networks: algorithms for load balancing, determination of networks with adequate spectral and combinatorial properties
- pattern recognition: studying the properties of Ihara's zeta function on graphs

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 (http://www.mi.sanu.ac.rs/projects/project144015.htm)

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

Cvetković D., Doob M., Gutman I., Torgašev A., Recent Results in the Theory of Graph Spectra, North-Holland, Amsterdam, 1988.
Cvetković D., Doob M., Sachs H., Spectra of Graphs, Theory and Application, 3rd edition, Johann Ambrosius Barth Verlag, Heidelberg--Leipzig, 1995.
Cvetković D., Rowlinson P., Simić S. K., Eigenspaces of Graphs, Cambridge University Press, Cambridge, 1997.
Cvetković D., Rowlinson P., Simić S., Spectral generalizations of line graphs: On graphs with least eigenvalue -2, Cambridge University Press, Cambridge, 2004.

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.

RESEARCH TEAM REFERENCES

01. Cvetković D., Rowlinson P., Simić S., An Introduction to the Theory of Graph Spectra, Cambridge University Press, Cambridge, 2010, XI+364, ISBN 987-0-521-13408-8.
02. Cvetković D., Simić S.K., Towards a spectral theory of graphs based on the signless Laplacian, II, Linear Algebra and its Applications, 432 (2010), 2257-2272.
03. M. Aouchiche, F.K. Bell, D. Cvetković, P. Hansen, P. Rowlinson, S.K. Simić, D. Stevanović, Variable neighborhood search for extremal graphs, 16. Some conjectures related to the largest eigenvalue of a graph, European Journal of Operations Research, 191 (3) (2008), 661-676.
04. D. Stevanović, M. Milošević, A spectral proof of the uniqueness of strongly regular graph with parameters (81,20,1,6), European Journal of Combinatorics, 30 (2009), 957-968.
05. I. Gutman, X. Li, J. Zhang, Graph energy, in: M. Dehmer, F. Emmert-Streib (Eds.), Analysis of Complex Networks. From Biology to Linguistics, Wiley-VCH,Weinheim, Chapter 7, 2009, pp. 145-174, ISBN 987-3-527-32345-6.
06. I. Gutman, B. Furtula, M. Petrović, Terminal Wiener index, Journal of Mathematical Chemistry 46 (2009) 522-531.
07. I. Gutman, B. Furtula, A. T. Balaban, Algorithm for simultaneous calculation of Kekule and Clar structure counts, and Clar number of benzenoid molecules, Polycyclic Aromatic Compounds 26 (2006) 17-35.
08. M.Chudnovsky, G. Cornuejols, X. Liu, P. Seymour, K. Vušković, Recognizing Berge graphs, Combinatorica 25 (2) (2005) 143-186.
09. T. Kloks, H. Muller, K. Vušković, Even-hole-free graphs that do not contain diamonds: a structure theorem and its consequences, Journal of Combinatorial Theory B 99 (2009) 733-800.
10. N. Mladenović, M. Dražić, V. Kovačević-Vujčić, M. Čangalović, General variable neighborhood search for the continuous optimization, European Journal of Operations Research, 191 (3) (2008), 753-770.