show/hide this revision's text 2 This post was dealing with topological minors, not the ones mentionned in the question.. Fixed !

Hello !

Well, first I do not think I read about this in any book I read. Which is not really a surprise, as I did not find many books mentionning graph minors. You will find a chapter about minors at the end of Diestel's book (http://www.math.uni-hamburg.de/home/diestel/), and I think we will otherwise have to wait for Bruce Reed's book on Graph Minors.

To focus on your problem, you can for example say that this property does not hold when your graph is not a forest : you can through edge subdivision arbitrarily increase the girth (length of a smallest cycle) of any graph.It means that if you think finding H (with a cycle) as a minor if G is the same as finding it as a subgraph, then you expect to find in H a cycle of length k. You can now subdivide the edges of G k times, to remove any possible cycle of length <= k, which of course changes nothing to minor containment.

Topological Minors :

The same fact that tells you $K_{1,3}$ has this property can be used to prove that for any $k$, $K_{1,k}$ also has this property.

Actually, let $H$ be any graph with two vertices $u,v$ of degree at least 3. Let $d(u,v)$ be their distance in $H$. Now take a graph $G$ having $H$ as a minor, and subdivide all its edges $d(u,v)+1$ times. Well, now you will not find two vertices of $G$ of degree larger than 3 at distance less than $d(u,v)$, so even though $G$ still contains $H$ as a minor, it does not contain it as a subgraph.

So in order to have this property, you must have a most one vertex of degree larger than 3, and I think this is an equivalence.

Usual minors :

In this case, for any graph $H$, there exists a graph $G$ having $H$ as a minor such that $G$ has maximal degree $3$. So there is no need to look at anything different from $K_{1,3}$ or a path to answer your question :-)

I can not help with your set version for the moment, though... :-)

Nathann

show/hide this revision's text 1

Hello !

Well, first I do not think I read about this in any book I read. Which is not really a surprise, as I did not find many books mentionning graph minors. You will find a chapter about minors at the end of Diestel's book (http://www.math.uni-hamburg.de/home/diestel/), and I think we will otherwise have to wait for Bruce Reed's book on Graph Minors.

To focus on your problem, you can for example say that this property does not when your graph is not a forest : you can through edge subdivision arbitrarily increase the girth (length of a smallest cycle) of any graph.It means that if you think finding H (with a cycle) as a minor if G is the same as finding it as a subgraph, then you expect to find in H a cycle of length k. You can now subdivide the edges of G k times, to remove any possible cycle of length <= k, which of course changes nothing to minor containment.

The same fact that tells you $K_{1,3}$ has this property can be used to prove that for any $k$, $K_{1,k}$ also has this property.

Actually, let $H$ be any graph with two vertices $u,v$ of degree at least 3. Let $d(u,v)$ be their distance in $H$. Now take a graph $G$ having $H$ as a minor, and subdivide all its edges $d(u,v)+1$ times. Well, now you will not find two vertices of $G$ of degree larger than 3 at distance less than $d(u,v)$, so even though $G$ still contains $H$ as a minor, it does not contain it as a subgraph.

So in order to have this property, you must have a most one vertex of degree larger than 3, and I think this is an equivalence.

I can not help with your set version for the moment, though... :-)

Nathann