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

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

Литература

• Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.