Magnet in a graph

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

Magnet in a graph --- магнит в графе.

A magnet in a graph [math]\displaystyle{ G = (V,E) }[/math] is defined as a pair [math]\displaystyle{ (a,b) }[/math] of adjacent vertices with the same weight and such that each vertex in [math]\displaystyle{ N_{G}(a) \setminus N_{G}(b) }[/math] is adjacent to each vertex in [math]\displaystyle{ N_{G}(b) \setminus N_{G}(a) }[/math]. In other words, the two endpoints of an edge induce a magnet in a graph [math]\displaystyle{ G }[/math] if and only if this edge is not the middle edge of any [math]\displaystyle{ P_{4} }[/math] in [math]\displaystyle{ G }[/math].