<p>Let $G$ and $H$ be graphs with the following relationship: for some $k$, after you perform at least $k$ arbitrary subdivisions of the edges of $G$ (or the edges produced through subdivision), $H$ must be a minor. What do you call the relationship between $G$ and $H$?</p>

<p>For example, consider a claw with each edge subdivided once and a claw with one edge subdivided twice. You can subdivide any edge of the former to produce a graph for which the latter is a minor $(k = 1)$. Is anyone writing about this or has it been given a name?</p>

CC BY-SA 3.0
2011-06-13T16:51:55.737Z
Are you sure you are stating this correctly?  Isn't the first paragraph simply "$H$ is a minor of $G$"?  Why not add a bunch of isolated vertices, making $k$ irrelevant?
Andrew D. King
CC BY-SA 3.0
2011-06-13T19:27:58.147Z
Are you looking for [topological minor](http://en.wikipedia.org/wiki/Minor_%28graph_theory%29#Topological_minors)?
Aaron Sterling
CC BY-SA 3.0
2011-06-13T19:50:14.320Z
@Andrew: you're right, the first paragraph does have a misstatement. I'll edit.
Eli
CC BY-SA 3.0
2011-06-13T23:08:13.413Z
Is this a correct way to rephrase the relationship you want to describe: "H is a minor of almost all subdivisions of G," where "almost all" means "all but finitely many."
Robin Kothari
CC BY-SA 3.0
2011-06-14T11:26:03.957Z
@Robin, I think the condition is weaker: after fixing some $k$, after he construct the upward set, he's requiring that $H$ be a minor, for all such sets.
Suresh Venkat
CC BY-SA 3.0
2011-06-14T12:59:14.283Z
@Suresh: Do you mean the relationship is parametrized by k? Like "H is a minor of every k-subdivision of G"? Where a k-subdivision of G is any graph obtained from G after k elementary subdivisions. It sounded to me like the relationship described only required the existence of such a k. @Eli: What is the correct interpretation of your question?
Robin Kothari
CC BY-SA 3.0
2011-06-14T13:40:38.797Z
I have never heard of this, but I believe it is equivalent to saying that if you subdivide any edge of $G$ $k$ times, $H$ will then be a minor.
Andrew D. King
CC BY-SA 3.0
2011-06-14T14:55:53.533Z
@Robin, I believe so, with "k" replaced by "at most k"
Suresh Venkat
CC BY-SA 3.0
2011-06-21T20:09:13.270Z
Andrew is correct in what I intend.
Eli
<graph-theory><co.combinatorics><terminology><graph-minor>
Name for relationship where one graph is a minor usually implies another is?
Eli
# Name for relationship where one graph is a minor usually implies another is?

(Asked by: username_0 on 2011-06-13)

Let $G$ and $H$ be graphs with the following relationship: for some $k$, after you perform at least $k$ arbitrary subdivisions of the edges of $G$ (or the edges produced through subdivision), $H$ must be a minor. What do you call the relationship between $G$ and $H$?

For example, consider a claw with each edge subdivided once and a claw with one edge subdivided twice. You can subdivide any edge of the former to produce a graph for which the latter is a minor $(k = 1)$. Is anyone writing about this or has it been given a name?

**Tags:** graph-theory, co.combinatorics, terminology, graph-minor

> **Comments:**
> **username_1**: Are you sure you are stating this correctly?  Isn't the first paragraph simply "$H$ is a minor of $G$"?  Why not add a bunch of isolated vertices, making $k$ irrelevant?  
> **username_2**: Are you looking for [topological minor](http://en.wikipedia.org/wiki/Minor_%28graph_theory%29#Topological_minors)?  
> **username_0**: @Andrew: you're right, the first paragraph does have a misstatement. I'll edit.  
> **username_3**: Is this a correct way to rephrase the relationship you want to describe: "H is a minor of almost all subdivisions of G," where "almost all" means "all but finitely many."  
> **username_4**: @Robin, I think the condition is weaker: after fixing some $k$, after he construct the upward set, he's requiring that $H$ be a minor, for all such sets.  
> **username_3**: @Suresh: Do you mean the relationship is parametrized by k? Like "H is a minor of every k-subdivision of G"? Where a k-subdivision of G is any graph obtained from G after k elementary subdivisions. It sounded to me like the relationship described only required the existence of such a k. @username_0: What is the correct interpretation of your question?  
> **username_1**: I have never heard of this, but I believe it is equivalent to saying that if you subdivide any edge of $G$ $k$ times, $H$ will then be a minor.  
> **username_4**: @Robin, I believe so, with "k" replaced by "at most k"  
> **username_0**: Andrew is correct in what I intend.  

---

## 0 answers

