On New Properties of Graphs with Magic Type Labeling

• Published in: Управляющие системы и машины
• Date: 2019
• Main Authors: Semeniuta, M.F., Sherman, Z.O.
• Format: Article
• Language: English
• Published: Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України 2019
• Subjects: Fundamental Problems in Computer Science
• Online Access: https://nasplib.isofts.kiev.ua/handle/123456789/161628
• Journal Title: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Cite this: On New Properties of Graphs with Magic Type Labeling / M.F. Semeniuta, Z.O. Sherman // Управляющие системы и машины. — 2019. — № 3. — С. 15-22. — Бібліогр.: 15 назв. — англ.

We have shown the connection between vertex labelings of magic graph and its overgraph. Also, we have introduced binary relation on the set of all -distance magic graphs, where , i=1, 2, … and proved, that it is equivalence relation. Therefore, we have explored the properties of the graphs, which are in this relation. Finally, we have offered the algorithm of constructing r-regular handicap graph of order n, where n ≡ 0(mod8), r ≡ 1,3(mod4) and 3 ≤ r ≤n–5. Мета статті – одержати нові властивості графів, що допускають дистанційні магічні та антимагічні розмітки, а також розробити алгоритму побудови 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, навед ена оцінка його трудомісткості. Цель статьи — получить новые свойства графов, допускающих дистанционные магические и антимагические разметки, а также разработать алгоритм построения r-регулярного гандикап графа G = (V, E) порядка n, где n ≡ 0(mod 8), r ≡ 1,3(mod 4) и 3 ≤ r ≤ n – 5. Методы. Использованы методы теории графов, теории множеств, матричного анализа при исследовании свойств графов, обладающих разметками магического типа. При разработке алгоритма построения регулярного гандикап графа задействованы методы теории разложений графов и теории алгоритмов. Результаты. Проведено исследование свойств D-дистанционных магических графов и показано, если вершинная разметка f графа G является D-дистанционной магической, то для D-надграфа GD биекция f порождает дистанционную магическую разметку при 0 ∊D и (k–n, 1)-дистанционную антимагическую разметку при 0 ∊ D. На множестве M всех Di-дистанционных магических графов, где i = 1, 2, ..., введено бинарное отношение R ⊂ M×M