Projects / Programmes
Catalogue of graphs with high level of symmetry
| Code |
Science |
Field |
Subfield |
| 1.01.00 |
Natural sciences and mathematics |
Mathematics |
|
| Code |
Science |
Field |
| P001 |
Natural sciences and mathematics |
Mathematics |
graph, group, automorphism, symmetry, edge-transitive graphs
Researchers (15)
Organisations (1)
Abstract
Graphs are abstract mathematical objects that are often used as models of structures and phenomena arising in science. Highly symmetric structures usually posses many nice and desirable features. This motivates the study of graphs with high level of symmetry, such as vertex- or edge-transitive graph (A graph is vertex- or edge transitive if its automorphism groups acts transitively on the vertices or edges, respectively.)
It is difficult to claim that a certain class of combinatorial objects is well understood, unless we have practical means by which we can enumerate all the members of this class, up to a prescribed size. More precisely, the state of knowledge about the class of arc-transitive (or edge-transitive, or vertex-transitive etc.) graphs is not yet satisfactory, for as long as we are unable to find all representatives of this class, up to a given size.
Attempts of constructing calagoues of graphs with high level of symmetry started in early 1930s, when Foster started collecting examples of arc-transitive graphs of valence 3. His work, now known as Foster census, has been a valuable source of information for graph and group theorists for many decades. It is only recently that his work has been superceded by the work of Conder and Dobcsáni, who used computers and some clever group theoretical techniques to contruct a complete list of all arc-transitve trivalent graphs on up to 768 vertices.
Extending the catalogue to graphs of other valences and symmetry types is one of the central goals of the proposed project. Since graphs of valence larger than 3 exibit much more complex combinatorial structure, new tools and approaches will need to be invented. We thus strongly believe that pursuing the main goal of the project will motivate new research directions in certain areas of combinatorics and group theory, and thus increase general understanding of graphs with prescibed types of symmetry. The main objective of the proposed project can therefore be understood both as the final goal as well as the motivation and guideline for a more general research of symmetry properties of graphs, and symmetry in general.
Significance for science
Pursuing the main goal of the project has motivated new research directions in certain areas of combinatorics and group theory. In particular, the study of graphs with large vertex-stabilisers has increased our knowledge of graphs with prescribed types of symmetry, and contribute to general understanding of the notion of symmetry in general. The final result of the project, the catalogue of highly symmetric graphs, will offer a valuable source of information for graph theorists as well as for researchers in other areas within and outside mathematics.
Significance for the country
It is difficult to claim that results of the project have immediate applications in industry. However, the catalogue of highly symmetrical graphs might find applications in in Slovenian pharmaceutical and chemical industry, as well as in electrical engineering, network design etc.
What is perhaps more important is that the topic of the project makes a part of a current mainstream research in algebraic combinatorics, and the results have a potential to be published in the high ranking mathematical journals. The project will even increase a very high reputation of the Slovenian school of algebraic combinatorics and graph theory, and thus contribute to promotion of Slovenian science in general. The excellence of the obtained results will attract foreign scholars and students, and open opportunities for our researchers to visit distinguished mathematical centres abroad.
Most important scientific results
Annual report
2008,
2009,
final report,
complete report on dLib.si
Most important socioeconomically and culturally relevant results
Annual report
2008,
2009,
final report,
complete report on dLib.si
