Graph minor

In graph theory minors are some graphs that can be obtained by contraction of edges of any other graph. The minor relation is in addition to the subgraph relation and the subgraph relation one of the most important relations of graph theory and allows many profound phrases such as Kuratowski's theorem or the theorem of Robertson - Seymour.

  • 2.1 Minor
  • 2.2 Topological Minor

Definition

All these graphs are always assumed to be simple.

Minor

If we replace the vertices of a graph by disjoint connected graphs and edges we obtain a new graph, which is called ( for inflated, inflated by - edges, in German. This name derives from the fact that by replacing the corners by graphs original graph "bigger" is ). Now includes a one graph, it is called a minor of.

Topological minor

Is a graph and a graph of sub-division (that is, a graph shows by dividing edges ), it is called a (that is topologically ). The corners of which are also included, branch vertices are called, all other vertices are called subdivision corners. Branch vertices inherit from their degree, subdivision corners are all of degree two. Now includes a one graph, it is called a topological minor of.

Equivalent definitions

The following definitions are also found occasionally in the literature:

A graph is called a minor of if a subgraph contains, seen from the edge due to contraction.

A graph is called topological minor of if a subdivision graph of contains.

Example

Minor

Links outside the complete graph with three vertices is shown. This is caused by contraction of edges from the graph, which in turn is included. is thus a minor of.

Topological minor

Links outside the complete graph with three vertices, center, a subdivision graph is shown. The subdivision graph but is included in the graph, ie it is a topological minor of.

Properties

  • The minor relation is defined minor of an order relation on the finite graph, ie, it is reflexive, transitive and anti-symmetric ( the same is true for the topological minor relation ).
  • Every subgraph of a graph is a minor of this graph.
  • Each one is also. For every topological minor is also an ordinary Minor.
  • The minor relation defines a well- quasi-ordering on the finite graph. This set is also known as Minorentheorem.
Edge contraction Graph (mathematics)#Simple graph Robertson–Seymour theorem Wolfram Research Michiel Hazewinkel Encyclopedia of Mathematics
574506
de