A definition of minor (in graph theory)

Many people I talk to about graph theory feel some uneasiness when it comes to the notion of “minor”. I want to try to alleviate this feeling by providing the definiton of minor that I work with.

First an easy definition. If G is a simple, undirected graph and S, T\subseteq V(G) are non-empty and disjoint, we say that S, T are connected to each other if there are s\in S, t\in T such that \{s,t\}\in E(G).

Let G, H be simple, undirected graphs. We say that G is a minor of H if there is a collection {\cal S} of non-empty, mutually disjoint, and connected subsets of V(H) and a bijection \varphi:V(G) \to {\cal S} such that

whenever v,w\in V(G) and \{v,w\}\in E(G) then the sets \varphi(v) and \varphi(w) are connected to each other in H.

Advertisements

About dominiczypen

I'm interested in general topology, order theory, and graph theory. This link takes you to my preprints on arXiv.
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s