Сборник переводов.
Идеи и методы теории графов все глубже проникают как в классические области применения этой теории, например в электротехнику, так и в новые области, например социологию и медицину. Широко используются в приложениях такие понятия теории графов, как «толщина», «число скрещиваний», «род графа», «факторы», «паросочетание».
Настоящая книга включает работы самого последнего времени, относящиеся к некоторым важным разделам теории графов. Большинство статей содержит окончательные результаты, мало известные нашим читателям. Сборник можно рассматривать как существенное дополнение к книге Ф. Харари «Теория графов» («Мир», 1973).
Книга заинтересует широкий круг математиков и инженеров, занимающихся теорией графов и ее приложениями. Аспиранты и студенты старших курсов технических вузов и университетов могут использовать ее как учебное пособие.
Предисловие редакторов перевода.
Д. Элиотт, П. Эрдёш. Некоторые теоремы о паросочетаниях.
П. Эрдёш, А. Реньи. О существовании 1-фактора у связного случайного графа.
Я. Плесник. Связность регулярных графов и существование 1-факторов.
Дж. Закс. Об 1-факторах n-связных графов.
В. Мадер Минимальные n-связные графы с максимальным числом ребер.
Г. Хетеи. О границах чисел ребер и степеней вершин, обеспечивающих существование m-факторов в двудольных графах.
Г. Рингель, Дж. Янгс. Решение проблемы Хивуда о раскраске карт.
Г. Рингель, Дж. Янгс. Решение проблемы Хивуда о раскраске карт: случай II.
Л. В. Байнеке, Ф. Харари. Род n-мерного куба.
Е. А. Нордхауз, Б. М. Стюарт, А. Т. Уайт. О максимальном роде графа.
Л. В. Байнеке, Ф. Харари, Дж. В. Мун. О толщине полного двудольного графа.
Л. В. Байнеке, Ф. Харари. Толщина полного графа.
М. Кляйнерт. Толщина n-мерного куба.
Д. Клейтман. Число скрещиваний графа Kb,n.
П. Эрдёш, Дж. В. Мун. О множествах согласованных дуг в турнире.
Л. В. Байнеке, Ф. Харари. Максимальное число сильно связных подтурниров.
Дж. В. Мун. Вложение турниров в простые турниры.
Д. Р. Фалкерсон. Нарушения в круговых турнирах.
Дж. В. Мун. Турниры с данной группой автоморфизмов.
Р. Фрухт, А. Гевирц, Л. В. Квинтас. Наименьшее число ребер в графах, имеющих группу автоморфизмов третьего порядка.
Г. Чартрэнд, Д. Митчем. Графические теоремы класса Нордхауза — Гаддума.
Г. Д. Фридман. О невозможности существования некоторых графов Мура.
Предметный указатель.
Указатель обозначений.
