(X,Y)-Графы пересечений

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

[math]\displaystyle{ (X,Y) }[/math]-Графы пересечений ([math]\displaystyle{ (X,Y) }[/math]-Intersection graphs) — Для пары [math]\displaystyle{ (X,Y) }[/math] заданных графов [math]\displaystyle{ X }[/math] и [math]\displaystyle{ Y }[/math] под [math]\displaystyle{ (X,Y) }[/math]-графом пересечений графа [math]\displaystyle{ G }[/math] понимается граф, вершины которого соответствуют различным индуцированным подграфам графа [math]\displaystyle{ G }[/math], изоморфным [math]\displaystyle{ Y }[/math], и где две вершины смежны, если пересечение соответствующих им подграфов содержит индуцированный подграф, изоморфный [math]\displaystyle{ X }[/math]. Это обобщает понятие реберного графа.

Литература

  • [J. Graph Theory]