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

Timeline

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
    • Downloading data from the program to analyze the results of work.
    • 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.
    • Adding Acknowledgements.
  15. Week 23.5.2022 - 29.5.2022
    • Final correcting the text of bachelor thesis.
  16. Week 30.5.2022 - 3.6.2022
    • Printing and submission of bachelor thesis.

Bibliography

For download