Задачи перечисления графов

Предлагаемая обзорная статья принадлежит известному американскому специалисту по теории графов. В ней приведена необходимая терминология и собрано большое количество разнообразных задач, относящихся к одной из областей теории графов – перечислению и подсчету графов с определенными свойствами. Известно, что получение явных общих формул в подобных задачах удается в редких случаях, так что приходится довольствоваться результатами в более слабой форме. В статье рассматриваются задачи, представленные в аналогичной работе автора 1964 г. (см. [24]), указано, какие из них уже решены, и приводится новый список из 27 задач. Следует заметить, что статья касается почти исключительно одной стороны проблемы перечисления, а именно получения перечисляющих рядов для графов того или иного класса, и содержит мало результатов об асимптотическом поведении числа графов при возрастании параметра (чаще всего числа ребер или вершин). Решения чаще всего основаны на методе Пойа. В статье изложены и проиллюстрированы примерами как сама теорема Пойа, так и ее применения к задачам перечисления графов. Таким образом, статью можно читать, не обращаясь к другим источникам.