В математике простой субкубический граф ( SSCG ) — это конечный простой граф , в котором каждая вершина имеет степень не более трех. Предположим, что у нас есть последовательность простых субкубических графов G 1 , G 2 , ... такая, что каждый граф G i имеет не более i + k вершин (для некоторого целого числа k ) и для любого i < j не является гомеоморфно вложимым в (т.е. является минором графа ) G j .
Теорема Робертсона–Сеймура доказывает, что субкубические графы (простые или нет) хорошо обоснованы гомеоморфной вложимостью, подразумевая, что такая последовательность не может быть бесконечной. Затем, применяя лемму Кёнига к дереву таких последовательностей при расширении, для каждого значения k существует последовательность с максимальной длиной. Функция SSCG( k ) [1] обозначает эту длину для простых субкубических графов. Функция SCG( k ) [2] обозначает эту длину для (общих) субкубических графов.
Последовательность SCG начинается с SCG(0) = 6, но затем резко увеличивается до значения, эквивалентного f ε 2 *2 в быстрорастущей иерархии .
Последовательность SSCG начинается медленнее, чем SCG, SSCG(0) = 2, SSCG(1) = 5, но затем быстро растет. SSCG(2) = 3 × 2 (3 × 2 95 ) − 8 ≈ 3,241704 × 1035 775 080 127 201 286 522 908 640 065. Его первые и последние 20 цифр — 32417042291246009846...34057047399148290040. SSCG(3) намного больше, чем TREE(3) и TREE TREE(3) (3), то есть функция TREE, вложенная в TREE(3) раз с 3 в конце.
Адам П. Гушер утверждает, что нет качественной разницы между асимптотическими темпами роста SSCG и SCG. Он пишет: «Очевидно, что SCG( n ) ≥ SSCG( n ), но я также могу доказать SSCG(4 n + 3) ≥ SCG( n )». [3]
Функция была предложена и изучена Харви Фридманом .