Бесквадра́тное сло́во — слово, в котором никакое подслово не повторяется подряд 2 раза.
Алгори́тм Ле́мпеля — Зи́ва — Уэлча — это универсальный алгоритм сжатия данных без потерь, созданный Авраамом Лемпелем, Яаковом Зивом и Терри Велчем. Он был опубликован Велчем в 1984 году в качестве улучшенной реализации алгоритма LZ78, опубликованного Лемпелем и Зивом в 1978 году. Алгоритм разработан так, чтобы его было достаточно просто реализовать как программно, так и аппаратно.
Дискре́тное логарифми́рование (DLOG) — задача обращения функции 
в некоторой конечной мультипликативной группе 
.
Раскраска графа — теоретико-графовая конструкция, частный случай разметки графа. При раскраске элементам графа ставятся в соответствие метки с учётом определённых ограничений; эти метки традиционно называются «цветами». В простейшем случае такой способ окраски вершин графа, при котором любым двум смежным вершинам соответствуют разные цвета, называется раскраской вершин. Аналогично раскраска рёбер присваивает цвет каждому ребру так, чтобы любые два смежных ребра имели разные цвета. Наконец, раскраска областей планарного графа назначает цвет каждой области, так, что каждые две области, имеющие общую границу, не могут иметь одинаковый цвет.
Хроматический многочлен — многочлен, изучаемый в алгебраической теории графов, представляющий число раскрасок графа как функцию от числа цветов. Первоначально определён Джорджем Биркгофов для попытки решения на проблемы четырёх красок. Обобщен и систематически изучен Хасслером Уитни, Татт обобщил хроматический многочлен до многочлена Татта, связав его с моделью Поттса статистической физики.
В теории графов максимальным независимым множеством, максимальным устойчивым множеством, или максимальным стабильным множеством называется независимое множество, не являющееся подмножеством другого независимого множества. То есть это такое множество вершин S, что любое ребро графа имеет хотя бы одну конечную вершину, не принадлежащую S, и любая вершина не из S имеет хотя бы одну соседнюю в S. Максимальное независимое множество является также доминирующим в графе, а любое доминирующее множество, являющееся независимым, должно быть максимальным независимым, поэтому максимальные независимые множества также называют независимыми доминирующими множествами. Граф может иметь много максимальных независимых множеств в широком диапазоне размеров.
Граф Хивуда — ненаправленный граф с 14 вершинами и 21 ребром, названный в честь Перси Джона Хивуда.
Граф Мёбиуса — Кантора — симметричный двудольный кубический граф с 16 вершинами и 24 рёбрами, названный в честь Августа Фердинанда Мёбиуса и Зелигмана Кантора (1857—1903). Его можно определить как обобщённый граф Петерсена 
, то есть он образован вершинами восьмиугольника, соединёнными с восьмиугольной звездой, в которой каждая точка соединена с третьей по счёту точкой.
В теории графов графом гиперкуба Qn называется регулярный граф с 2n вершинами, 2n−1n рёбрами и n рёбрами, сходящимися в одной вершине. Его можно получить как одномерный скелет геометрического гиперкуба. Например, Q3 — это граф, образованный 8 вершинами и 12 рёбрами трёхмерного куба. Граф можно получить другим образом, отталкиваясь от семейства подмножеств множества с n элементами путём использования в качестве вершин все подмножества и соединением двух вершин ребром, если соответствующие множества отличаются только одним элементом.
Конфигура́ция прямы́х — это разбиение плоскости, образованное набором прямых. Конфигурации прямых изучается в комбинаторной геометрии, а в вычислительной геометрии строятся алгоритмы для эффективного построения конфигураций.
В теории графов вечное или бессмертное доминирующее множество для графа G = (V, E) — это подмножество D вершин V, такое, что D является доминирующим множеством, на котором располагается мобильная охрана первоначально (не более одного охранника может находиться в одной вершине). Множество D должно быть таким, что для любой бесконечной последовательности атак на вершины множество D может быть модифицировано путём передвижения охранника со смежной вершины на атакуемую вершину, если атакуемая вершина не была занята охранником во время атаки. Конфигурация охранников должна после каждой атаки и движения охранника образовывать доминирующее множество. Вечное доминирующее число, γ∞(G), — это минимальное число вершин во всех таких множествах D. Например, вечное доминирующее число цикла из пяти вершин равно трём.
Задача поиска изоморфного подграфа — это вычислительная задача, в которой входом являются два графа G и H и нужно определить, не содержит ли G подграф, изоморфный графу H. Задача поиска изоморфного подграфа является обобщением как задачи о максимальной клике, так и задачи о проверке, не содержит ли граф гамильтонов цикл, а потому является NP-полной. Однако задачи поиска изоморфного подграфа с некоторыми видами подграфов могут быть решены за полиномиальное время.
Задача Лемера о функции Эйлера задаёт вопрос, существует ли какое-либо составное число n, такое, что функция Эйлера φ(n) делит n − 1. Задача остаётся нерешённой.
Практичное число или панаритмичное число — это положительное целое число n, такое что все меньшие положительные целые числа могут быть представлены в виде суммы различных делителей числа n. Например, 12 является практичным числом, поскольку все числа от 1 до 11 можно представить в виде суммы делителей 1, 2, 3, 4 и 6 этого числа — кроме самих делителей, мы имеем 5 = 3 + 2, 7 = 6 + 1, 8 = 6 + 2, 9 = 6 + 3, 10 = 6 + 3 + 1 и 11 = 6 + 3 + 2.
Задача о паре ближайших точек — это задача вычислительной геометрии. Дано n точек в метрическом пространстве, нужно найти пару точек с наименьшим расстоянием между ними.
Фишечная игра — это вид математической игры, в которой игра заключается в передвижении «фишек» или «маркеров» на ориентированном графе. Существует большое число различных фишечных игр.
Топологический граф — представление графа на плоскости, в котором вершины графа представлены различными точками, а рёбра кривыми Жордана, соединяющими соответствующие пары точек. Точки, представляющие вершины графа, и дуги, представляющие рёбра, называются вершинами и рёбрами топологического графа. Обычно предполагается, что любые два ребра топологического графа пересекаются конечное число раз, при этом ни одно ребро не проходит через вершину и никакие два ребра не касаются друг друга. Топологический граф называется также «рисунком» графа.
Цветовое кодирование — алгоритмическая техника, которая полезна для обнаружения структурных мотивов. Например, оно может быть использовано для обнаружения простого пути длины k в заданном графе. Традиционный алгоритм цветового кодирования является вероятностным, но он может быть дерандомизирован без существенного увеличения времени работы.
