Difference between revisions of "Nearly Complete Graph"
Owen Vaughan (talk | contribs) |
Owen Vaughan (talk | contribs) |
||
| 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. |
| − | + | == Mathematical Definition == | |
| − | |||
Consider a graph with vertices ''v'', edges ''e'', and genus ''g''. | Consider a graph with vertices ''v'', edges ''e'', and genus ''g''. | ||
| Line 12: | Line 11: | ||
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)''. | 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)''. | ||
| − | A graph with vertices ''v'' is said to be 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. | + | A graph with vertices ''v'' is said to be ''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. |
| − | == | + | ==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] |
Revision as of 12:31, 31 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.
Mathematical Definition
Consider a graph with vertices v, edges e, and genus g.
Euler's lower bound is defined to be
X = (e - 3v + 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).
A graph with vertices v is said to be 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.