Difference between revisions of "Nearly Complete Graph"
Owen Vaughan (talk | contribs) (Created page with "A graph is a collection of vertices and edges. A graph is complete if there is an edge connecting every vertex to every other vertex. A graph is nearly complete if it can be o...") |
Owen Vaughan (talk | contribs) |
||
| Line 16: | Line 16: | ||
==External Links== | ==External Links== | ||
| − | * [https://link.springer.com/article/10.1007/BF01836527 | + | * [https://link.springer.com/article/10.1007/BF01836527 The genus of nearly complete graphs-case 6, Jonathan L. Gross, 1975] |
Revision as of 16:09, 30 December 2019
A graph is a collection of vertices and edges. A graph is complete if there is an edge connecting every vertex to every other vertex. A graph is nearly complete if it can be obtained by removing a small number of edges from a complete graph.
What follows is a mathematically precise definition of a nearly complete graph.
Consider a graph G with vertices v, edges e, genus g, and faces f.
Euler's lower bound is defined to be
X = (e - 3f + 6)/6 .
If a graph is complete then g is equal to the lowest integer greater than or equal to X. Consider a number p such that the removal of any set of p or fewer edges from a complete graph yields a connected graph with g = X. The maximum value of p is denoted by NC(v). It depends only on the vertex number.
A graph with vertices v is nearly complete if it can be constructed by starting with a complete graph with the same number of vertices and removing up to NC(v) edges.