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 K5 or K3,3 as a minor. Therefore the two graphs K5 or K3,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 Kn+5 and K32,1n 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
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 |
-
NonApexGraphQ[g]
takes a graph g and yields True if g is non-apex and False otherwise.There are also functions
NonEdgeApexGraphQ[g]
andNonContractionApexGraphQ[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 asMMGraphQ[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 asMMGraphQ[NonApexGraphQ,g]
. There are also functionsMMNEGraphQ[g]
andMMNCGraphQ[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.
-
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 {g1, …, gn}. -
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 e1 and e2 (respectively the vertices v1 and v2) will be colored the same if g-e1 and g-e2 (respectively g-v1 and g-v2) are isomorphic. -
GraphModel[g]
displays the graph g in various different layouts with the edges and vertices colored withGraphColor
.GraphModel[g,n]
displays n different layouts of g like above.