Гіпотези щодо коліс у приєднаному добутку з циклами

Анотація

Під числом перетинів $\mathrm{cr}(G)$ простого графа $G$ розуміють мінімальну кількість перетинів ребер серед усіх можливих зображень $G$ на площині. Числа перетинів приєднаного добутку двох графів вивчають через їх широке практичне застосування. Основною метою статті є встановлення значення $\mathrm{cr}\left(W_5+C_n\right)$ для колеса $W_5$ на шести вершинах, де $C_n$ $-$ цикли на $n$ вершинах. В. Юе та ін. у [Comp. Eng. Appl. 2014, 50 (18), 79-84] висунули гіпотезу, що число перетинів для $W_m+C_n$ дорівнює $Z(m+1)Z(n)+\big(Z(m)-1\big)\big\lfloor \frac{n}{2} \big \rfloor+n+ \big\lceil\frac{m}{2}\big\rceil+2$ для всіх цілих $m,n \geq 3$. Тут число Заранкевича $Z(n)=\big\lfloor \frac{n}{2} \big\rfloor \big\lfloor \frac{n-1}{2} \big\rfloor$ визначене для всіх $n\geq 1$. Зазначену гіпотезу підтвердили для $W_3+C_n$ $-$ М. Клешч, а для $W_4+C_n$ $-$ М. Сташ та Ю. Валіска. У цій роботі ми доводимо справедливість цієї гіпотези для $W_5+C_n$.