Реберные графы и обходы

Исследуем теперь связь эйлеровых и гамильтоновых графов с реберными графами.

Пусть x=uv- ребро графа G, а w не является вершиной в G. Говорят, что ребро х подразбито, если оно заменено на ребра uw и wv. Если каждое ребро графа G подразбито, то такой граф называется графом подразбиений графа G и обозначается S (G); см. рисунок

Если обозначить через Sn(G) граф, получаемый из G введением n новых вершин степени 2 на каждом ребре графа G, так что S(G) = S1(G), то можно определить новый граф Ln (G) = L(Sn-1 (G)). Отметим, что в общем случае Ln (G)!=Lⁿ (G). Здесь Lⁿ (G) — итерированный реберный граф графа G.

Теорема. Если G - эйлеров граф, то граф L(G) эйлеров и гамильтонов. Если G - гамильтонов граф, то L(G) - также гамильтонов граф.

Легко привести контрпримеры к обратным утверждениям. Например, граф L(G), изображенный на рисунке, эйлеров и гамильтонов, в то время как граф G не эйлеров; граф L(G) на рисунке гамильтонов, а граф G нет.

Второе предложение теоремы можно усилить. Это достигается благодаря следующему результату Харари и Нэш-Вильямса, который легко вытекает из предыдущей теоремы и равенства L2(G) = L(S(G)).

Теорема. Для того чтобы граф L2(G) был гамильтоновым, достаточно, чтобы граф G был гамильтоновым, и необходимо, чтобы граф L (G) был гамильтоновым.

Графы на рисунке показывают, что первое из условий не является необходимым, а второе не является достаточным для того, чтобы L2(G) был гамильтоновым графом. Отметим также,

что L (G) = L1 (G) и L2 (G) могут быть гамильтоновыми графами, даже если граф G не будет эйлеровым. Однако граф L3(G) связывает эти два понятия.

Теорема. Граф G эйлеров тогда и только тогда, когда граф L³(G) гамильтонов.

Для почти каждого связного графа G почти все графы Lⁿ(G), как показал Чартрэнд, гамильтоновы.

Теорема. Если G — нетривиальный связный граф с р вершинами, не являющийся простой цепью, то граф Lⁿ(G) гамильтонов для всех п>р- 3.