Results 1 to 4 of 4

Math Help - Graphs....up to isomorphism.

  1. #1
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9

    Graphs....up to isomorphism.

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Jun 2005
    Posts
    295
    Awards
    1
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    I was considering another way to kill this problem. Perhaps, we should consider the non-isomorphic adjancey matricies for n vertices?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. An isomorphism
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: February 24th 2011, 12:33 AM
  2. Isomorphism (Help)
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: November 3rd 2010, 09:30 AM
  3. isomorphism
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 10th 2010, 08:50 AM
  4. Check two graphs are isomorphism or not!
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 10th 2010, 03:03 AM
  5. Replies: 4
    Last Post: February 14th 2010, 03:05 AM

Search Tags


/mathhelpforum @mathhelpforum