# University of Twente Student Theses

## Counting and enumerating 2-isomorphic graphs

Heuven, P.J.B.
(2023)
*Counting and enumerating 2-isomorphic graphs.*

PDF
1MB |

Abstract: | This research aims to find every 2-isomorphic graph of a given 2-connected graph G. The main results of this research include a formula for the number of different 2-isomorphic graphs of G and how to enumerate every 2-isomorphic graph efficiently. These results are achieved by utilizing Whitney switches and Whitney's theorem, which provide a way to find any 2-isomorphic graph of G. A Whitney switch can only be applied on a pair of vertices that represent a vertex cut. The SPQR-decomposition is used to find these pairs of vertices. The SPQR-decomposition creates a SPQR-tree of a 2-connected graph and differentiates 2-connected and 3-connected parts of a graph. The pairs of vertices that represent a vertex cut are not found in 3-connected parts of a graph. This property is used to derive the number of different 2-isomorphic graphs based on the SPQR-tree of G. This derivation is also used to design an algorithm that enumerates every 2-isomorphic graph of G with time complexity O(|V|+N|E|), where N is the number of different 2-isomorphic graphs. |

Item Type: | Essay (Bachelor) |

Faculty: | EEMCS: Electrical Engineering, Mathematics and Computer Science |

Subject: | 31 mathematics |

Programme: | Applied Mathematics BSc (56965) |

Link to this item: | https://purl.utwente.nl/essays/96240 |

Export this item as: | BibTeX EndNote HTML Citation Reference Manager |

Repository Staff Only: item control page