# Minimal embeddable Graph

• May 13th 2012, 01:18 PM
Trome
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
• May 15th 2012, 09:04 AM
dakurels
Re: Minimal embeddable Graph
If G isn't complete, then minimal graph that is not embeddable into G exist and have at least $\displaystyle \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).