Projects / Programmes
January 1, 2015
- December 31, 2021
| Code |
Science |
Field |
Subfield |
| 1.01.00 |
Natural sciences and mathematics |
Mathematics |
|
| 1.07.00 |
Natural sciences and mathematics |
Computer intensive methods and applications |
|
| Code |
Science |
Field |
| P110 |
Natural sciences and mathematics |
Mathematical logic, set theory, combinatories |
| Code |
Science |
Field |
| 1.01 |
Natural Sciences |
Mathematics |
mathematics, graph theory, topological graph theory, metric graph theory, graph products, chemical graph theory, geometric graphs, graph invariants, algorithmic graph theory, applications of graph theory
Researchers (24)
Organisations (2)
Abstract
The goal of the programme is to develop central areas of graph theory and in this way strengthening the role, the visibility, and the influence of the Slovenian graph theory as one of the world's centers of this theory. Among the areas that we especially plan to develop are topological graph theory, metric graph theory, graph products, chemical graph theory, graph theory related to geometry, graph invariants, algorithmic graph theory, and applications of these areas. Here is a summary of some of the problems and topics that we will investigate.
Our priorities in topological graph theory will be a search for complete minors and immersions in surface embedded graphs, investigations of structural properties of the crossing number problem, and research in the area of graph drawing. In metric graph theory we will investigate classes of median-type graphs for which a local-global characterization of their complexes has been proved. We will investigate other natural generalizations of median graphs within the context of weakly modular graphs and their properties, such as the fixed point theorem, contractibility and retractibility from product spaces. We will study possibilities of measuring distances between graphs based on the concept of Hausdorff graph distance. This is a new idea that was recently introduced in our programme group. On graph products we will continue to study convexities (Steiner, geodetic), different product labelings, and consider algorithmic aspects. In the area of chemical graph theory we will investigate carbon nanotubes, in particular we will be interested it the structure and properties of resonance graphs of these nanotubes. We will also try to develop a polynomial-time algorithm for the Clar problem for more general graphs rather than just specific benzenoid graphs. Our main focus on graphs with geometric properties will be to determine which problems can be solved more efficiently for geometrically-constraint graphs. In the area of graph invariants we shall study graph classes which admit threshold colorings on one hand, on the other we would like to find minimal obstructions (critical graphs), the smallest graphs which do not admit total threshold colorings. We will continue with the research of domination invariants on product graphs and with the research of domination game played on graphs. Among other invariants that will be of special interest to us are vertex and edge b-colorings, efficient open domination, total domination, and L(p,q,r)–labelings. During our investigations we will always keep in mind algorithmic aspects. For instance, we will try to improve the time complexity of the decomposition algorithm with respect to the strong product, develop faster algorithms specialized for planar graphs and faster algorithms specialized for geometric intersection graphs.
Significance for science
The project belongs to basic research in the area of mathematics. Problems that we will work on are internationally important, which can in particular be justified by our bibliography from the last period as well as with the (citation) impact of our results. The problems are central in the area of graph theory and at the same time have applications in other scientific fields. For instance, our results on carbon nanotubes can accelerate the synthesis of carbon nanomolecules and therefore help the improvement of nanomaterials. Distances between graphs are used in those areas of science where similarities of objects are studied. New insights concerning distances between graphs further develop existing areas and give a fresh look at existing problems, specifically in areas like biology, computer science, chemistry, social sciences and linguistics. The study of graph invariants addresses some important real-life problems. In particular, the frequency assignment problem asks for assigning frequencies to transmitters in a wireless network. In a broadcasting network, each transmitter is assigned a frequency channel for its transmissions. Two transmissions can interfere if their channels are too close. This means that even if two transmitters use different channels, there still may be interference if the two transmitters are located close to each other. The spectrum of frequencies gets more and more scarce, because of increasing demands. Thus the task is to minimize the span of frequencies while avoiding interference.
We expect that the newly obtained results will be published in leading journals from the area of discrete mathematics and we will present them at international scientific conferences. We expect that we will be invited to deliver several invited plenary talks which will further emphasize the importance of our research achievements. In this way we will further increase the international role of the Slovenian graph theory school.
Significance for the country
The research programme is oriented to encourage the integration of the most promising young researchers. In this way it enables a long-term continuation of the research quality in mathematics, which in turn has a positive influence on the quality of the university programs in mathematics and other sciences. In the period 2009-2014 we have supervised 9 Ph.D. students, and three more completed dissertations are expected by the end of this year. After finishing their Ph.D., our students are getting employed also in industry, hence our programme has a positive impact on the national economy. Since mathematics is used in many other areas, the quality of research in mathematics has an indirect but important influence on the development of other disciplines as well. Inside mathematics the programme mostly develops graph theory and keeps and strengthens its world reputation. The expected results are mostly theoretical. Nevertheless, they have a big potential for applications, especially our research in algorithmic and optimization aspects of graph theory. This can be well justified with our previous research that has led to a cooperation with the Slovenian industry focused on technological development, mostly in the information and telecommunication technology. In June 2015 we will organize the “8th Slovenian International Conference on Graph Theory”, where we expect about 200-300 participants. This is one of the largest conferences in the world on graph theory. Our programme group will lead the organization, in particular, the programme leader is the main organizer of the event.
Most important scientific results
Annual report
2015,
interim report
Most important socioeconomically and culturally relevant results
Annual report
2015,
interim report
