Про дистанційну антимагічну розмітку графів
Досліджується антимагічний тип вершинної розмітки графа. Для циркулянтних графів знайдена необхідна умова, а для голландського вітряка – необхідна і достатня умови існування (a, d)-дистанційної антимагічної розмітки. Исследуется антимагический тип вершинной разметки графа. Для циркулянтных графов на...
Збережено в:
| Опубліковано в: : | Теорія оптимальних рішень |
|---|---|
| Дата: | 2016 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2016
|
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/113015 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Про дистанційну антимагічну розмітку графів / М.Ф. Семенюта // Теорія оптимальних рішень: Зб. наук. пр. — 2016. — № 2016. — С. 26-32. — Бібліогр.: 7 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859672545709522944 |
|---|---|
| author | Семенюта, М.Ф. |
| author_facet | Семенюта, М.Ф. |
| citation_txt | Про дистанційну антимагічну розмітку графів / М.Ф. Семенюта // Теорія оптимальних рішень: Зб. наук. пр. — 2016. — № 2016. — С. 26-32. — Бібліогр.: 7 назв. — укр. |
| collection | DSpace DC |
| container_title | Теорія оптимальних рішень |
| description | Досліджується антимагічний тип вершинної розмітки графа. Для циркулянтних графів знайдена необхідна умова, а для голландського вітряка – необхідна і достатня умови існування (a, d)-дистанційної антимагічної розмітки.
Исследуется антимагический тип вершинной разметки графа. Для циркулянтных графов найдено необходимое условие, а для голландской мельницы – необходимое и достаточное условие существования (a, d)-дистанционной антимагической разметки.
We studied the antimagic type of a vertex labeling of the graph. We have found necessary condition for existence of (a, d)-distance antimagic labelling for circulation graphs, as well as necessary and sufficient conditions for existence of (a, d)-distance antimagic labelling for a Dutch windmill graph.
|
| first_indexed | 2025-11-30T14:07:57Z |
| format | Article |
| fulltext |
26 Теорія оптимальних рішень. 2016
ТЕОРІЯ
ОПТИМАЛЬНИХ
РІШЕНЬ
Досліджується антимагічний тип
вершинної розмітки графа. Для
циркулянтних графів знайдена не-
обхідна умова, а для голландсько-
го вітряка – необхідна і достатня
умови існування (a, d)-дистан-
ційної антимагічної розмітки.
М.Ф. Семенюта, 2016
УДК 519.1
М.Ф. СЕМЕНЮТА
ПРО ДИСТАНЦІЙНУ АНТИМАГІЧНУ РО-
ЗМІТКУ ГРАФІВ
Вступ. Під розміткою графа G = (V, E) розу-
міємо відображення множини елементів гра-
фа на скінченну множину, що складається з
натуральних чисел. Отримані образи нази-
вають мітками. Вершинам або ребрам поста-
вимо у відповідність ваги (суми міток), які
визначаються за певним правилом. Якщо всі
ваги однакові, мова йде про магічний тип
розмітки, якщо різні – про антимагічний. Для
вершинних (реберних) розміток областю
значень є множина вершин V (ребер E), а для
тотальних – множина VE. Вивчення магіч-
них розміток започатковано в роботі
Д. Седлячека 1963 року [1]. Він визначив ма-
гічну розмітку графа G, як таку бієкцію
множини ребер на множину натуральних чи-
сел, що ребра дістають різні мітки і суми мі-
ток ребер, інцидентних даній вершині, одна-
кові для кожної вершини. В 1970 році
А. Котціг
і А. Роса [2] тотальну розмітку f графа
G = (V, E), при якій кожне ребро отримує ва-
гу f(u)+f(v)+f(uv), де u, vV(G), uvE(G), на-
звали магічною за умови, що ваги всіх ребер
однакові та дорівнюють числу, яке назива-
ють магічною сталою. Щоб розрізнити ці
поняття, для останнього почали використо-
вувати термін реберно-магічна тотальна роз-
мітка. Н. Хартсфілд і Г. Рінгель у роботі [3]
1989 року заклали основи для анти-
магічного типу розміток. Антимагічна
розмітка графа G = (V, E) являє собою таку
бієкцію множини E на множину чисел 1, 2,...
ПРО ДИСТАНЦІЙНУ АНТИМАГІЧНУ РОЗМІТКУ ГРАФІВ
Теорія оптимальних рішень. 2016 27
…, |E|, що вершинні суми міток попарно різні, де вершинна сума – це сума мі-
ток ребер, інцидентних даній вершині. Означення (a, d) – реберно-антимагічної
тотальної розмітки запропоновано в 2000 році [4]. Це тотальна розмітка, при
якій ваги ребер утворюють арифметичну прогресію. В 2012 році, як наслідок
проведених досліджень, з’явилася (a, d) – дистанційна антимагічна розмітка,
введена С. Арумугамом і Н. Камачі [5].
Розмітки графів знайшли широке коло застосувань у теоретичних
дослідженнях, пов’язаних з вивченням розкладів графів та алгебраїчних комбі-
наторних структур, в теорії відображень, в теорії поля. Серед практичних засто-
сувань можна відмітити такі напрямки, як кодування радарних імпульсів, мере-
жеве планування, управління базами даних, астрономія.
Розглянемо скінченні неорієнтовані графи без кратних ребер та
петель. Під вагою w(u) вершини u графа G = (V, E), при вершинній розмітці f,
розуміємо суму міток вершин, суміжних з u, тобто
)(
)()(
uNv
vfuw ,
де vV(G) і N(u) – множина суміжності вершини u.
(a, d)-дистанційною антимагічною розміткою графа G = (V, E) порядку n
називається така бієкція f : V(G){1, 2, …, n}, що множина всіх ваг вершин
утворює арифметичну прогресію a, a + d, a + 2d, …, a + (n – 1)d з першим
членом a і різницею d, де a, d – фіксовані невід’ємні цілі числа і a ≥ 1, d 0.
Граф G, що допускає таку розмітку, називають (a, d)-дистанційним антимагіч-
ним графом.
С. Арумугам і Н. Камачі, які започаткували дану розмітку, отримали
декілька базових результатів [5]. Встановили необхідну умову існування
(a, d)-дистанційної антимагічної розмітки графа, довели, що цикл Cn буде
(a, d)-дистанційним антимагічним графом лише коли n – непарне і d = 1, а граф
C2n
+ є (2n + 2, 1)-дистанційним антимагічним графом. Також запропонували
дослідити основні класи графів на наявність такої розмітки. Наступний крок
зроблено в роботі [6], де досліджуються на дистанційну антимагічність ланцюги
Pn при 2 ≤ n ≤ 15, диз’юнктивне об’єднання ізоморфних копій циклу Cn, гол-
ландський вітряк Fn та графи з порядком меншим 6. Задачі, що розв’язуються в
[5 і 6] можна поділити на два типи. До першого віднесемо задачу знаходження
умов існування розмітки, а до другого – задачу визначення аналітичного опису
розмітки, який дозволяє знайти її безпосередньо побудовою. В даній статті роз-
глядається задача 1-го типу для циркулянтних графів. Також досліджено умови
існування (a, d)-дистанційної антимагічної розмітки графа Fn.
М.Ф. СЕМЕНЮТА
28 Теорія оптимальних рішень. 2016
В наступній лемі сформульована необхідна умова існування (a, d)-
дистанційної антимагічної розмітки графа G, де і – його мінімальний і мак-
симальний степені, відповідно.
Лема 1 [5]. Якщо граф G є (a, d)-дистанційним антимагічним порядку n, то
)1(2
)1()1(2
n
n
d
.
Наслідок 1 [5]. Якщо граф G є r-регулярним (a, d)-дистанційним антима-
гічним порядку n з r 2, то d r.
Необхідна і достатня умови існування (a, d)-дистанційної антимагічної роз-
мітки для 1-регулярного графа наведені в теоремі 1.
Теорема 1 [5]. Граф G є (1, 1)-дистанційним антимагічним тоді і тільки тоді,
коли кожна його компонента є ізоморфним образом P2.
Нехай s1, s2, …, sm, n – натуральні числа, такі, що 1 ≤ s1 s2 … sm n.
Неорієнтований граф Cn(s1, s2, …, sm) з множиною вершин V = {u1, u2, …, un}
і ребрами ),(
jsii uu
, для i = 1, 2, …, n, j = 1, 2, …, m, де i + sj береться за моду-
лем n, називають циркулянтним графом, а m – його розмірністю.
Елементи породжуваної множини S = s1, s2, …, sm називають твірними.
Параметричний опис C(n; S) повністю визначає циркулянтний граф порядку n
і розмірності m. Його степінь дорівнює 2m, якщо sm n/2. Якщо n парне
і sm = n/2, то C(n;S) є (2m – 1)-регулярним графом. В роботі [7] показано, що
циркулянтний граф C(n; S) є зв’язним, тоді і тільки тоді, коли найбільший спіль-
ний дільник (НСД) (s1, s2, …, sm, n) = 1. Граф C(n; S) буде двочастковим, якщо s1,
s2, …, sm – непарні, а n – парне [7].
Теорема 2. Циркулянтний граф Cn(s1, s2, …, sm), де smn/2
і НСД (s1, s2, …, sm, n) = 1, не допускає (a, d)-дистанційної антимагічної розміт-
ки, якщо d 1(mod2) і n 0(mod2).
Доведення. Припустимо, що існує (a, d)-дистанційна антимагічна розмітка f
для графа Cn(s1, s2, …, sm), де sm n/2 і НСД (s1, s2, …, sm, n) = 1.
Це 2m-регулярний зв’язний граф. Обчислимо суму ваг всіх його вершин:
2
)1(
)(2
1
ndn
anufm
n
i
i
. (1)
З рівності (1) маємо
2
)1(
)1(
nd
nma . (2)
З останньої рівності випливає, що
розмітка f може бути (a, d)-дистанційною
антимагічною лише в наступних випадках: d 1(mod2) і n 1(mod2)
або d 0(mod2).
ПРО ДИСТАНЦІЙНУ АНТИМАГІЧНУ РОЗМІТКУ ГРАФІВ
Теорія оптимальних рішень. 2016 29
Теорему доведено.
Теорема 3. Циркулянтний граф Cn(s1, s2, …, sm), де sm = n/2
і НСД (s1, s2, …, sm, n) = 1, не допускає (a, d)-дистанційної антимагічної розміт-
ки, якщо d 0(mod2).
Доведення. При sm = n/2 і НСД (s1, s2, …, sm, n) = 1, граф Cn(s1, s2, …, sm) яв-
ляє собою (2m – 1)-регулярний зв’язний граф парного порядку. Припустимо, що
для нього існує (a, d)-дистанційна антимагічна розмітка. Обчислимо суму ваг
всіх вершин і знайдемо значення a:
2
)1)(12(
ndm
da . (3)
Припущення виконується тільки при d 1(mod2), так як n 0(mod2)
за умовою.
Теорему доведено.
Теорема 4. Циркулянтний граф Cn(s), де s ≤ (n – 1)/2 є (a, 1)-дистанційним
антимагічним, якщо n – непарне і a 1. Циркулянтний граф Cn(n/2) є (1, 1)-ди-
станційним антимагічним.
Доведення. Якщо НСД (s, n) = 1 для непарного n і s ≤ (n – 1)/2, тоді Cn(s) –
цикл порядку n. Він допускає (a, 1)-дистанційну антимагічну розмітку
з a 1 [5].
Нехай s ≤ (n – 1)/2 і НСД (s, n) = h, тоді граф Cn(s) являє собою
диз’юнктивне об’єднання h копій циклу Cn/h. В такому разі, Cn(s) буде (a, 1)-
дистанційним антимагічним графом, коли n приймає непарні значення [6] і a
1.
Кожний циркулянтний граф Cn(n/2) є диз’юнктивним об’єднанням n копій
ланцюга P2, тому допускає (1, 1)-дистанційну антимагічну розмітку [5].
Теорему доведено.
Циркулянтний граф Cn(1, s) є 4-регулярним, якщо sn/2 і 3-регулярним,
якщо s = n/2. Оскільки НСД (1, s, n) = 1, то Cn(1, s) – зв’язний граф. Для нього
маємо результати, описані в наступних теоремах.
Теорема 5. Циркулянтний граф Cn(1, s), де sn/2, не допускає
(a, d)-дистанційної антимагічної розмітки, якщо n 0(mod2) і d = 1 або d = 3.
Доведення. Припустимо, що існує (a, d)-дистанційна антимагічна розмітка
для графа Cn(1, s), де s n/2. З леми 1 випливає, що d може приймати значення
менші, ніж 4. З рівності (2) маємо:
2
)1(
)1(2
nd
na .
М.Ф. СЕМЕНЮТА
30 Теорія оптимальних рішень. 2016
Якщо n 0(mod2) і d = 1 або d = 3, тоді a приймає не натуральні значення.
Прийшли до протиріччя з припущенням.
Теорему доведено.
Наслідок 1. Якщо циркулянтний граф Cn(1, s), де s n/2 допускає
(a, d)-дистанційну антимагічну розмітку, то n 1(mod2), d = 1 і a = (3n + 5)/2
або n 1(mod2), d = 3 і a = (n+7)/2, або d = 2 і a = n + 3.
Доведення наслідку випливає безпосередньо з теореми 4.
Циркулянтний граф C5(1, 2) – це повний граф порядку 5. Якщо визначити
його вершинну розмітку f, як f(ui) = i, де i = 1, …, 5, uiV(C5(1, 2)), то f є
(10, 1)-дистанційною антимагічною розміткою C5(1, 2).
На рисунку показано циркулянтний граф C7(1, 2). Задамо вершинну розміт-
ку f наступним чином:
f(u1) = 1, f(u2) = 4, f(u3) = 7, f(u4) = 3, f(u5) = 6, f(u6) = 2, f(u7) = 5,
де uiV(C7(1, 2)) для i = 1, …, 7.
Визначимо ваги вершин:
w(u1) = f(u2) + f(u3) + f(u6) + f(u7) = 18,
w(u2) = f(u1) + f(u3) + f(u4) + f(u7) = 16,
w(u3) = f(u1) + f(u2) + f(u4) + f(u5) = 14,
w(u4) = f(u2) + f(u3) + f(u5) + f(u6) = 19,
w(u5) = f(u3) + f(u4) + f(u6) + f(u7) = 17,
w(u6) = f(u1) + f(u4) + f(u5) + f(u7) = 15,
w(u7) = f(u1) + f(u2) + f(u5) + f(u6) = 13.
Вони утворюють арифметичну прогресію з першим членом a = 13 і різни-
цею d = 1. Тому розмітка f для C7(1, 2) є (13, 1)-дистанційною антимагічною.
РИСУНОК. Циркулянтний граф C7(1, 2)
u1 u2
u3
u4
u5
u6
u7
ПРО ДИСТАНЦІЙНУ АНТИМАГІЧНУ РОЗМІТКУ ГРАФІВ
Теорія оптимальних рішень. 2016 31
Циркулянтний граф Cn(1, n/2) при n = 4 є повним графом, він буде
(6, 1)-дистанційним антимагічним.
Якщо n = 6, то C6(1, 3) є повним двочастковим графом. Позначимо
V(C6(1, 3)) = u1, u2, u3, u4, u5, u6, тоді N(u1) = N(u2) = N(u3) = u2, u4, u6. З цього
випливає [5], що C6(1, 3) не допускає (a, d)-дистанційної антимагічної розмітки.
Далі дослідимо графи Cn(1, n/2), для яких n ≥ 8.
Теорема 6. Якщо для Cn(1, n/2), де n ≥ 8 існує (a, d)-дистанційна антимагіч-
на розмітка, то d = 1, a = n + 2.
Доведення. Cn(1, n/2) є 3-регулярним зв’язним графом парного порядку.
Припустимо, що існує (a, d)-дистанційна антимагічна розмітка даного графа,
тоді d = 1 або d = 2.
З рівності (3) маємо
2
)1)(3(
nd
da . Отже a = n + 2 при d = 1, а при
d = 2, не існує парних натуральних чисел n ≥ 8, що задовольняють рівності
1
2
2
n
a
, так як n 0(mod2).
Теорему доведено.
Голландський n-вітряк Fn (граф дружби) утворює n копій циклу порядку
три, кожні два з яких перетинаються тільки в одній, спільній для всіх циклів,
вершині. Результати відносно його дистанційної антимагічності у вигляді двох
теорем подано в [6]. В теоремі 5 пропонуємо простіший, ніж в [6], спосіб вста-
новлення умов існування (a, d)-дистанційної антимагічної розмітки Fn.
Теорема 7. Граф Fn допускає (a, d)-дистанційну антимагічну розмітку тоді
і тільки тоді, коли d = 1 і n = 1 або n = 2.
Доведення. Позначимо v вершину степеня 2n в графі Fn. Припустимо, що
існує (a, d)-дистанційна антимагічна розмітка f для Fn. Очевидно, що
n(2n + 1) ≤ w(v) ≤ n(2n + 3).
Якщо w(v) = n(2n + 1), то f(v) = 2n + 1 і для деякої вершини u вага прийме
значення w(u) = 4n + 1. Тоді w(v) – w(u) = 2n2 – 3n – 1. З іншого боку,
w(v) – w(u) ≤ 2n або 2n2 – 5n – 1 ≤ 0. Остання нерівність виконується лише при
n ≤ 2. Для n = 1 маємо цикл, тобто F1 = C3, який є (a, 1)-дистанційним антимагіч-
ним графом [5]. Для n = 2, d може приймати значення 1 або 2, в обох випадках
f(v) = 5. Іншим вершинам поставимо у відповідність мітки 1, 2, 3, 4 так, що су-
міжні вершини дістають мітки, які відрізняються на одиницю. Отримаємо
(6, 1)-дистанційну антимагічну розмітку F2. Нехай d = 2, тоді, додавши суми ваг
всіх вершин, знайдемо, що a = 1. Це неможливо, оскільки (1, 1)-дистанційним
антимагічним може бути лише граф, у якого кожна компонента є ізоморфним
образом P2 [5].
М.Ф. СЕМЕНЮТА
32 Теорія оптимальних рішень. 2016
Якщо w(v) = n(2n + 3), то f(v) = 1. Міркуючи аналогічно, отримаємо, що для
деякої вершини u її вага становить w(u) = 2n + 2 і w(v) – w(u) = 2n2 + n – 2 ≤ 2n
або 2n2 – n – 2 ≤ 0. Остання нерівність виконується лише при n = 1.
Нехай w(v) = n(2n + 2), розглянемо довільну вершину u, відмінну від v, її
вага набуває значення w(u) = f(v) + f(z), де u і z суміжні вершини. Тоді
w(v) – w(u) = 2n2 + 2n – (f(v) + f(z)) ≤ 2n або f(v) + f(z) ≥ 2n2. Остання нерівність
не має розв’язку для f(v) і f(z) з множини 1, 2, …, 2n+1.
Таким чином, Fn має (a, d)-дистанційну антимагічну розмітку лише при
d = 1 і n = 1 або n = 2.
Теорему доведено.
Висновок. Поняття (a, d)-дистанційної антимагічної розмітки виникло
порівняно недавно, в 2012 році, тому цей напрямок містить багато відкритих
проблем. Результати даної роботи є початком їх розв’язку.
М.Ф. Семенюта
О ДИСТАНЦИОННОЙ АНТИМАГИЧЕСКОЙ РАЗМЕТКЕ ГРАФОВ
Исследуется антимагический тип вершинной разметки графа. Для циркулянтных графов
найдено необходимое условие, а для голландской мельницы – необходимое и достаточное
условие существования (a, d)-дистанционной антимагической разметки.
M.F. Semeniuta
ON DISTANCE ANTIMAGIC LABELING OF GRAPHS
We studied the antimagic type of a vertex labeling of the graph. We have found necessary condition
for existence of (a, d)-distance antimagic labelling for circulation graphs, as well as necessary and
sufficient conditions for existence of (a, d)-distance antimagic labelling for a Dutch windmill graph.
1. Sedlacek J. Problem, 27 in: Theory of graphs and its applications // Proc. Symposium Smolenice.
– 1963. – P. 163 – 164.
2. Kotzig A., Rosa A. Magic valuations of finite graphs // Canad. Math. Bull. – 1970. – Vol. 13. –
P. 451 – 461.
3. Hartsfield N., Ringel G. Supermagic and antimagic graphs // J. Recreat. Math. – 1989. – Vol. 21,
N 2. – P. 107 – 115.
4. Simanjuntak R., Bertault F., Miller M. Two new (a, d)-antimagic graph labelings // Proc. of
Eleventh Australasian Workshop on Combinatorial Algorithms. – 2000. – Vol. 11. –
P. 179 – 189.
5. Arumugam S., Kamatchi N. On (a, d)-distance antimagic graphs // Australasian journal of com-
binatorics. – 2012. – Vol. 54. – P. 279 – 287.
6. Nalliah M. Antimagic labelings of graphs and digraphs: Ph. D. thesis // M. Nalliah. – The Na-
tional Centre for Advanced Research in Discrete Mathematics, University of Kalasalingam, 2014
– 135 p.
7. Heuberger C. On planarity and colorability of circulant graphs // Discrete Math. – 2003. –
Vol. 268. – P. 153–169.
ПРО ДИСТАНЦІЙНУ АНТИМАГІЧНУ РОЗМІТКУ ГРАФІВ
Теорія оптимальних рішень. 2016 33
Одержано 20.03.2016
|
| id | nasplib_isofts_kiev_ua-123456789-113015 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | XXXX-0013 |
| language | Ukrainian |
| last_indexed | 2025-11-30T14:07:57Z |
| publishDate | 2016 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Семенюта, М.Ф. 2017-01-31T16:13:28Z 2017-01-31T16:13:28Z 2016 Про дистанційну антимагічну розмітку графів / М.Ф. Семенюта // Теорія оптимальних рішень: Зб. наук. пр. — 2016. — № 2016. — С. 26-32. — Бібліогр.: 7 назв. — укр. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/113015 519.1 Досліджується антимагічний тип вершинної розмітки графа. Для циркулянтних графів знайдена необхідна умова, а для голландського вітряка – необхідна і достатня умови існування (a, d)-дистанційної антимагічної розмітки. Исследуется антимагический тип вершинной разметки графа. Для циркулянтных графов найдено необходимое условие, а для голландской мельницы – необходимое и достаточное условие существования (a, d)-дистанционной антимагической разметки. We studied the antimagic type of a vertex labeling of the graph. We have found necessary condition for existence of (a, d)-distance antimagic labelling for circulation graphs, as well as necessary and sufficient conditions for existence of (a, d)-distance antimagic labelling for a Dutch windmill graph. uk Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень Про дистанційну антимагічну розмітку графів О дистанционной антимагической разметке графов On distance antimagic labeling of graphs Article published earlier |
| spellingShingle | Про дистанційну антимагічну розмітку графів Семенюта, М.Ф. |
| title | Про дистанційну антимагічну розмітку графів |
| title_alt | О дистанционной антимагической разметке графов On distance antimagic labeling of graphs |
| title_full | Про дистанційну антимагічну розмітку графів |
| title_fullStr | Про дистанційну антимагічну розмітку графів |
| title_full_unstemmed | Про дистанційну антимагічну розмітку графів |
| title_short | Про дистанційну антимагічну розмітку графів |
| title_sort | про дистанційну антимагічну розмітку графів |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/113015 |
| work_keys_str_mv | AT semenûtamf prodistancíinuantimagíčnurozmítkugrafív AT semenûtamf odistancionnoiantimagičeskoirazmetkegrafov AT semenûtamf ondistanceantimagiclabelingofgraphs |