Частинні випадки задачі граціозності графів
Розглядаються частинні випадки задач з розробки модифікацій конструктивних методів породження граціозних дерев та використанню цих дерев у побудові граціозних одноциклічних графів Знайдено новий метод побудови граціозного дерева з ізоморфних дерев менших порядків. Отримано умови існування одноциклі...
Збережено в:
| Опубліковано в: : | Компьютерная математика |
|---|---|
| Дата: | 2015 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2015
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/168385 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Частинні випадки задачі граціозності графів / М.Ф. Семенюта // Компьютерная математика. — 2015. — № 2. — С. 96-102. — Бібліогр.: 11 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-168385 |
|---|---|
| record_format |
dspace |
| spelling |
Семенюта, М.Ф. 2020-05-01T08:04:51Z 2020-05-01T08:04:51Z 2015 Частинні випадки задачі граціозності графів / М.Ф. Семенюта // Компьютерная математика. — 2015. — № 2. — С. 96-102. — Бібліогр.: 11 назв. — укр. 2616-938Х https://nasplib.isofts.kiev.ua/handle/123456789/168385 519.1 Розглядаються частинні випадки задач з розробки модифікацій конструктивних методів породження граціозних дерев та використанню цих дерев у побудові граціозних одноциклічних графів Знайдено новий метод побудови граціозного дерева з ізоморфних дерев менших порядків. Отримано умови існування одноциклічних графів, конструкції яких пов’язані з граціозними деревами певного виду. Рассматриваются частные случаи задач по разработке модификаций конструктивных методов порождения грациозных деревьев и использованию этих деревьев в построении грациозных одноциклических графов. Найден новый метод построения грациозного дерева из изоморфных деревьев меньших порядков. Получены условия существования одноциклических графов, конструкции которых связаны с грациозными деревьями определенного вида. For some special cases, we consider the problem of developing modifications of constructive methods for obtaining graceful trees and of applying these trees to construct graceful single-cycle graphs. New method to construct a graceful tree from isomorphic trees of smaller order is found. Existence conditions are obtained for one-cycle graphs, whose constructions are connected with graceful trees of a certain type. uk Інститут кібернетики ім. В.М. Глушкова НАН України Компьютерная математика Инструментальные средства информационных технологий Частинні випадки задачі граціозності графів Частные случаи задачи грациозности графов Special cases of the graph gracefulness problem Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Частинні випадки задачі граціозності графів |
| spellingShingle |
Частинні випадки задачі граціозності графів Семенюта, М.Ф. Инструментальные средства информационных технологий |
| title_short |
Частинні випадки задачі граціозності графів |
| title_full |
Частинні випадки задачі граціозності графів |
| title_fullStr |
Частинні випадки задачі граціозності графів |
| title_full_unstemmed |
Частинні випадки задачі граціозності графів |
| title_sort |
частинні випадки задачі граціозності графів |
| author |
Семенюта, М.Ф. |
| author_facet |
Семенюта, М.Ф. |
| topic |
Инструментальные средства информационных технологий |
| topic_facet |
Инструментальные средства информационных технологий |
| publishDate |
2015 |
| language |
Ukrainian |
| container_title |
Компьютерная математика |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Частные случаи задачи грациозности графов Special cases of the graph gracefulness problem |
| description |
Розглядаються частинні випадки задач з розробки модифікацій конструктивних методів породження граціозних дерев та використанню цих дерев у побудові граціозних одноциклічних графів Знайдено новий метод побудови граціозного дерева з ізоморфних дерев менших порядків. Отримано умови існування одноциклічних графів, конструкції яких пов’язані з граціозними деревами певного виду.
Рассматриваются частные случаи задач по разработке модификаций конструктивных методов порождения грациозных деревьев и использованию этих деревьев в построении грациозных одноциклических графов. Найден новый метод построения грациозного дерева из изоморфных деревьев меньших порядков. Получены условия существования одноциклических графов, конструкции которых связаны с грациозными деревьями определенного вида.
For some special cases, we consider the problem of developing modifications of constructive methods for obtaining graceful trees and of applying these trees to construct graceful single-cycle graphs. New method to construct a graceful tree from isomorphic trees of smaller order is found. Existence conditions are obtained for one-cycle graphs, whose constructions are connected with graceful trees of a certain type.
|
| issn |
2616-938Х |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/168385 |
| citation_txt |
Частинні випадки задачі граціозності графів / М.Ф. Семенюта // Компьютерная математика. — 2015. — № 2. — С. 96-102. — Бібліогр.: 11 назв. — укр. |
| work_keys_str_mv |
AT semenûtamf častinnívipadkizadačígracíoznostígrafív AT semenûtamf častnyeslučaizadačigracioznostigrafov AT semenûtamf specialcasesofthegraphgracefulnessproblem |
| first_indexed |
2025-11-24T11:38:48Z |
| last_indexed |
2025-11-24T11:38:48Z |
| _version_ |
1850845846862561280 |
| fulltext |
96 Компьютерная математика. 2015, № 2
Розглядаються частинні випадки
задач з розробки модифікацій
конструктивних методів поро-
дження граціозних дерев та вико-
ристанню цих дерев у побудові
граціозних одноциклічних графів.
Знайдено новий метод побудови
граціозного дерева з ізоморфних
дерев менших порядків. Отримано
умови існування одноциклічних
графів, конструкції яких пов’язані
з граціозними деревами певного
виду.
М.Ф. Семенюта, 2015
УДК 519.1
М.Ф. СЕМЕНЮТА
ЧАСТИННІ ВИПАДКИ ЗАДАЧІ
ГРАЦІОЗНОСТІ ГРАФІВ
Вступ. Наприкінці 1960-х років у радіоастро-
номії набула популярності проблема, пов’я-
зана з оптимальним плануванням радіоантен
для сканування видимих областей небосхи-
лів. Вона сприяла появі теорії розміток гра-
фа, яка розпочала свій розвиток з математи-
чної задачі розкладу повного графа на копії
певного графа. Вперше в 1963 році ця задача
сформульована Г. Рингелем, відома як гіпо-
теза Рингеля, і полягає в наступному: для
кожного додатнього числа q існує розклад
повного графа K2q+1 на ізоморфні дерева з
q ребрами. Для її вирішення в 1967 році
А. Роса ввів α- та β-оцінки графа. С. Голомб
у 1972 році, незалежно, пропонує поняття
граціозної розмітки [1], яке тотожнє до
β-оцінки. Гіпотеза Рінгеля – Котціг – Роса,
що всі дерева граціозні, надихає на створен-
ня методів побудови граціозних дерев. Як
з’ясувалося, складність доведення гіпотези
пов’язана з тим, що не в кожному граціозно-
му дереві висячій вершині можна поставити
у відповідність мітку 0. Інакше, всі граціозні
дерева породжувалися б індуктивно з дерев
менших порядків. Тому виникли більш
складні методи генерації граціозних дерев,
перший з них розроблено в 1973 році [2]. Він
покладений в основу інших методів, описа-
них в роботах [3 – 8].
А. Роса, довівши теорему про те, що, якщо
G граціозний граф розміру q, то граф K2q+1
допускає G-розклад, поширює проблему по-
будови граціозної розмітки на різні типи
графів. Він також доводить необхідну умову
ЧАСТИННІ ВИПАДКИ ЗАДАЧІ ГРАЦІОЗНОСТІ ГРАФІВ
Компьютерная математика. 2015, № 2 97
існування граціозної розмітки графа G: якщо G – ейлерів граф з q 1 або
2(mod4), то G не допускає граціозної розмітки. Цей критерій дозволяє відкинути
певні сімейства графів з дослідження на граціозність.
В задачі граціозності розглядається питання про можливість адаптації мето-
дів побудови граціозних дерев на інші класи графів. У даній роботі запропоно-
вано новий спосіб побудови граціозного дерева на основі модифікації відомих
методів. Також розглянуто задачу граціозності для певного типу одноциклічних
графів.
Постановка проблеми. Будемо розглядати скінчені неорієнтовані графи
без петель і кратних ребер. Під порядком графа розуміємо число його вершин,
а під розміром – число ребер.
Граф G = (V , E ) називають підграфом графа G = (V, E), якщо V V,
E E. Максимальний зв’язний підграф графа G – компонента зв'язності або
просто компонента графа G. Якщо G – зв’язний граф, то mG – граф з m компо-
нентами, кожна з яких ізоморфна G. Також можна сказати, що mG = i
m
i
G
1
–
диз’юнктивне об’єднання графів Gi, кожний з яких – це копія графа G.
Маршрутом у графі вважається послідовність ребер та вершин, у якій вер-
шини чергуються з ребрами, послідовність починається з вершини і закінчуєть-
ся вершиною і кожні два сусідні елементи цієї послідовності інцидентні. Дов-
жина маршруту дорівнює кількості ребер у ньому. Маршрут називають ланцю-
гом, якщо всі його ребра різні. Ланцюг простий, якщо всі його вершини (а, отже,
і ребра) різні. Під відстанню між двома вершинами в графі розуміємо довжину
найкоротшого простого ланцюга, який з’єднує їх. У статті використовуються
стандартні позначення, зокрема, Pn – простий ланцюг.
Ін’єктивну функцію f: V 0, 1, 2, , q називають граціозною розміткою
графа G = (V, E) розміру q, якщо вона індукує таку реберну розмітку
f *: E{1, 2, 3, …, q}, що f * – бієкція і f *(uv) = f(u) – f(v) для будь-яких суміж-
них вершин u, vV(G). Граф G – граціозний, якщо він допускає граціозну роз-
мітку f. У випадку граціозного дерева функція f – бієктивна.
В роботі досліджується клас задач, які в загальному вигляді можна сформу-
лювати так: 1) розробити модифікації конструктивних методів породження гра-
ціозних дерев; 2) використати породжені граціозні дерева в побудові граціозних
одноциклічних графів.
В наступних розділах розглянуті частинні випадки наведеного класу задач.
Метод -побудови та його модифікації. Наведемо два конструктивних ме-
тоди формування граціозних дерев, основаних на методі -побудови [9, 10].
М.Ф. СЕМЕНЮТА
98 Компьютерная математика. 2015, № 2
Перший з них пов’язаний з розв’язанням частинного випадку задачі другого
класу, яка розглядається в наступному розділі. Опишемо його більш детально.
Означення 1 [9, 10]. Нехай S, Т – дерева, а u, v – вершини графів S, T, від-
повідно. Розглянемо дерево, отримане приєднанням однієї копії Т до кожної
вершини S, крім u, за допомогою ототожнення вершини v в окремій копії Т
з вершиною S. Позначають отримане дерево S+1T і його побудову називають
+1-побудовою.
Очевидно, що V(S+1T) = (V(S)–1)V(T) +1 і дерева S+1T, T+1S не ізо-
морфні в загальному випадку.
Теорема 1 [9]. Якщо дерева S і T мають граціозні розмітки f, g з f(u) = pS – 1
і g(v) = 0, де uV(S), vV(T) і pS – порядок S, то S+1T – граціозне дерево.
Вершини u і v приймаємо за корені дерев S, T, де uV(S), vV(T). Опишемо
процес побудови граціозної розмітки дерева S+1T, що задовольняє умові теоре-
ми 1, і назвемо його +1-граціозною побудовою.
Припустимо, що дерева S, T мають pS, pT вершин, відповідно. Тоді граф
S+1T містить pS – 1 копій Т. Побудуємо pS – 1 допоміжних розміток
g0, g1, …, 2spg для Т, здійснюючи розбиття його множини вершин, на дві під-
множини A, B таким чином, що корінь v належить A і, приймаючи
( ), якщо ,
( )
( 2) ( ), якщо .
T
i
s T
i p g x x A
g x
p i p g x x B
Підмножини A і B обираємо так, щоб A B = V(T) і кожне ребро T з’єднує
вершини з різних підмножин, тобто розглядаємо дерево T як двочастковий граф.
Отримаємо pS – 1 ізоморфних копій дерева Т з gi розмітками. Легко пока-
зати, що всі вершинні мітки різні, всі реберні мітки різні. Множинами ,
igV
,
igE використаних вершинних і реберних міток, є
igV = 0, 1, …, (pS – 1)pT – 1,
igE = 1, …, (pS – 1)pT – 1\pT, 2pT, …, (ps – 2)pT =
= 1, …, (pS – 1)pT\pT, 2pT, …, (p s– 1)pT.
В дереві S+1T кожній вершині х копії дерева S, відмінній від u, ставиться у
відповідність мітка gf (х), а вершині u – мітка (pS – 1)pT. В результаті для дерева
S+1T використовуються правильні вершинні мітки, тобто вершинні мітки, що
задовольняють умові граціозності.
Розглянемо мітки ребер S+1T – це копії ребер дерева S. Кожна вершина х із
копії S отримує мітку f(х)pT, тому представлена розмітка дерева S+1T, присвоює
ЧАСТИННІ ВИПАДКИ ЗАДАЧІ ГРАЦІОЗНОСТІ ГРАФІВ
Компьютерная математика. 2015, № 2 99
мітки pT, 2pT, …, (ps – 1)pT ребрам копії S. Отже, описана розмітка S+1T,
– граціозна і S+1T – граціозне дерево.
Метод +-побудови узагальнює, введений раніше в [3, 4], метод побудови
дерева, яке містить n ізоморфних копій дерева T порядку p. Автори [3, 4] у під-
граф з диз’юнктивного об’єднання копій T вводять, в одному випадку нову вер-
шину, яка з’єднується ребром з кожною копією вершини v в T, в іншому випад-
ку ізоморфні образи вершини v ототожнюються. Перше з нових дерев познача-
ють Tv
n(p), друге – Tv
n(p)*, і вони граціозні, якщо T граціозне дерево.
У даній статті створено новий спосіб побудови граціозного дерева, в основу
якого покладено комбінацію ідеї знаходження граціозного дерева Tv
n(p) [3] з
-побудовою. Опишемо цей спосіб.
Нехай T – граціозне дерево порядку p і f – така його граціозна розмітка, що
vV(T) є вершиною з найбільшою міткою, тобто f(v) = p – 1. Розглянемо ліс:
nT = i
n
i
T
1
, де Ti – ізоморфні копії дерева T, i = 1,2, …, n, вершина vi дерева Ti –
ізоморфний образ v з T. Побудуємо дерево, яке позначимо T *, додавши до графа
nT, ребра v1v2, v1v3, …, v1vn. Таким чином, T *= i
n
i
T
1
+ v1v2 + v1v3 + … + v1vn.
Можна сказати, що побудова T * є модифікацією методу -побудови з на-
кладанням додаткових умов на певну вершину v. В наступній теоремі з’ясовані
умови граціозності T *, а при її доведенні отримано формулу знаходження вер-
шинних міток для граціозної розмітки T *.
Теорема 2. Якщо T – граціозне дерево порядку p, то T * = i
n
i
T
1
+ v1v2 + v1v3 +
+… + v1vn – також граціозне дерево.
Доведення. Якщо p = 1, то T = P1, а T * є зіркою, тому T * – граціозне дерево.
Розглянемо p 2. Позначимо d(u) – відстань від вершини v до вершини u дерева
T порядку p. Інакше кажучи, d(u) реалізує двочастковість дерева. Припустимо,
що функція f – граціозна розмітка T з f(v) = p – 1. Нехай вершини us
i, viV(T *)
є ізоморфними образами вершин us, vV(T), відповідно, і us
i vi для будь-яких
i = 1,2, …, n, s1, 2, …, p. Задамо вершинну розмітку дерева T * наступним
чином:
1 ( ), якщо ( ) парне в ,
( )
( 1 ) 1 ( ), якщо ( ) непарне в ,s
s si
s s
i p f u d u T
u
n i p f u d u T
(vi) = (i – 1)p.
Покажемо, що буде ін’єктивною функцією. Доведення проведемо від
супротивного.
Розглянемо випадок, коли d(um) і d(uk) мають різну парність, um, ukV(T).
М.Ф. СЕМЕНЮТА
100 Компьютерная математика. 2015, № 2
1. Припустимо, що (um
i) = (uk
i). Тоді
ip – 1 – f(um) = (n + 1 – i) p– 1 – f(uk) f(uk) – f(um)=pn + 1 – 2i.
Так як f(uk) – f(um) p, то n + 1 – 2 = 0, а отже f(uk) – f(um) = 0, приходимо
до протиріччя.
2. Припустимо, що (um
i) = (uk
j). Тоді
ip – 1 – f(um) = (n + 1 – j)p – 1 – f(uk) f(uk) – f(um) = pn + 1 – i – j.
Аналогічно n + 1 – i – j = 0 і f(uk) – f(um) = 0, прийшли до протиріччя.
Наступний випадок, коли d(um) і d(uk) мають однакову парність, доводиться
аналогічно.
Отже – ін’єктивна функція з множини вершин V(T *) в множину чисел
{0, 1, 2, …, np – 1}.
Якщо um
iuk
i – ребро підграфа Ti дерева T *, то d(um) і d(uk) мають різну
парність. Знаходимо мітку цього ребра:
(um
i) – (uk
i) = ip – 1 – f(um) – (n + 1 – i)p + 1 + f(uk) = (n + 1 – 2i)p + f(um) – f(uk).
Маємо множину міток ребер підграфа
1
n
i
i
T
дерева T *:
1, 2, …, p – 1, p + 1, p + 2, …, 2p – 1, 2p + 1, 2p + 2,…, np – 1 =
= 1, 2, 3, …, np – 1\p, 2p, 3p, …, (n – 1)p,
яка складається з різних чисел.
Для ребер v1v2, v1v3, …, v1vn мітки отримуємо наступним чином:
(v1) – (vi) = 0 – (i – 1)p = (i – 1)p,
де i = 2, 3, …, n.
Мітки всіх ребер дерева T * різні. Таким чином, встановлена взаємно
однозначна відповідність між множиною ребер E(T *) і множиною чисел
{1, 2, …, p – 1, p, p + 1, …, 2p – 1, 2p, 2p + 1,…, np – 1}.
Отже, розмітка – граціозна і T * є граціозним графом. Теорему доведено.
Метод побудови граціозного дерева T *назвемо модифікованою граціозною
побудовою.
Про граціозність одноциклічного графа. Будемо використовувати метод
формування граціозних одноциклічних графів з граціозних дерев, отриманих
з допомогою +1-побудови. Розглянемо дерево S+1T порядку p і доведемо на-
ступну теорему.
ЧАСТИННІ ВИПАДКИ ЗАДАЧІ ГРАЦІОЗНОСТІ ГРАФІВ
Компьютерная математика. 2015, № 2 101
Теорема 3. Нехай S, T граціозні дерева порядку pS і pT (pSpT 2), відповідно,
такі: 1) корінь u – висяча вершина в дереві S+1T або 2) висяча вершина дерева T
має найбільшу мітку в його граціозній розмітці, тоді існує така вершина
wV(S+1T), де w u, що одноциклічний граф G = S+1T + uw буде граціозним.
Доведення. За умовою, дерево S+1T – граціозне і, згідно з +1-побудовою,
дерева S і T мають граціозні розмітки f, g з f(u) = pS – 1 і g(v) = 0, де uV(S),
vV(T). Якщо вершина u – висяча в S+1T, то за теоремою 7 [11] існує така
вершина wV(S+1T), що граф G = S+1T+uw буде граціозним.
Розглянемо випадок, коли для граціозного дерева S+1T порядку p вершина
u не є висячою. За теоремою 1, дерева S і T мають граціозні розмітки, які позна-
чимо f, g і f(u) = pS – 1, g(v) = 0, де uV(S), vV(T), pS – порядок S. Виходячи з
+1-граціозної побудови, вершина u буде суміжною з вершиною x, якій відпові-
дає мітка 0 в S+1T, тобто з копією вершини v, для якої f(x) = 0. Існує вершина
wV(T) з міткою 1 і w A, тобто g0(w) = 1 (або як w беремо вершину з міткою 1
+ (i + 2 – pS)pT, якщо w B). Припустимо, що z – висяча вершина дерева T, яка
має найбільшу мітку, тоді z суміжна з коренем v. Таким чином, g(z) = pT – 1 і ребру
vzE(T) відповідає мітка pT – 1. Так як z B в T, то g0(z) = (pS – 1)pT – 1 =
= p – 2. Отже, в дереві S+1T вершина z отримує мітку p – 2, і ребро vz – мітку p – 2.
Нехай – вершинна розмітка графа G. Задамо наступним чином,
(x) = gi(x) для всіх вершин x i-ої копії дерева T, крім z, i = 0, 1, …, pS – 2
і (z) = q = p. Якщо x – вершина дерева S, то (x) = gf(x)(v). Для вершини w маємо
(w) = g0(w) = 1, де w A ((w) = 2spg (w) = 1, де w B).
Розмітка , породжує реберну розмітку, що кожному ребру ставить у відпо-
відність абсолютну величину різниці міток інцидентних йому вершин. При роз-
мітці , мітки всіх ребер графа G = S+1T+uw з множини E(G)\{vz, uw}
збігаються з мітками цих ребер в дереві S+1T і утворюють множину 1, 2, …,
…, p – 1\{p – 2}. У графі G ребра vz, uw отримають мітки p і p – 2, відповідно.
Так як мітки всіх вершин і ребер при розмітці одноциклічного графа
G = S+1T + uw задовольняють умові граціозності, то він є граціозним. Теорему
доведено.
Висновок. В результаті проведеного дослідження створено новий метод
побудови граціозного дерева з ізоморфних дерев менших порядків. Запропоно-
вано ідею отримання граціозних одноциклічних графів, породжених деревом
певної конструкції. Надалі планується розглянути можливості адаптації методів
побудови граціозних дерев на інші класи графів.
М.Ф. Семенюта
ЧАСТНЫЕ СЛУЧАИ ЗАДАЧИ ГРАЦИОЗНОСТИ ГРАФОВ
М.Ф. СЕМЕНЮТА
102 Компьютерная математика. 2015, № 2
Рассматриваются частные случаи задач по разработке модификаций конструктивных методов
порождения грациозных деревьев и использованию этих деревьев в построении грациозных
одноциклических графов. Найден новый метод построения грациозного дерева из изоморф-
ных деревьев меньших порядков. Получены условия существования одноциклических гра-
фов, конструкции которых связаны с грациозными деревьями определенного вида.
M.F. Semenyuta
SPECIAL CASES OF THE GRAPH GRACEFULNESS PROBLEM
For some special cases, we consider the problem of developing modifications of constructive meth-
ods for obtaining graceful trees and of applying these trees to construct graceful single-cycle graphs.
New method to construct a graceful tree from isomorphic trees of smaller order is found. Existence
conditions are obtained for one-cycle graphs, whose constructions are connected with graceful trees
of a certain type.
1. Golomb S.W. How to number a graph // Graph Theory and Computing (ed. R.C. Read), Aca-
demic Press, New York, 1972. – P. 23 – 37.
2. Stanton R.A., Zanke C.R. Labeling of balanced trees // Proceedings of the Forth Southeastern
Conference on Combinatorics, Graph Theory and Computing, Boca Raton. – 1973. –
P. 479 – 495.
3. Koh K.M., Rogers D.G., Tan T. On graceful trees // Nanta Math. – 1977. – Vol.10, Issue 2. –
P. 207 – 211.
4. Koh K.M., Rogers D.G., Tan T. Two theorems on graceful trees // Discrete Math. – 1979. –
Vol. 26. – P. 141 – 148.
5. Jin D.J., Lee S.H., Liu H.L., Liu S.Z., Lu X.G., Zhang D. The radical product of graceul trees //
Comput. Math. Appl. – 1993. – Vol. 26, Issue 10. – P. 89 – 93.
6. Liu S.Z., Jin D.J., Lee S.H., Liu H.L., Lu X.G., Zhang D.The joint sum of graceful trees //
Comput. Math. Appl. – 1993. – Vol. 26, Issue 10. – P. 83 – 87.
7. Burzio M., Ferrarese G. The subdivision of a graceful tree is a graceful tree // Discrete Math. –
1998. – Vol. 181, Issue 1 – 3. – P. 275 – 281.
8. Edwards M., Howard L. A Survey of graceful trees // Atlantic Electronic Journal of
Mathematics. – 2006. – Vol. 1, Issue 1. – P. 5 – 30.
9. Stanton R., Zarnke C. Labeling of balanced trees // Proc. 4th Southeast Conf. Combin., Graph
Theory, Comput. – 1973. – P. 479 – 495.
10. Burzio M., Ferrarese G. The subdivision graph of a graceful tree is a graceful tree // Discrete
Math. – 1998. – Vol. 181. – P. 275 – 281.
11. Семенюта М.Ф. Грациозность одноциклических графов // Теорія оптимальних рішень. –
2015. – С. 10 – 15.
Одержано 15.05.2015
Про автора:
Семенюта Марина Фролівна,
кандидат фізико-математичних наук,
доцент Кіровоградської льотної академії НАУ.
|