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

Вершины и ребра графа называются его элементами. Два элемента графа называются соседними, если они смежны или инцидентны. Тотальным графом Т (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, п) определены только для связных графов.