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 |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page