Projects / Programmes
Contemporary and New Metric Concepts in Graph Theory
| 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 |
metric graph theory; shortest paths; metric dimensions; partial cubes; orienteted matroids; convexity; packing chromatic number
Researchers (20)
Organisations (3)
Abstract
Graphs form a natural mathematical model for an impressive spectrum of problems arising in as different areas as biology, computer science, operations research, and a variety of social sciences. In particular, graphs are the underlying model in the investigations of complex networks and big data, which are hot topics in contemporary science. In many of these investigations, distances between the nodes and concepts involving the metric structure give the essential information about the network properties one is interested in. The intrinsic metric nature of graphs therefore makes metric properties of graphs a central topic in graph theory. The main goal of the project is to follow the recent trends in metric graph theory and being a step ahead by proposing and investigating concepts that will bring new insights, model applications, and give directions for future developments in the area.
Main objectives of the project are investigations in the following areas of metric graph theory:
(1) Shortest paths and their applications. We will investigate the strong geodetic number from different points of view, in particular try to determine exactly or improve the best known bounds on the strong geodetic number of grid-like graphs. We will also study the general position problem on Sierpiński graphs and on important interconnection networks such as hypercubes and grid-like architectures, as well as their subclasses.
(2) Metric dimensions. We will study how the structure of graphs influences the metric, edge metric and mixed metric dimension. Studying critical graphs will help to understand the influence of the structure on the values of the dimensions. We will be interested how the edge metric and the mixed metric dimension behave on product graphs. Computational aspect of these two dimensions will also be studied. We will investigate the partition dimension and the k-metric antidimension. In particular, we conjecture that the partition dimension of the rooted product of two arbitrary graphs is at most the sum of the partition dimensions of both graph factors minus one.
(3) Metrically defined classes of graphs. Several related classes will be studied, in particularcube-complements, partial cubes, and exact distance graphs. We will use cube-complements to further understand generalized Fibonacci cubes and related classes. We will use the connection between oriented matroids and partial cubes to answer some open problems about oriented matroids as well as to analyze the implications this has on partial cubes. In particular, we will focus on long standing questions about so called corners of such structures and their connection to the famous Las Vergnas conjecture. We plan to study the concept of exact distance graphs in a completely general setting.
(4) Convexities. The focus will be on the toll number which will be considered on general graphs and compared with other convexities. We will also investigate invariants that were already considered for geodesic convexity, for example the convexity number.
(5) Selected additional metric concepts. Here we will investigate (i) the packing chromatic number, in particular critical graphs with respect to the invariant and the packing chromatic number of subcubic graphs; (ii) the structure of Voronoi diagrams in graphs, in particular exploring new applications of Voronoi diagrams on planar graphs; (iii) radio k-labelings, where we plan to improve bounds or find exact radio k-labeling numbers for different families of graphs; and (iv) distance based queries in graphs, where we will search for new data structures to handle distance-based queries.
Significance for science
The project belongs to basic research in the area of mathematics. Problems on which we plan to work are internationally important, which can in particular be justified by our bibliography from the last period, by the (citation) impact of our results, and by the bibliography presented in the application. From the latter it is evident that the problems are central in the area of metric graph theory and at the same time have applications in other scientific fields, specifically in areas like biology, computer science, chemistry, and social sciences. Moreover, we propose several new ideas and concepts which are expected to open new research areas in the field of metric graph theory. The obtained results are planned to be published in leading journals from the area of discrete mathematics and will be presented at international scientific conferences, in part as invited, plenary lectures. In this way we will further increase the international role of the Slovenian graph theory school, in particular its role in metric graph theory.
Significance for the country
The project belongs to basic research in the area of mathematics. Problems on which we plan to work are internationally important, which can in particular be justified by our bibliography from the last period, by the (citation) impact of our results, and by the bibliography presented in the application. From the latter it is evident that the problems are central in the area of metric graph theory and at the same time have applications in other scientific fields, specifically in areas like biology, computer science, chemistry, and social sciences. Moreover, we propose several new ideas and concepts which are expected to open new research areas in the field of metric graph theory. The obtained results are planned to be published in leading journals from the area of discrete mathematics and will be presented at international scientific conferences, in part as invited, plenary lectures. In this way we will further increase the international role of the Slovenian graph theory school, in particular its role in metric graph theory.
Most important scientific results
Interim report
Most important socioeconomically and culturally relevant results
Interim report
