Число форсування в нуль деяких родин графiв

Анотація

Статтю присвячено дослiдженню числа форсування в нуль деяких родин графiв. Концепцiя форсування в нуль є порiвняно новою темою дослiджень у дискретнiй математицi, яка вже має певнi практичнi застосування, зокрема, число форсування в нуль використовується у дослiдженнях мiнiмального рангу матриць сумiжних графiв. Також процес форсування в нуль є одним iз прикладiв процесiв поширення на графах. Такi процеси часто використовують для моделювання технiчних або соцiальних процесiв i в iнших сферах: в статистичнiй механiцi, фiзицi, аналiзi соцiальних мереж тощо.
Нехай вершини графа G вважатимуться бiлими, за винятком певного набору S чорних вершин. Ми перефарбуємо вершини графа з бiлого в чорний, використовуючи певне правило, а саме
Правило змiни кольору: Бiла вершина стає чорною, якщо це єдина бiла вершина, що прилягає до чорної вершини.

[5] Число форсування в нуль Z(G) графа G — це мiнiмальна потужнiсть набору чорних вершин S, необхiдних для перетворення всiх вершин графа G на чорнi за скiнченну кiлькiсть крокiв за допомогою «правила змiни кольору».
Вiдомо [10], що для будь-якого графа G його число форсування в нуль не може бути меншим за мiнiмальну степiнь вершин. Такi та iншi вже вiдомi факти стали основою пошуку числа форсування в нуль для двох наступних родин графiв:
Граф-шестерня, що позначається W_2,n, — це граф, отриманий шляхом вставки додаткової вершини мiж кожною парою сусiднiх вершин по периметру графа колеса W_n. Таким чином, W_2,n має 2n + 1 вершин i 3n ребер.
Граф-призма, що позначається Y_n, або в загальному випадку Y_m,n, iнодi його також називають круговою драбиною, — це граф, що вiдповiдає скелету n-призми.
Граф-колесо, що позначається W_n, — це граф, утворений шляхом приєднання однiєї (центральної) вершини до всiх вершин циклу довжиною n.
У цiй статтi розглядаються визначення, доведення та деякi приклади числа форсування в нуль та процесу форсування в нуль родини графiв-шестерень та родини графiв-призм.