How many graph isomorphic classes are there given n vertices?

  • Context: Graduate 
  • Thread starter Thread starter Dragonfall
  • Start date Start date
  • Tags Tags
    Classes Graph
Click For Summary
SUMMARY

The discussion centers on the enumeration of graph isomorphic classes for undirected simple graphs with n vertices, referencing the OEIS sequence A000088. The participants express interest in understanding the derivation of the formulas provided in the sequence. The conversation highlights the need for clarity on whether brute force methods were employed in obtaining these formulas.

PREREQUISITES
  • Understanding of graph theory concepts, specifically isomorphism.
  • Familiarity with undirected simple graphs.
  • Knowledge of the Online Encyclopedia of Integer Sequences (OEIS) and its usage.
  • Basic combinatorial mathematics for deriving formulas.
NEXT STEPS
  • Research the derivation methods for OEIS sequence A000088.
  • Explore combinatorial techniques for counting graph isomorphism classes.
  • Learn about brute force algorithms in graph enumeration.
  • Investigate software tools for graph theory analysis, such as SageMath.
USEFUL FOR

Mathematicians, computer scientists, and researchers interested in graph theory, particularly those focusing on graph enumeration and isomorphism.

Dragonfall
Messages
1,023
Reaction score
5
I'm talking about undirected simple graphs.
 
Mathematics news on Phys.org
I believe this is
http://www.research.att.com/~njas/sequences/A000088
 
Last edited by a moderator:
Thanks. I'd like to see how those formulas were obtained, though.
 
Brute force??
 
The formula is at the bottom of the link above.
 
Yes but how do you derive said formula?
 

Similar threads

Undergrad Classify the isomorphism of a graph
  • · Replies 3 ·
Replies
3
Views
2K
Undergrad The number of intersection graphs of ##n## convex sets in the plane
  • · Replies 2 ·
Replies
2
Views
1K
Undergrad Prove that a given graph contains a cycle using induction (Graph Theory)
  • · Replies 7 ·
Replies
7
Views
3K
Undergrad Edge connectivity of a graph given the number of edge disjoint paths
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Finding the dependence of maximum vertex degree on k-colorability
  • · Replies 1 ·
Replies
1
Views
2K
MHB How many girls were there in the class?
  • · Replies 2 ·
Replies
2
Views
1K
Undergrad Finding the chromatic number of a graph with biconnected components
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad How to prove that 2 graphs are not isomorphic?
  • · Replies 4 ·
Replies
4
Views
11K
MHB Number of students in a class at first
  • · Replies 3 ·
Replies
3
Views
2K
Graduate Counting edge numbers in bipartite graphs
  • · Replies 1 ·
Replies
1
Views
1K