Graphs....up to isomorphism.

**ThePerfectHacker** · September 3rd 2006, 05:46 AM

If $|V(G)|=n$ . How many non-isomorphic graphs are there? In total, there are $\frac{n(n-1)}{2}$ edges but not all compose non-isomorphic graphs. For example, $G=(\{v_1,v_2,v_3\},\{v_1v_2\})$ and $G=(\{v_1,v_2,v_3\},\{v_1v_3\})$ but they are isomorphic.

**Plato** · September 3rd 2006, 03:15 PM

There is quite a good discussion of the problem in the first chapter of the text, GRAPHS: An Introductory Approach by Wilson & Watkins. (Because of your location, you can find it in most mathematics libraries.) It turns out that the problem is different for labeled graphs than for unlabeled graphs. You seem to be using labeled graphs, graphs having named vertices . For unlabeled graphs Polya solve the problem in 1935. Wilson & Watkins give what they call “graph cards” at the end of chapter 1: they list all non-isomorphic unlabeled graphs of order 1 to 6. There are 153 non-isomorphic unlabeled graphs of order 6.

**rgep** · September 7th 2006, 11:38 AM

This is sequence A000088 in the Encyclopaedia of Integer Sequences.

**ThePerfectHacker** · September 8th 2006, 10:44 AM

I was considering another way to kill this problem. Perhaps, we should consider the non-isomorphic adjancey matricies for n vertices?

Thread: Graphs....up to isomorphism.

LinkBack

Thread Tools

Display

Graphs....up to isomorphism.

Similar Math Help Forum Discussions

An isomorphism

Isomorphism (Help)

isomorphism

Check two graphs are isomorphism or not!

Isomorphism proves: f and g are isomorphisms, prove f + g is an isomorphism

Search Tags