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

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

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

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

Определение

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

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

Свойства

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

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

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

  ${\displaystyle \alpha (G\cdot H)=\alpha (G)\alpha (H)}$.

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

  ${\displaystyle \omega (G\cdot H)=\omega (G)\omega (H)}$.

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

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

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

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