In mathematics, a simple subcubic graph (SSCG) is a finite simple

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...

in which each

vertex Vertex, vertices or vertexes may refer to: Science and technology Mathematics and computer science *Vertex (geometry), a point where two or more curves, lines, or edges meet *Vertex (computer graphics), a data structure that describes the position ...

has

degree Degree may refer to: As a unit of measurement * Degree (angle), a unit of angle measurement ** Degree of geographical latitude ** Degree of geographical longitude * Degree symbol (°), a notation used in science, engineering, and mathemati ...

at most three. Suppose we have a sequence of simple subcubic graphs ''G''₁, ''G''₂, ... such that each graph ''G''_''i'' has at most ''i'' + ''k'' vertices (for some integer ''k'') and for no ''i'' < ''j'' is ''G''_''i'' homeomorphically embeddable into (i.e. is a

graph minor In graph theory, an undirected graph is called a minor of the graph if can be formed from by deleting edges and vertices and by contracting edges. The theory of graph minors began with Wagner's theorem that a graph is planar if and only i ...

of) ''G''_''j''. The

Robertson–Seymour theorem In graph theory, the Robertson–Seymour theorem (also called the graph minor theorem) states that the undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering. Equivalently, every family of graphs that i ...

proves that subcubic graphs (simple or not) are well-founded by homeomorphic embeddability, implying such a sequence cannot be infinite. So, for each value of ''k'', there is a sequence with maximal length. The function SSCG(''k'') denotes that length for simple subcubic graphs. The function SCG(''k'') denotes that length for (general) subcubic graphs. The ''SCG'' sequence begins SCG(0) = 6, but then explodes to a value equivalent to f_ε₂*2 in the fast-growing hierarchy. The ''SSCG'' sequence begins SSCG(0) = 2, SSCG(1) = 5, but then grows rapidly. SSCG(2) = 3 × 2^{(3 × 2⁹⁵)} − 8 ≈ 3.241704 × 10^{35775080127201286522908640066} and its decimal expansion ends in ...11352349133049430008. SSCG(3) is much larger than both TREE(3) and TREE^TREE(3)(3). Adam P. Goucher claims there is no qualitative difference between the asymptotic growth rates of SSCG and SCG. He writes "It's clear that SCG(''n'') ≥ SSCG(''n''), but I can also prove SSCG(4''n'' + 3) ≥ SCG(''n'')."TREE(3) and impartial games , Complex Projective 4-Space
/ref>

Notes

References

{{DEFAULTSORT:Friedman's SSCG function Mathematical logic Theorems in discrete mathematics Order theory Wellfoundedness Graph theory

See also

Notes

References