The problem of isomorphism of two graphs and counting the number of nonisomorphic graphs
Loading...
Date
2021
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Faculty of Mathematics and Computer Science Department of Mathematics - Option : Algebra and Discrete Mathematics
Abstract
In this memory we have given some examples of isomorphic and non isomorphic graphs.
Also, we have shown how to use the Polya enumeration theorem to count the number of
non isomorphic graphs on n vertices. Since, if n=50 vertices in the graphs, then there is
n!=50!=304109320171337804361260 8166064768844377641568960512000000000000 permutations
to check if the graphs are isomorphic or not and this number is very large and we say that
NP-hard problem.
Description
Keywords
Polya's theorem, permutation, isomorphic graphs, non isomorphic graphs.