Прямое произведение графов

• Декартово произведение двух рёбер является циклом с четырьмя вершинами: K₂ ${\displaystyle \square }$ K₂=C₄.
• Декартово произведение K₂ и пути является лестницей.
• Декартово произведение двух путей является решёткой.
• Декартово произведение n рёбер является гиперкубом:

${\displaystyle (K_{2})^{\square n}=Q_{n}.}$

Таким образом, декартово произведение двух графов гиперкубов является другим гиперкубом — Q_i ${\displaystyle \square }$ Q_j=Q_i+j.

• Декартово произведение двух медианных графов является другим медианным графом.
• Граф вершин и рёбер n-угольной призмы является декартовым произведением K₂ ${\displaystyle \square }$ C_n.
• Ладейный граф является декартовым произведением двух полных графов.

Если связный граф является декартовым произведением, его можно разложить единственным образом на произведение простых множителей, графов, которые нельзя разложить на произведение графов [4][5]. Однако, Имрих и Клавжар[6] описали несвязный граф, который можно представить двумя различными путями как декартово произведение простых графов:

(K₁ + K₂ + K₂²) ${\displaystyle \square }$ (K₁ + K₂³)=(K₁ + K₂² + K₂⁴) ${\displaystyle \square }$ (K₁ + K₂),

где знак плюс означает несвязное объединение, а верхний индекс означает кратное декартово произведение.

Декартово произведение является вершинно-транзитивным графом тогда и только тогда, когда каждое из его множителей является вершинно-транзитивным[7].

Декартово произведение является двудольным тогда и только тогда, когда каждый из его множителей является двудольным. Более обще, хроматическое число декартова произведения удовлетворяет уравнению

χ(G ${\displaystyle \square }$ H)=max {χ(G), χ(H)}[8].

Гипотеза Хедетниеми утверждает связанное равенство для тензорного произведения графов. Число независимости декартовых произведений непросто вычислить, но, как показал Визинг[5], число независимости удовлетворяет неравенствам

α(G)α(H) + min{|V(G)|-α(G),|V(H)|-α(H)} ≤ α(G ${\displaystyle \square }$ H) ≤ min{α(G) |V(H)|, α(H) |V(G)|}.

Гипотеза Визинга утверждает, что число доминирования декартова произведения удовлетворяет неравенству

γ(G ${\displaystyle \square }$ H) ≥ γ(G)γ(H).

Алгебраическую теорию графов можно использовать для анализа декартова произведения графов. Если граф ${\displaystyle G_{1}}$ имеет ${\displaystyle n_{1}}$ вершин и ${\displaystyle n_{1}\times n_{1}}$ матрицу смежности ${\displaystyle \mathbf {A} _{1}}$, а граф ${\displaystyle G_{2}}$ имеет ${\displaystyle n_{2}}$ вершин и ${\displaystyle n_{2}\times n_{2}}$ матрицу смежности ${\displaystyle \mathbf {A} _{2}}$, то матрица смежности декартова произведения двух графов задаётся формулой

${\displaystyle \mathbf {A} _{1\square 2}=\mathbf {A} _{1}\otimes \mathbf {E} _{n_{2}}+\mathbf {E} _{n_{1}}\otimes \mathbf {A} _{2}}$,

где ${\displaystyle \otimes }$ означает произведение Кронекера матриц, а ${\displaystyle \mathbf {E} _{n}}$ означает ${\displaystyle n\times n}$ единичную матрицу[9].

Согласно Имриху и Клавжару[6] декартовы произведения графов определили в 1912 Уайтхед и Рассел. Произведение графов неоднократно переоткрывалось позже, в частности, Гертом Сабидусси[4].

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