Тождественный граф

Тожде́ственный граф (асимметри́чный граф) — граф, группа автоморфизмов которого состоит из одного единственного тождественного автоморфизма. Образно говоря, роль каждой вершины в тождественном графе уникальна.

Тождественный граф из одной вершины есть просто одна отдельная вершина. Тождественных графов из 2, 3, 4 и 5 вершин не существует.

Тождественных графов из шести вершин восемь штук и они изображены ниже.

Identity graph1.svg Identity graph2.svg Identity graph3.svg Identity graph4.svg Identity graph5.svg Identity graph6.svg Identity graph7.svg Identity graph8.svg

Количество тождественных графов на 7, 8, 9,... вершинах соответственно равно 152, 3696, 135004, ... (последовательность A003400 в OEIS)

См. такжеПравить