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, 25055, Україна, marina_semenyuta@ukr.net
З.О. Шерман, кандидат фіз .-мат . наук, старший викладач кафедри медичної фізики та інформаційних технологій № 2, Донецький нац. медичний університет,
вул . Привокзальна, кв. 27, 84404, м . Ліман, Україна,
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.
Методи. Використано методи теорії графів, теорії множин, матричного аналізу при дослідженні властивостей графів, які володіють розмітками магічного типу. При розробці алгоритму побудови регулярного гандикап графа задіяні методи теорії розкладів графів теорії алгоритмів.
Результат. Проведено дослідження властивостей D-дистанційних магічних графів і показано, якщо вершинна розмітка f графа є D-дистанційною магічною, то для -надграфа GD бієкція f породжує дистанційну магічну розмітку при 0 є D і (k-1, 1)-дистанційну антимагічну розмітку при 0 належить D. На множині M всіх Di-дистанційних магічних графів, де i=1, 2, … введено бінарне відношення R є підмножиною MxM. Запропоновано алгоритм побудови r-регулярного гандикап графа G=(V,E) порядку n, де n≡0(mod8), r≡1,3(mod4) і 3≤r≤n–5, наведена оцінка його трудомісткості.
Висновок. Встановлено зв’язок між вершинними розмітками магічного типу графа та його надграфа. Одержано опис відношення еквівалентності на множині всіх Di-дистанційних магічних графів і досліджено властивості графів, що знаходяться в цьому відношенні. Результати дослідження є корисні для подальшого розвитку даної тематики і розширюють коло застосувань графів з розмітками магічного типу.
Завантажити повний текст PDF (англійською ).
Ключові слова: граф, D-дистанційна магічна розмітка, (a, d)-дистанційна антимагічна розмітка, гандикап розмітка,
D-дистанційна матриця, відношення еквівалентності, 1-фактор.
Надійшла 18.06.2019
