Последовательности степеней ребер самодополнительных графов

Ж. А. Черняк


Аннотация: Граф $G$ называется реализацией последовательности неупорядоченных пар натуральных чисел
\begin{equation} (\alpha_1,\beta_1),\dots,(\alpha_q,\beta_q), \tag{1} \end{equation}
если она является последовательностью степеней ребер графа $G$. Реализация $G$ последовательности (1) называется само дополнительной, если $G$ изоморфен своему дополнению.
В работе полностью описаны последовательности (1), имеющие самодополнительную реализацию. Доказательство основной теоремы конструктивно и дает алгоритм построения такой реализации. Библ. 7 назв.

УДК: 519.1

Поступило: 29.01.1981

 Англоязычная версия: Mathematical Notes, 1983, 34:2, 631–637

Реферативные базы данных:

• 
• 
•