Control Systems and Computers, N3, 2019, Статья 2
https://doi.org/10.15407/csc.2019.03.015
Semeniuta M.F., Sherman Z.O. On New Properties of Graphs with Magic Type Labeling. Control Systems and Computers. С. 15-22.
УДК 519.1
Семенюта Марина Фроловна, канд. физ.-мат. наук, профессор кафедры физико-математических дисциплин Летной акад. нац. ави. ун-та., г. Кропивницкий, пер. Ботанический, 12, E-mail: marina_semenyuta@ukr.net
Шерман Зоя Александровна, канд. физ.-мат. наук, Донецкий национальный медицинский университет, старший преподаватель кафедры медицинской физики и информационных технологий №2, E-mail: sherman.zoya@gmail.com
О НОВЫХ СВОЙСТВАХ ГРАФОВ С РАЗМЕТКАМИ МАГИЧЕСКОГО ТИПА
Введение. В данной работе исследуются свойства графов с вершинными разметками магического типа, а именно с D-дистанционной магической, впервые предложенной A. O’Нилом и П. Слэйтером в 2011 году, и с (a, d)-дистанционной антимагической, введенной в 2012 году С. Арумугамом и Н. Камачи. Результаты по решению задач существования, построения и перечисления для различных версий разметок графов можно найти в электронном журнале «A dynamic survey of graph labeling» под редакцией Д. Галлиана.
Цель статьи – получить новые свойства графов, допускающих дистанционные магические и антимагические разметки, а также разработать алгоритм построения r-регулярного гандикап графа G=(V,E) порядка n, где n≡0(mod8), r≡1,3(mod4) и 3≤r≤n–5.
Методы. Использованы методы теории графов, теории множеств, матричного анализа при исследовании свойств графов, обладающих разметками магического типа. При разработке алгоритма построения регулярного гандикап графа задействованы методы теории разложений графов и теории алгоритмов.
Результат. Предложен алгоритм построения r-регулярного гандикап графа порядка n, где n≡0(mod8), r≡1,3(mod4) и 3≤r≤n–5, приведена оценка его трудоемкости.
Вывод. Установлена связь между вершинными разметками магического типа графа и его надграфа. Получено описание отношения эквивалентности на множестве всех D-дистанционных магических графов и исследованы свойства графов, находящихся в этом отношении. Результаты исследования являютя полезными для дальнейшего развития данной тематики и расширяют круг применений графов с разметкой магического типа.
Загрузить полный текст в PDF (на английском).
Ключевые слова: граф, D-дистанционная магическая разметка, (a, d)-дистанционная антимагическая разметка, гандикап разметка, D-дистанционная матрица, отношение эквивалентности, 1-фактор.
Поступила 18.06.2019
