# Asymmetric graphs

Bachelor thesis, Simona Dubeková

## Supervisor

doc. RNDr. Tatiana Jajcayová, PhD.

## Consultant

Mgr. Dominika Mihálová

## Annotation

We study non-oriented simple graphs. We call a graph symmetric, if there exists a non-identical permutation of its vertices, which leaves the graph invariant, i.e. a graph is called symmetric if the group of its automorphisms is not trivial. A graph which is not symmetric will be called asymmetric. The degree of symmetry of a symmetric graph is measured by the size of its group of automorphisms. We will measure the degree of asymmetry of an asymmetric graph by the number of vertices which we have to delete to obtain a symmetric graph.

## Goal

We will measure the degree of asymmetry of an asymmetric graph by the number of vertices which we have to delete to obtain a symmetric graph.

## Proposal of the structure of the thesis

• Introduction
• Preliminaries (e.g. including concepts from Graph Theory and Theory of symmetries (automorphism groups))
• Existing softwares/libraries (e.g. more detailed studying GAP, Naughty and Grape systems)
• Implementation
• Results
• Summary
• Future work

## Timeline

• Oct./Nov. 2021 Studying literature from student's books
• 1.11.2021 Bachelor thesis website
• 9.11.2021 Bachelor thesis timeline
• Nov. 2021 Revision concepts and terms
• Nov. 2021 More detailed studying of graph isomorphism
• 30.11.2021 Collecting resources and presenting them
• Dec. 2021 Testing ideas and concepts with small examples
• Jan. 2022 Studying professional articles
• Jan./Mar. 2022 Design algorithms and programs
• Apr./May 2022 Finishing writing a bachelor thesis, proofreading
• 20.5.2022 Submission of the bachelor thesis

## Diary

1. Week 14.2.2022 - 20.2.2022
• Supplement to the chapter Preliminaries by Prim's and Kruskal's Algorithm.
• Programming class Bipartite whose function isBipartite can determine if a given graph is bipartite and testing this function on minimal asymmetric graphs.
2. Week 21.2.2022 - 27.2.2022
• Modification of the chapter Preliminaries and addition of the Induced Subgraph to this section.
• Use of Kruskal's algorithm in finding minimal asymmetric graphs.
3. Week 28.2.2022 - 6.3.2022
• Supplement to the chapter Implementation by unsuccessful code and finding its solution.
• Print graphs to a text file in a format used by GAP.
4. Week 7.3.2022 - 13.3.2022
• Programming of minimal asymmetric graphs and graphs with one less edge/vertex.
• Programming the user interface to the console.
5. Week 14.3.2022 - 20.3.2022
• Drawing minimal asymmetric graphs and graphs with fewer edges/vertices using GAP.
• Programming of minimal asymmetric graphs and graphs with any less edges/vertices.
6. Week 21.3.2022 - 27.3.2022
• Writing a chapter Introduction.
• Programming of minimal asymmetric graphs with one more edge.
7. Week 28.3.2022 - 3.4.2022
• Testing and debugging the program, later fixing small errors.
• Adding the work progress to the chapter Implementation.
8. Week 4.4.2022 - 10.4.2022
• Creation of the Catalogue of minimal asymmetric graphs with iterativly removed vertices.
• Abstract writing for the thesis.
9. Week 11.4.2022 - 17.4.2022
• Filtering isomorphic graphs using GAP.
• Description of all program functions in the Implementation chapter.
10. Week 18.4.2022 - 24.4.2022
• Describing the results of the work in the chapter Results.
11. Week 25.4.2022 - 1.5.2022
• Summary of work results in the chapter Summary.
• Editing all the text of the bachelor thesis including Catalogue.
12. Week 2.5.2022 - 8.5.2022
• Writing README, instructions for using the program.
• Writing and drawing a class diagram for the program.
13. Week 9.5.2022 - 15.5.2022
• Editing and correcting the text, including editing the chapters Preliminaries, Implementation and Results.
• Refactoring and code testing for bachelor thesis.
14. Week 16.5.2022 - 22.5.2022
• Editing and correcting the text, including editing the chapters Introduction, Summary and Abstract.