Реберные графы

Понятие реберного графа для данного графа настолько естественно, что независимо было введено многими авторами. Конечно, каждый из них давал свое название: Ope назвал этот граф «смежностным графом», Сабидусси - «графом производной», Байнеке — «производным графом», Сешу и Рид - «реберно-вершинно-двойственным», Кастелейн — «покрывающим графом», Менон - «присоединенным» («сопряженным»). Были даны различные описания реберных графов. В этой главе вводится также тотальный граф, который изучался впервые Бехзадом , и поскольку (это очень удивительно!) он был обнаружен единожды, он не имеет других названий. Мы исследуем связь между реберными и тотальными графами, уделяя особое внимание эйлеровым и гамильтоновым графам.