Minor-Minimal Graph Functions

A Mathematica package that contains functions related to finding the forbidden minors of a given graph property. In particular, this package has functions relating to the properties of a graph being apex, edge-apex, or contraction-apex. Additionally in the brute-force-search directory is a Mathematica notebook containing the details how to perform a brute-force search for certain classes of minor-minimal graphs. This package was used to arrive at the results in these papers:

According to the Robertson–Seymour Theorem, given any property of graphs P that is closed under taking minors (if graph G has P, then every minor of G has P), there is some finite obstruction set of graphs such that each obstruction doesn't have P, but every minor of an obstruction has P. This finite set is referred to as the minor-minimal non-P graphs, or sometimes also the forbidden minors of the property P. The significance of this obstruction set is that it completely characterizes the graphs with property P. That is, a graph G has P if and only if it does not have one of these obstructions as a minor.

The classic example of this, preceding the Robertson–Seymour Theorem, is Wagner's Theorem. According to Wagner's Theorem, a graph is planar if and only if it does not contain either K₅ or K_3,3 as a minor. Therefore the two graphs K₅ or K_3,3 are the obstructions to graph planarity.

This Mathematica package was created to help search for the forbidden minors to the properties of a graph being apex, edge-apex, or contraction-apex. Unfortunately the properties edge-apex and contraction-apex aren't closed under taking minors. So while their obstruction sets don't completely characterize the property, they are still worthwhile to search for.

For further reading, see:

• Six variations on a theme: almost planar graphs
  Lipton, Mackall, Mattman, Pierce, Robinson, Thomas, and Weinschelbaum
  Involve, a Journal of Mathematics 11-3 (2018), 413–448.
• The K_n+5 and K_3²,1ⁿ families are obstructions to n-apex
  Thomas W Mattman and Mike Pierce
  Appears in Contemporary Mathematics 689; 2017
• Classifying the Finite Set of Minor-Minimal Non-Apex Graphs
  Mike Pierce, supervised by Dr Thomas Mattman;
  CSU Chico Honors Thesis in Mathematics, 2014

Constants

This package contains the following graphs as constants:

Name	Graph
K5	K5 , the complete graph on five vertices
K6	K6 , the complete graph on six vertices
K33	K3,3 , the complete bipartite graph on two sets of three vertices
J1	The Jørgensen graph

Important Functions

• NonApexGraphQ[g] takes a graph g and yields True if g is non-apex and False otherwise.

  There are also functions NonEdgeApexGraphQ[g] and NonContractionApexGraphQ[g] defined similarly.

• MMGraphQ[P,g] takes a graph property P such that ¬P is closed under taking minors and a graph g and returns True if g is minor-minimal with respect to P and False otherwise. This function is defined pretty simply as

    MMGraphQ[P,g] := Return[P[g] && !MemberQ[P /@ SimpleMinors[g], True]];

  There are three specific implementations of this function. Firstly there is MMNAGraphQ[g] which is simply defined as MMGraphQ[NonApexGraphQ,g]. There are also functions MMNEGraphQ[g] and MMNCGraphQ[g], but these have to defined differently because neither of the properties edge-apex or contraction-apex are closed under taking minors.

• SimpleMinors[g] takes a graph g and returns a list of the simple minors of g. Specifically it returns a list of all distinct graphs that are the result of either deleting an edge, contracting an edge, or deleting a degree-0 vertex in g.

  SimpleMinors[g,n] returns the distinct minors with a minimum vertex degree of n.

Supplementary Functions

• EdgeContract[g,e] contracts the edge e in the graph g. Note that this function is built into Mathematica 10.

• DeleteGraphDuplicates[{g1, ..., gn}] removes duplicate graphs (up to isomorphism) from the list {g₁, …, g_n}.

• GraphSimplify[g] simplifies the graph g so that the result will have no degree-0, -1, or -2 vertices.

  GraphSimplify[] will print an outline of the graph simplification algorithm.

• GraphColor[g] displays the graph g with edges and vertices colored according to their equivalence. In particular, the edges e₁ and e₂ (respectively the vertices v₁ and v₂) will be colored the same if g-e₁ and g-e₂ (respectively g-v₁ and g-v₂) are isomorphic.

• GraphModel[g] displays the graph g in various different layouts with the edges and vertices colored with GraphColor.

  GraphModel[g,n] displays n different layouts of g like above.