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

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