Results 1 to 2 of 2

Math Help - Find the number of graphs such that...

  1. #1
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1

    Find the number of graphs such that...

    Find the number of undirected graphs on n vertices such that, whenever there is a path a_1 \leftrightarrow a_2 \leftrightarrow ... \leftrightarrow a_k joining the vertices a_1,...,a_k, then there is a complete graph on a_1,...,a_k.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by Bruno J. View Post
    Find the number of undirected graphs on n vertices such that, whenever there is a path a_1 \leftrightarrow a_2 \leftrightarrow ... \leftrightarrow a_k joining the vertices a_1,...,a_k, then there is a complete graph on a_1,...,a_k.
    I can't think of any hints that wouldn't be completely and utterly cryptic, so I'll just sort of give you the logical leap bit, and is hopefully only a wee bit cryptic...presuming, of course, you didn't quite get the leap bit...

    Basically, what you want to do find out how many ways there are of partitioning and n-element set.

    I'm sure you can solve the problem from there.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. interval graphs and chromatic number
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 22nd 2010, 02:52 PM
  2. Number of Graphs
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: November 18th 2010, 08:15 AM
  3. Replies: 3
    Last Post: November 17th 2010, 06:59 AM
  4. Number of directed graphs with no cycles
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: May 23rd 2009, 06:18 AM
  5. Find where the two graphs intersect.
    Posted in the Calculus Forum
    Replies: 4
    Last Post: May 16th 2008, 10:26 PM

Search Tags


/mathhelpforum @mathhelpforum