Loading...
Projects / Programmes source: ARIS

EXPLORATION OF THE INTRINSIC STRUCTURE OF TOWER GRAPHS

Research activity

Code Science Field Subfield
1.01.05  Natural sciences and mathematics  Mathematics  Graph theory 

Code Science Field
P001  Natural sciences and mathematics  Mathematics 

Code Science Field
1.01  Natural Sciences  Mathematics 
Keywords
discrete mathematics; graph theory; theoretical computer science; Tower of Hanoi problem; tower graphs; Sierpiński graphs; integer sequences
Evaluation (rules)
source: COBISS
Researchers (18)
no. Code Name and surname Research area Role Period No. of publicationsNo. of publications
1.  35352  PhD Jernej Azarija  Mathematics  Researcher  2016  25 
2.  17005  PhD Boštjan Brešar  Mathematics  Researcher  2016 - 2018  403 
3.  25993  PhD Sergio Cabello Justo  Mathematics  Researcher  2016 - 2018  218 
4.  32028  PhD Tanja Dravec  Mathematics  Researcher  2016 - 2017  145 
5.  35875  Marjeta Grahek    Technical associate  2017 - 2018 
6.  36905  PhD Andreas Hinz  Mathematics  Researcher  2016 - 2018  66 
7.  05949  PhD Sandi Klavžar  Mathematics  Head  2016 - 2018  1,177 
8.  33510  PhD Jelena Klisara  Mathematics  Researcher  2016  16 
9.  22648  PhD Tadeja Kraner Šumenjak  Mathematics  Researcher  2017 - 2018  119 
10.  31670  PhD Borut Lužar  Computer intensive methods and applications  Researcher  2016 - 2018  183 
11.  37403  PhD Tilen Marc  Mathematics  Researcher  2018  47 
12.  08727  PhD Uroš Milutinović  Mathematics  Researcher  2016 - 2018  348 
13.  01931  PhD Bojan Mohar  Mathematics  Researcher  2016 - 2018  1,002 
14.  16013  PhD Ciril Petr  Mathematics  Researcher  2016 - 2018  68 
15.  22649  PhD Janez Povh  Computer intensive methods and applications  Researcher  2016  341 
16.  11666  PhD Aleksander Vesel  Computer intensive methods and applications  Researcher  2016 - 2018  339 
17.  33306  PhD Sara Sabrina Zemljič  Mathematics  Researcher  2016 - 2018  19 
18.  03430  PhD Janez Žerovnik  Mathematics  Researcher  2017 - 2018  805 
Organisations (2)
no. Code Research organisation City Registration number No. of publicationsNo. of publications
1.  0101  Institute of Mathematics, Physics and Mechanics  Ljubljana  5055598000  20,216 
2.  2784  Faculty of Information Studies in Novo mesto  Novo mesto  3375650  6,110 
Abstract
The main goal of the project is to deepen the understanding of Hanoi graphs, Sierpiński graphs, and related classes of graphs. The specific topics we plan to cover are 1. Metric properties of tower graphs; 2. Algorithms and computer experiments on tower graphs; 3. Structural properties of tower graphs; 4. Investigation of tower graphs relevant in (neuro-)psychology and elsewhere; 5. Classification of Sierpiński-like graphs; and 6. Second edition of the book ''The Tower of Hanoi—Myths and Maths''.   The core of our research will be performed in the classical theorem-proof manner. However, due to the delicate structure of Hanoi graphs we will also concentrate on numerical evidence to obtain eventually provable results. The main goal of our computational experiments will be to compute distances and metric invariants in Hanoi graphs. We will also employ computer experiments for the Star Tower of Hanoi graphs and for different structure properties of Hanoi and Sierpiński graphs, like for instance the packing chromatic number of Sierpiński graphs.   Our plan is to investigate invariants and other problems on Sierpiński graphs and related classes of graphs, including those in the general framework introduced by Hasunuma, that are of recent interest to the research community. In this way we will deepen the understanding of these classes of graphs and at the same time open them to other researchers. The problems that we plan to attack include complexity (that is, the number of spanning trees), the number of matchings, the packing chromatic number, and the game domination number.   For Hanoi graphs the situation is much more delicate. For instance, no 1-perfect codes exist in non-trivial Hanoi graphs and many graph invariants which were determined for Sierpiński graphs are still unknown for Hanoi graphs, such as the domination number and the independence number. Our plan is to attack these invariants and obtain good upper and lower bounds for them because it seems that exact values are intrinsically difficult to obtain.   The Tower of London is the central solitaire game used by (neuro-)psychologists to test cognitive abilities. Since most graph invariants are unknown for London graphs (for instance, already the calculation of their sizes leads to intriguing number theoretical questions), our primary goal is to determine (or to bound) graph invariants of those London graphs which are of interest for (neuro-)psychologists. Tower graphs are also applicable elsewhere. A couple of months ago, chemical self-assembly of ''Sierpiński triangles'' was reported on. Our goal with respect to this application is to understand the self-assembly and to see how our understanding of Sierpiński-like graphs can be used to make new insights into this application.    Graphs whose drawings can be viewed as approximations to the famous Sierpiński triangle have been studied intensely in the past 25 years in numerous different scientific areas. Therefore it is not surprising that different names have been used for the same object and the same name for different objects. Our aim is to bring some order into this zoo of Sierpiński-like graphs and to summarize the properties of the most important species.   The second edition of the book ''The Tower of Hanoi—Myths and Maths'' is also planned. It will contain a number of updates, but also some more introductory topics from discrete mathematics and mathematics general in order to be more suitable for classroom usage. The second edition was in particular triggered by progress on a problem open for more than a century. This development, initiated by Thierry Bousch from Paris, will be a central topic of our project. We are in contact with the author and may wish to incorporate him into our own efforts.
Significance for science
The project belongs to basic research in the area of mathematics and related fields such as computer science. 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 impact of our results. The problems we plan to attack are central in the area and at the same time have applications in other scientific fields, for instance in neuro-psychology and in chemistry.  The problems that we propose to investigate are not only unsolved, but having in mind the extended recent interest into Sierpiński graphs (including Hanoi graphs), they are also relevant. We expect to publish several papers in key journals from the area of discrete mathematics related to the topics of the proposed project. We will also present our results at relevant international conferences. The work on the project will serve as a perfect basis for a second edition of the 2013 Springer book The Tower of Hanoi—Myths and Maths. That the second edition is a desirable and realistic goal of the project can be justified by the recent very quick development of the area and by a dozen of very positive reviews that the book has received. Also, the large scale computer experiments can serve as a model for future algorithms and computational methods.
Significance for the country
The proposed project is in the area of pure mathematics, therefore it is difficult to measure its direct impact on the economy and society. However, the project is oriented to encourage the integration of young researchers and students into its activities. In this way it allows for a long-term continuation of the research quality in mathematics, which in turn has an important impact on the quality of the university programs in mathematics and other sciences. As a direct impact of the project we can also consider the fact that it supports a continuation of research contacts of Slovenian scientists with the most up-to-date developments.
Most important scientific results Interim report, final report
Most important socioeconomically and culturally relevant results Interim report, final report
Views history
Favourite