If . How many non-isomorphic graphs are there? In total, there are edges but not all compose non-isomorphic graphs. For example, and but they are isomorphic.

Printable View

- September 3rd 2006, 06:46 AMThePerfectHackerGraphs....up to isomorphism.
If . How many non-isomorphic graphs are there? In total, there are edges but not all compose non-isomorphic graphs. For example, and but they are isomorphic.

- September 3rd 2006, 04:15 PMPlato
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. - September 7th 2006, 12:38 PMrgep
This is sequence A000088 in the Encyclopaedia of Integer Sequences.

- September 8th 2006, 11:44 AMThePerfectHacker
I was considering another way to kill this problem. Perhaps, we should consider the non-isomorphic adjancey matricies for n vertices?