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

Автор(и)

  • Victoria Petruk Національний університет «Києво-Могилянська Академія»

DOI:

https://doi.org/10.18523/2617-70803202048-52cs

Ключові слова:

число форсування в нуль, граф-шестерня, граф-призма

Анотація

Статтю присвячено досл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в:
Граф-шестерня, що позначається W2,n, — це граф, отриманий шляхом вставки додаткової вершини мiж кожною парою сусiднiх вершин по периметру графа колеса Wn. Таким чином, W2,n має 2n + 1 вершин i 3n ребер.
Граф-призма, що позначається Yn, або в загальному випадку Ym,n, iнодi його також називають круговою драбиною, — це граф, що вiдповiдає скелету n-призми.
Граф-колесо, що позначається Wn, — це граф, утворений шляхом приєднання однiєї (центральної) вершини до всiх вершин циклу довжиною n.
У цiй статтi розглядаються визначення, доведення та деякi приклади числа форсування в нуль та процесу форсування в нуль родини графiв-шестерень та родини графiв-призм.

Біографія автора

Victoria Petruk, Національний університет «Києво-Могилянська Академія»

Магiстр прикладної математики, випускниця Нацiонального унiверситету «Києво-Могилянська академiя». Сфера наукових iнтересiв — дискретна математика, метрична геометрiя.

Посилання

F. Harary and R. A. Melter, ”On the the metric dimension of a graph”, Ars Combinatoria. 2, 191–195 (1976).

S. Khuller, B. Raghavachari and A. Rosenfeld, “Landmarks in graphs”, Disc. Appl. Math. 70, 217–229 (1996).

B. Shanmukha, B. Sooryanarayana and K. S. Harinath, “Metric dimension ofWheels”, Far East J. Appl. Math. 8 (3), 217–229 (2002).

C. Hernando, M. Mora, I. M. Pelayo, C. Seara, J. Caceres and M. L. Puertas, “On the metric dimension of some families of graphs”, Electronic Notes in Discrete Mathematics. 22, 129–133 (2005).

Linda Eroh, Cong X. Kang and Eunjeong Yi, “A Comparison between the Metric Dimension and Zero Forcing Number of Trees and Unicyclic Graphs”, Acta Mathematica Sinica, English Series Jun. 33 (6), 731–747 (2017).

Thomas Kalinowski, Nina Kamcev and Benny Sudakov, Zero forcing number of graphs (2017). Retrieved from arXiv:1705.10391v2[math.CO].

Shannon Dillman and Franklin Kenter, Leaky Forcing: A New Variation of Zero Forcing (2019). Retrieved from arXiv:1910.00168v1[math.CO].

Kiran B. Chilakamarri, Nathaniel Dean, Cong X. Kang and Eunjeong Yi, Iteration Index of a Zero Forcing Set in a Graph (2011). Retrieved from arXiv:1105.1492v1[math.CO].

Fatemeh Alinaghipour Taklimi, Zero Forcing Sets for Graphs (2013). Retrieved from arXiv:1311.7672v1 [math.CO].

A. Berman, S. Friedland, L. Hogben et al., “An upper bound for the minimum rank of a graph”, Linear Algebra Appl. 429, 1629–1638 (2008).

F. Barioli, W. Barrett, S. M. Fallat, H. T. Hall, L. Hogben, B. Shader, P. van den Driessche and H. van der Holst, “Zero forcing parameters and minimum rank problems”, Linear Algebra and its Applications. 433, 401–411 (2010).

##submission.downloads##

Опубліковано

2021-02-24