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

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

Пусть 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.

Тотальные графы

Вершины и ребра графа называются его элементами. Два элемента графа называютсясоседними, если они смежны или инцидентны.Тотальным графомТ (G) называется граф, у которого множеством вершин является V (G) U X (G) и две вершины смежны тогда и только тогда, когда они соседние в графе G. На рисунке показано образование тотального графа Т(К₃)

- Легко видеть, что T(G) содержит в качестве порожденных подграфов как G, так и L(G). Другую характеризацию тотальных графов дал Бехзад

Теорема.Тотальный граф Т(G) изоморфен квадрату графа подразбиений S(G).

Следствие(а).Если v — вершина графа G, то степень вершины v в T(G) равна 2deg v. Если x=uv — ребро графа G, то степень вершины х в Т (G) равна deg u+ deg v.

Следствие(б). Пусть G — это (р, q)-граф, вершины которого имеют степени di; тогда тотальный граф Т (G) имеет Pm=P+q вершин и qT =2q+ (1/2)di*di ребер.

В гл. 2 были определены числа Рамсея r(m,n) и было отмечено, что их вычисление в общем случае остается нерешенной задачей. Бехзад и Раджави сформулировали и решили аналогичную проблему относительно реберных графов.Реберным числом Рамсеяr1 (m,n) называется такое наименьшее положительное целое число р, что каждый связный граф с р вершинами содержит илиnпопарно несмежных ребер, или звезду К1,m. Другими словами, r1(m, n) — такое наименьшее натуральное число р, что для любого графа G с р вершинами L (G) содержит Кmили L(G)) содержит Кn

Теорема.Для n> 1 всегда справедливо равенство r1 (2, n) = = 3. Для всех других значений тип

r1(m, n) = (m—1) (n—1)+2.

Отметим, что равенство r1 (m,n)=r1 (n,m) верно не всегда. К тому же в противоположность числам Рамсея числа r1(m, п) определены только для связных графов.