Декартів добуток графів

• Декартів добуток двох ребер є циклом з чотирма вершинами: K₂ ${\displaystyle \square }$ K₂=C_4.
• Декартів добуток 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. Декартів добуток графів(англ.) на сайті Wolfram MathWorld.