Сильная степень графа

Материал из WikiGrapp
Перейти к:навигация, поиск

Сильная степень графа (Strong degree of a graph) - для графа G=(V,E) граф G^{k} = (V^{k}, E^{k}) у которого множество вершин V^{k} = \underbrace{V \times V
\times \ldots \times V}_{k} а несовпадающие вершины (u_{1}, u_{2}, \ldots, u_{k}) и (v_{1}, v_{2}, \ldots,
v_{k}) смежны в графе G^{k} тогда и только тогда, когда для каждого индекса i = 1, 2, \ldots, k выполняется условие u_{i} = v_{i} или (u_{i},v_{i}) \in E.


Strong degree of a graph.png


Литература

[Лекции]