Лексикографическое произведение графов

Лексикографическое произведение или суперпозиция графов — конструкция графа по данным двум. Если связи рёбер в двух графах являются отношениями порядка, то связь рёбер в их лексикографическом произведении является соответствующим лексикографическим порядком — отсюда название.

Лексикографическое произведение графов.

Лексикографическое произведение первым изучал Феликс Хаусдорф.

Определение

$G\cdot H$ графов G и H — это граф, такой, что

• Множество вершин графа $G\cdot H$ есть $V(G)\times V(H)$; то есть прямое произведение множеств вершин графов $G$ и $H$.
• Любые две вершины (u,v) и (x,y) смежны в $G\cdot H$ тогда и только тогда, когда либо u смежна x в G, либо $u=x$ и v смежна y в H.

Свойства

• Лексикографическое произведение в общем случае не коммутативно: $G\cdot H\neq H\cdot G$. Однако оно удовлетворяет дистрибутивному закону для дизъюнктного объединения: $(A+B)\cdot C=A\cdot C+B\cdot C$.

• Для дополнений выполняется: $\mathrm {C} (G\cdot H)=\mathrm {C} (G)\cdot \mathrm {C} (H)$.

• Число независимости лексикографического произведения можно легко вычислить из его сомножителей :

  $\alpha (G\cdot H)=\alpha (G)\alpha (H)$.

• Кликовое число лексикографического произведения мультипликативно:

  $\omega (G\cdot H)=\omega (G)\omega (H)$.

• Хроматическое число лексикографического произведения равно b-кратному хроматическому числу графа G для b, равному хроматическому числу H:

  $\chi (G\cdot H)=\chi _{b}(G)$, где $b=\chi (H)$.

• Лексикографическое произведение двух графов является совершенным графом тогда и только тогда, когда оба множителя совершенны.

• Задача распознавания, является ли граф лексикографическим произведением по сложности эквивалентна задаче об изоморфизме графов.

Ссылки

• Weisstein, Eric W. Graph Lexicographic Product (англ.) на сайте Wolfram MathWorld.