Difference between revisions of "Nearly Complete Graph"

 
(3 intermediate revisions by the same user not shown)
Line 1: Line 1:
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.
+
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 relative to the size of the graph.  
  
 +
== Mathematical Definition ==
  
What follows is a mathematically precise definition of a nearly complete graph.
+
Consider a graph with vertices <math>v</math>, edges <math>e</math>, and genus <math>g</math>.
  
Consider a graph ''G'' with vertices ''v'', edges ''e'', and genus ''g''.
+
Calculate
  
Euler's lower bound is defined to be
+
:<math> X = (e - 3v + 6)/6 </math>.
  
''X'' = (''e'' - 3''v'' + 6)/6 .
+
Let <math>\lceil X \rceil</math> denote the smallest integer greater than or equal to <math>X</math>. All graphs satisfy Euler's lower bound
  
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.
+
:<math> g \geq \lceil X \rceil</math> .
  
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.
+
For complete graphs <math> g =\lceil X \rceil</math> and the bound is saturated.  
  
 +
One may start with a complete graph and remove <math>p</math> edges such that the remaining graph satisfies
 +
* Euler's lower bound is saturated <math> g =\lceil X \rceil</math>
 +
* The graph is connected
 +
Let <math> NC(n) </math> denote the maximum number of possible edge removals from the complete graph <math>K_n</math> such that the above two properties hold no matter which edges are removed. A graph with <math>n</math> vertices is ''nearly complete'' if it can be obtained by removing <math> p \leq NC(n) </math> edges from the complete graph <math>K_n</math>.
  
==External Links==
+
==References==
* [https://link.springer.com/article/10.1007/BF01836527 The genus of nearly complete graphs-case 6, Jonathan L. Gross, 1975]
+
* [https://link.springer.com/article/10.1007/BF01836527 ''The genus of nearly complete graphs-case 6'', Jonathan L. Gross, Aeq. Math. 13, 243–249 (1975) doi:10.1007/BF01836527]

Latest revision as of 13:19, 3 May 2020

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 relative to the size of the graph.

Mathematical Definition

Consider a graph with vertices , edges , and genus .

Calculate

.

Let denote the smallest integer greater than or equal to . All graphs satisfy Euler's lower bound

.

For complete graphs and the bound is saturated.

One may start with a complete graph and remove edges such that the remaining graph satisfies

  • Euler's lower bound is saturated
  • The graph is connected

Let denote the maximum number of possible edge removals from the complete graph such that the above two properties hold no matter which edges are removed. A graph with vertices is nearly complete if it can be obtained by removing edges from the complete graph .

References