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

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

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

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

Определение

$G\cdot H$ графов Шаблон:Mvar и Шаблон:Mvar — это граф, такой, что

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

Свойства

• Лексикографическое произведение в общем случае не коммутативно: $G\cdot H\ne 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)$.

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

  $\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)$.

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

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

Литература

• Шаблон:Книга

Ссылки

• Шаблон:Mathworld