Results 1 to 2 of 2

Math Help - Minimal embeddable Graph

  1. #1
    Newbie
    Joined
    May 2012
    From
    Cologne
    Posts
    1

    Minimal embeddable Graph

    Given a graph G. A graph H is called embeddable into G if a subset of G is equal to H.

    For a given graph G we want to find the minimal (least number of edges (but of course at most as many vertices as G)) graph that is not embeddable.

    Can someone tell me what the general approach to those probelms is (if there is)?

    In the specific case G consists of c "core" vertices which form a complete subgraph and x outer vertices each connected exactly to all os the c core vertices.

    I already figured out that this specific graph is complete up to the missing vertices between the x outer vertices. Therefore those must be targetes, eg with cycles or the like but I am not quite sure.

    Thanks,
    Trome
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    May 2012
    From
    Poland
    Posts
    1

    Re: Minimal embeddable Graph

    If G isn't complete, then minimal graph that is not embeddable into G exist and have at least \omega(G) +1 vertices. Now you have to add some edges (with new vertices) to the maximum clique (of course you can also remove some edges from that).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Minimal polynomials
    Posted in the Advanced Algebra Forum
    Replies: 8
    Last Post: April 5th 2011, 11:15 PM
  2. Minimal functions
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: July 7th 2010, 08:36 PM
  3. Minimal Polynomials
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: February 3rd 2010, 10:11 AM
  4. Minimal polynomial
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: October 7th 2009, 08:34 PM
  5. Minimal Polynomial....
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: March 11th 2009, 09:04 AM

Search Tags


/mathhelpforum @mathhelpforum