Projects / Programmes
Independence in domination in structured graph classes
Code |
Science |
Field |
Subfield |
1.01.05 |
Natural sciences and mathematics |
Mathematics |
Graph theory |
Code |
Science |
Field |
P110 |
Natural sciences and mathematics |
Mathematical logic, set theory, combinatories |
Code |
Science |
Field |
1.01 |
Natural Sciences |
Mathematics |
Graph Theory; Independence; Domination; Graph Classes; Algorithms
Researchers (19)
Organisations (3)
Abstract
In the past decades, Graph Theory has arisen as one of the main areas of contemporary scientific research in mathematics. While its rapid development is partially due to increasing importance of technology and networks where it finds many applications, a number of original and valuable contributions by distinguished researchers established Graph Theory as a mature mathematical discipline. Over the years the Slovenian School of Graph Theory has been an essential part of the development of Graph Theory on the global level. Its international recognition has attained levels comparable to those reached by similar institutions from the technologically most developed countries around the world.
This project proposal is focused on structural and algorithmic aspects of Graph Theory and concentrates on a selection of classical and modern promising research areas at the intersection of Graph Theory with Theoretical Computer Science: the independent set problem in hereditary graph classes; the study of the price of connectivity for variants of independence and domination; the study of graph classes defined by cliques and independent sets, including CIS graphs and equistable graphs; the study of graph classes defined by variants of domination; computational complexity and algorithms for variants of domination. In addition to the above described topics, the project also includes research in other related areas of graph theory, including Algebraic Graph Theory.
Remark: There is a mistake in the title. The title should read: "Independence and domination in structured graph classes".
Significance for science
Apart from Art, Mathematics is the only universal language of human communication present in all civilizations. Abstract mathematical theories are used in Natural Sciences, Engineering, Computer Science and also in Social, Economic and Biomedical Sciences. It has an essential role in many important areas of research, such as Safe Communications, Data Protection, or Decoding of Humane Genome, thus proving that its influence to the very foundations of modern society has reached previously unthinkable levels.
The proposed project stands at the cutting edge of today's research in Graph Theory. The importance of our research goals can be seen from project team members' bibliographies, their citations, and numerous links with scientists around the world. The outcome of this project will have a great impact to the development of the Graph Theory as well as to related fields, and will give a strong impetus to the Slovenian Graph Theory School.
Significance for the country
In view of social and economic changes in the past 20 years, our existence as a fully developed nation in Europe depends as much on preserving our language and culture as it depends on having a highly educated population. Slovenia needs faster technological development. This calls for an even tighter incorporation of mathematics into scientific research and education. Our group already has a lot of experience in this respect and is going to continue to work in this direction also in the framework of the proposed project.
Despite the fact that the proposed research is essentially theoretical in nature, we expect at least some of the obtained results to find applications in the development of algorithms for real-world problems that can be modeled using variants independence and domination problems (see Section 11).
The research group will fully respect principles of the 'European Charter for Researchers' and 'Code of Conduct for the Recruitment of Researchers” in line with the public awareness of researchers and research importance. The research group organizes many formal and informal activities that are addressed to general public and available for non-specialists in the field.
The research group will ensure that research activities are made known to society at large in such a way that they can be understood by non-specialists, thereby improving the public's understanding of science and research. The research group is aware that direct engagement with the public will help researchers to better understand public interest in priorities for science and technology and also the public's concerns. With the proposed project the group will contribute to the reinforcement of public recognition of researchers and their important societal role and EU’s care for researchers.
In this sense, the research group has been organizing, already for the past six years, a series of mathematical evenings, originally called ''UP FAMNIT Excursions into Mathematical universe'' (third week every month) targeted at non-specialists in the field, general public interested in science (from children to adults). Lectures are oriented to popular mathematics, with connection to the modern problems and the role of mathematics in modern technology and daily life (see http://matematicni-izleti.famnit.upr.si/en/).
Most important scientific results
Interim report,
final report
Most important socioeconomically and culturally relevant results
Interim report,
final report