Upper bound for the diameter of a tree in the quantum graph theory
UDC 519.177We study two Sturm – Liouville spectral problems on an equilateral tree with continuity and Kirchhoff conditions at internal vertices and Neumann conditions at pendant vertices (first problem) and with Dirichlet conditions at pendant vertices (second problem). The spectrum of each of thes...
Gespeichert in:
| Datum: | 2022 |
|---|---|
| Hauptverfasser: | , , , , , , , |
| Format: | Artikel |
| Sprache: | Ukrainisch |
| Veröffentlicht: |
Institute of Mathematics, NAS of Ukraine
2022
|
| Online Zugang: | https://umj.imath.kiev.ua/index.php/umj/article/view/7176 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Ukrains’kyi Matematychnyi Zhurnal |
| Завантажити файл: |  |
Institution
Ukrains’kyi Matematychnyi Zhurnal| _version_ | 1860512631491657728 |
|---|---|
| author | Boyko, O. P. Martynyuk, O. M. Pivovarchik, V. M. Бойко, Ольга Мартынюк, Ольга Бойко, О. П. Мартинюк, О. М. Пивоварчик, В. М. |
| author_facet | Boyko, O. P. Martynyuk, O. M. Pivovarchik, V. M. Бойко, Ольга Мартынюк, Ольга Бойко, О. П. Мартинюк, О. М. Пивоварчик, В. М. |
| author_sort | Boyko, O. P. |
| baseUrl_str | https://umj.imath.kiev.ua/index.php/umj/oai |
| collection | OJS |
| datestamp_date | 2022-10-24T09:23:21Z |
| description | UDC 519.177We study two Sturm – Liouville spectral problems on an equilateral tree with continuity and Kirchhoff conditions at internal vertices and Neumann conditions at pendant vertices (first problem) and with Dirichlet conditions at pendant vertices (second problem). The spectrum of each of these problems consists of infinitely many normal (isolated Fredholm) eigenvalues. It is shown that, knowing the asymptotics of the eigenvalues, it is possible to estimate the diameter of a tree from above for each of these problems. |
| doi_str_mv | 10.37863/umzh.v74i8.7176 |
| first_indexed | 2026-03-24T03:31:51Z |
| format | Article |
| fulltext |
DOI: 10.37863/umzh.v74i8.7176
УДК 519.177
О. П. Бойко, О. М. Мартинюк, В. М. Пивоварчик1,2 (Пiвденноукр. нац. пед. ун-т iм. К. Д. Ушинського,
Одеса)
ВЕРХНЯ МЕЖА ДЛЯ ДIАМЕТРА ДЕРЕВА У КВАНТОВIЙ ТЕОРIЇ ГРАФIВ
We study two Sturm – Liouville spectral problems on an equilateral tree with continuity and Kirchhoff conditions at internal
vertices and Neumann conditions at pendant vertices (first problem) and with Dirichlet conditions at pendant vertices (second
problem). The spectrum of each of these problems consists of infinitely many normal (isolated Fredholm) eigenvalues. It
is shown that, knowing the asymptotics of the eigenvalues, it is possible to estimate the diameter of a tree from above for
each of these problems.
Розглянуто двi спектральнi задачi Штурма – Лiувiлля на рiвносторонньому деревi з умовами неперервностi i Кiрх-
гофа у внутрiшнiх вершинах та умовами Неймана у висячих вершинах i з умовами Дiрiхле у висячих вершинах
вiдповiдно. Спектр кожної з цих задач складається з нескiнченної кiлькостi нормальних (iзольованих фредгольмо-
вих) власних значень. Показано, що знаючи асимптотики власних значень, можна оцiнити зверху дiаметр дерева
для кожної з цих задач.
1. Вступ. У роботi дослiджуються спектральнi задачi Штурма – Лiувiлля на рiвносторонньому
метричному деревi з умовами Неймана й умовами Дiрiхле на висячих вершинах та умовами
неперервностi та Кiрхгофа у внутрiшнiх вершинах. Ця тема належить до так званої теорiї
квантових графiв (див., наприклад, [1]). Цi задачi виникають при описi руху квантової частинки
у тонкому хвильоводi, який має форму дерева.
Припускаємо, що потенцiали рiвнянь Штурма – Лiувiлля на ребрах є дiйсними L2-функцiями.
Кiлькiсть p вершин дерева скiнченна. Спектр такої задачi складається з нескiнченної послiдов-
ностi нормальних (iзольованих фредгольмових) власних значень, якi прямують до нескiнчен-
ностi. Послiдовнiсть цих власних значень можна подати як об’єднання таких пiдпослiдов-
ностей, що перший (головний) член асимптотики залежить лише вiд довжини ребра та вiд
кiлькостi ребер. Вiдомо (див. [6 – 8]), що якщо потенцiали на ребрах графа однаковi i симетрич-
нi щодо середини ребра, то iснує зв’язок мiж спектром задачi Штурма – Лiувiлля на графi i
спектром так званого дискретного лапласiана цього графа. Рiзнi автори користуються рiзними
означеннями дискретного лапласiана (див., наприклад, [5]). Ми використовуємо таке: дискрет-
ний лапласiан графа — це матриця \~A = D - 1/2AD - 1/2, де A — матриця сумiжностi графа,
D = \mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}
\bigl\{
d(v1), d(v2), . . . , d(vp)
\bigr\}
— матриця степенiв вершин, d(vi) — степiнь вершини vi.
Вищезгаданий зв’язок полягає в тому, що другi члени асимптотичного розвинення пiдпослi-
довностей безпосередньо однозначно пов’язанi з власними значеннями дискретного лапласiана
дерева. Умови однаковостi потенцiалiв на ребрах i симетрiї їх щодо середини ребра викону-
ються у так званому незбуреному випадку, тобто коли потенцiали рiвняння Штурма – Лiувiлля
на ребрах qj \equiv 0 для всiх j. Отже, у цьому випадку такий зв’язок iснує. Якщо потенцiали на
ребрах — довiльнi дiйснi L2-функцiї, то згiдно з результатами роботи [9] (теорема 5.4) перший
i другий члени асимптотики власних значень не залежать вiд потенцiалiв, а залежать лише вiд
1 Вiдповiдальний за листування, e-mail: vpivovarchik@gmail.com.
2 Пiдтримано Мiнiстерством освiти i науки України за темою „Штучнi матерiали як основа створення новiтнiх
бiосенсорiв” (https://mon.gov.ua/storage/app/uploads/public/61f/944/3d1/61f9443d16f00443598040.pdf).
c\bigcirc О. П. БОЙКО, О. М. МАРТИНЮК, В. М. ПИВОВАРЧИК, 2022
1020 ISSN 1027-3190. Укр. мат. журн., 2022, т. 74, № 8
ВЕРХНЯ МЕЖА ДЛЯ ДIАМЕТРА ДЕРЕВА У КВАНТОВIЙ ТЕОРIЇ ГРАФIВ 1021
форми дерева. Питання про можливiсть встановлення форми графа виходячи з асимптотики
власних значень розглянуто у [10, 11]. Воно тiсно пов’язане з питанням iснування коспектраль-
них (iзоспектральних) графiв у класичнiй теорiї графiв (див., наприклад, [2]).
Оскiльки iснують коспектральнi дерева i у квантовiй теорiї графiв (див., наприклад, [14]), то
з огляду на асимптотику власних значень не можна в деяких випадках однозначно встановити
форму дерева. У данiй роботi ми розглядаємо питання лише про знаходження верхньої межi
для дiаметра дерева.
У пунктi 2 наведено опис двох задач Штурма – Лiувiлля на рiвносторонньому деревi з
умовами неперервностi i Кiрхгофа у внутрiшнiх вершинах та умовами Неймана у висячих
вершинах i умовами Дiрiхле у висячих вершинах вiдповiдно.
У пунктi 3 наведено асимптотичнi розвинення для власних значень задач Неймана i Дiрiхле
та показано зв’язок мiж коефiцiєнтами других членiв цих асимптотик з власними значеннями
дискретного лапласiана, який вiдповiдає розглянутому дереву.
У пунктi 4 отримано верхнi межi для дiаметра дерева через кiлькiсть рiзних коефiцiєнтiв у
других членiв асимптотичних розвинень для власних значень задач Неймана та Дiрiхле.
У пунктi 5 наведено приклади дерев, для яких отриманi верхнi межi збiгаються з їхнiми
дiаметрами, а також приклади, у яких не збiгаються.
2. Спектральнi задачi. Нехай T — метричне рiвностороннє дерево з g = p - 1 ребром
однакової довжини l. Позначимо через vi вершини, через d(vi) степенi вершин, через ej ребра.
Нехай P = v1v2, v2v3, . . . , vLvL+1 — найдовший простий ланцюг у T (або один iз найдовших,
якщо є кiлька з найбiльшою довжиною). Довжину L цього ланцюга називають комбiнаторним
дiаметром дерева. Виберемо один iз кiнцiв P (вершину v1) як корiнь дерева. Спрямуємо всi
ребра вiд кореня. Таким чином, степiнь входу кожної вершини, окрiм кореня, d+(vi) = 1, а
степiнь виходу d - (vi) = d(vi) - 1. Степiнь входу кореня дорiвнює 0, а степiнь виходу кореня
— 1. Позначимо через W - (vi) множину iндексiв js, s = 1, 2, . . . , d - (vi), ребер, що виходять з
vi, а через ji iндекс ребра, що входить у vi.
Локальнi координати на ребрi ej ототожнюємо з точками iнтервалу [0, l] таким чином, що
координата зростає зi зростанням вiдстанi вiд кореня. Це означає, що висячим вершинам (крiм
кореня) вiдповiдає локальна координата l. Кореню вiдповiдає локальна координата 0. Кожна
внутрiшня вершина має локальну координату l на вхiдному ребрi та локальну координату 0 на
кожному вихiдному ребрi. Функцiя yj на ребрi ej задовольняє рiвняння Штурма – Лiувiлля
- y\prime \prime j + qj(x)yj = \lambda yj , j = 1, 2, . . . , g, (1)
де qj — дiйсна функцiя, що належить до L2(0, l). У кожнiй внутрiшнiй вершинi vi з вихiдними
ребрами ej , j \in W - (vi), та вхiдним ребром ek накладаємо умови неперервностi
yj(0) = yk(l), j \in W - (vi), (2)
й умову Кiрхгофа
y\prime k(l) =
\sum
j\in W - (vi)
y\prime j(0). (3)
Ми розглянемо двi спектральнi задачi: задачу Неймана i задачу Дiрiхле.
ISSN 1027-3190. Укр. мат. журн., 2022, т. 74, № 8
1022 О. П. БОЙКО, О. М. МАРТИНЮК, В. М. ПИВОВАРЧИК
Для задачi Неймана на кожнiй висячiй вершинi (крiм кореня), iнцидентнiй ребру ej , накла-
даємо крайову умову Неймана
y\prime j(l) = 0, (4)
а у коренi умова Неймана має вигляд
y\prime 1(0) = 0. (5)
Для задачi Дiрiхле на кожнiй висячiй вершинi (крiм кореня), iнцидентнiй ребру ej , накла-
даємо крайову умову Дiрiхле
yj(l) = 0, (6)
а у коренi умова Дiрiхле має вигляд
y1(0) = 0. (7)
Позначимо через sj
\bigl( \surd
\lambda , x
\bigr)
розв’язок рiвняння Штурма – Лiувiлля (1) на ребрi ej , який за-
довольняє умову sj
\bigl( \surd
\lambda , 0
\bigr)
= s\prime j
\bigl( \surd
\lambda , 0
\bigr)
- 1 = 0, а через cj
\bigl( \surd
\lambda , x
\bigr)
розв’язок, який задовольняє
умову cj
\bigl( \surd
\lambda , 0
\bigr)
- 1 = c\prime j
\bigl( \surd
\lambda , 0
\bigr)
= 0. Тодi характеристичну функцiю, тобто цiлу функцiю,
множина коренiв якої збiгається зi спектром задачi (1) – (5) (цю функцiю визначено з точ-
нiстю до сталого множника), можна виразити через sj
\bigl( \surd
\lambda , l
\bigr)
, s\prime j
\bigl( \surd
\lambda , l
\bigr)
, cj
\bigl( \surd
\lambda , l
\bigr)
i c\prime j
\bigl( \surd
\lambda , l
\bigr)
.
Для цього розглянемо систему вектор-функцiй \psi j(\lambda , x) = \mathrm{c}\mathrm{o}\mathrm{l}
\bigl\{
0, 0, . . . , sj
\bigl( \surd
\lambda , x
\bigr)
, . . . , 0
\bigr\}
та
\psi j+g(\lambda , x) = \mathrm{c}\mathrm{o}\mathrm{l}
\bigl\{
0, 0, . . . , cj
\bigl( \surd
\lambda , x
\bigr)
, . . . , 0
\bigr\}
для j = 1, 2, . . . , g. Так, як i у [13] (теорема 3.3),
позначимо через Lj , j = 1, 2, . . . , 2g, лiнiйнi функцiонали, що утворенi вiдповiдно до рiвнянь
(1) – (5). Тодi \Phi N (\lambda ) = \| Lj(\psi k(\lambda , x)\| 2gj,k — характеристична матриця, що вiдповiдає системi
лiнiйних рiвнянь, якi описують умови неперервностi i Кiрхгофа у внутрiшнiх вершинах. Її
визначник
\phi N (\lambda ) := \mathrm{d}\mathrm{e}\mathrm{t}(\Phi N (\lambda ))
є характеристичною функцiєю задачi (1) – (5).
Аналогiчно визначається \phi D — характеристична функцiя задачi Дiрiхле (1) – (3), (6), (7).
3. Допомiжнi результати. Для простого графа матриця A = (Ai,j)
p
i,j=1, де Ai,i = 0 i для
всiх i = 1, 2, . . . , p i для всiх j \not = i
Ai,j =
\left\{ 1, якщо vi i vj сумiжнi,
0, якщо не сумiжнi,
називається матрицею сумiжностi. Позначимо через
D = \mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}
\bigl\{
d(v1), d(v2), . . . , d(vp)
\bigr\}
матрицю степенiв вершин. Тодi назвемо\widetilde A = D - 1/2AD - 1/2 (8)
дискретним лапласiаном, або зваженою матрицею сумiжностi.
Коренi визначника лапласiана становлять спектр задачi, яка виникає в класичнiй спектраль-
нiй теорiї графiв. Така задача тiсно пов’язана зi скiнченновимiрними задачами, якi описують
коливання стiльтьєсiвських струн (див., наприклад, [4]). Зв’язок мiж задачею (1) – (5) та дис-
кретним лапласiаном встановлює така теорема.
ISSN 1027-3190. Укр. мат. журн., 2022, т. 74, № 8
ВЕРХНЯ МЕЖА ДЛЯ ДIАМЕТРА ДЕРЕВА У КВАНТОВIЙ ТЕОРIЇ ГРАФIВ 1023
Теорема 1 (див. теорему 5.2 у [10]). Нехай T — дерево з p \geq 2 вершинами i qj \equiv 0
для всiх j. Тодi спектр задачi (1) – (5) збiгається з множиною коренiв функцiї\surd
\lambda
\bigl(
\mathrm{s}\mathrm{i}\mathrm{n}
\surd
\lambda l
\bigr) - 1
\phi N
\bigl(
\mathrm{c}\mathrm{o}\mathrm{s}
\surd
\lambda l
\bigr)
.
Наслiдок 1. Якщо qj \equiv 0 для всiх j = 1, . . . , g, то власнi значення задачi (1) – (5) можна
подати як об’єднання пiдпослiдовностей
\bigl\{
\~\lambda k
\bigr\} \infty
k=1
=
2g\bigcup
i=1
\Bigl\{
\~\lambda
(i)
k
\Bigr\} \infty
k=1
, занумерованих так, що
\~\lambda
(i)
k \leq \~\lambda
(i)
k+1 i\sqrt{}
\~\lambda
(i)
k =
2\pi (k - 1)
l
\pm 1
l
\mathrm{a}\mathrm{r}\mathrm{c}\mathrm{c}\mathrm{o}\mathrm{s}\alpha i для i = 2, 3, . . . , p - 1, k = 1, 2 . . . , (9)\sqrt{}
\~\lambda
(1)
k =
\pi (k - 1)
l
k = 1, 2, . . . . (10)
Тут \alpha 1 = 1, \alpha 2, \alpha 3, . . . , \alpha p - 1, \alpha p = - 1 — власнi значення дискретного лапласiана \~A.
За теоремою 5.4 роботи [9], навiть якщо потенцiали на ребрах рiзнi та не симетричнi щодо
середин ребер, але належать простору L2(0, l), виконується нерiвнiсть
\bigm| \bigm| \bigm| \lambda (i)k - \~\lambda
(i)
k
\bigm| \bigm| \bigm| \leq C < \infty
для всiх i та k, де \lambda k — власнi значення задачi (1) – (5), а \~\lambda k — власнi значення цiєї ж задачi при
qj \equiv 0 для всiх j. З цього та наслiдку 1 випливає наступний результат для загального випадку,
тобто коли потенцiали qj не є тотожно нульовими.
Теорема 2 (теорема 5.3 з [10]). Нехай T — рiвностороннє матричне дерево, а потенцiали
qj \in L2(0, l) — дiйснi функцiї. Тодi власнi значення задачi (1) – (5) можна подати як об’єднання
пiдпослiдовностей \{ \lambda k\} \infty k=1 =
2g\bigcup
i=1
\Bigl\{
\lambda
(i)
k
\Bigr\} \infty
k=1
з асимптотиками
\sqrt{}
\lambda
(i)
k =
k\rightarrow \infty
2\pi (k - 1)
l
\pm 1
l
\mathrm{a}\mathrm{r}\mathrm{c}\mathrm{c}\mathrm{o}\mathrm{s}\alpha i +O
\biggl(
1
k
\biggr)
для i = 2, 3, . . . , p - 1, k = 1, 2, . . . , (11)\sqrt{}
\lambda
(1)
k =
k\rightarrow \infty
\pi (k - 1)
l
+O
\biggl(
1
k
\biggr)
, k = 1, 2, . . . . (12)
Тепер перейдемо до опису спектра задачi (1) – (3), (6), (7). Тут нам будуть потрiбнi деякi
поняття.
Нехай \^T — дерево, отримане видаленням всiх висячих вершин дерева T разом iз iнци-
дентними з ними ребрами. Для зручностi позначимо висячi вершини дерева T через vp - r+1,
vp - r+2, . . . , vp, а внутрiшнi вершини T, тобто вершини дерева \^T , через v1, v2,. . . , vp - r. Нехай
\^A — матриця сумiжностi дерева \^T , а \^DT = \mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}
\bigl\{
d(v1), d(v2), . . . , d(vp - 1)
\bigr\}
, де d(vi) — степiнь
вершини vi у деревi T. Розглянемо многочлен
PT, \^T (z) := \mathrm{d}\mathrm{e}\mathrm{t}
\Bigl(
z \^DT - \^A
\Bigr)
. (13)
Наступна теорема є окремим випадком теореми 6.4.2 [12].
Теорема 3. Нехай T — рiвностороннє дерево з принаймнi двома ребрами довжини l. По-
тенцiали на ребрах однаковi та симетричнi щодо середин ребер
\bigl(
q(l - x) = q(x)
\bigr)
. Тодi спектр
задачi (1) – (3), (6), (7) збiгається з множиною коренiв характеристичної функцiї
\phi D(\lambda ) = sr - 1
\bigl( \surd
\lambda , l
\bigr)
PT, \^T
\Bigl(
c
\bigl( \surd
\lambda , l
\bigr) \Bigr)
,
ISSN 1027-3190. Укр. мат. журн., 2022, т. 74, № 8
1024 О. П. БОЙКО, О. М. МАРТИНЮК, В. М. ПИВОВАРЧИК
де PT, \^T — многочлен, означений рiвнянням (13), s
\bigl( \surd
\lambda , x
\bigr)
i c
\bigl( \surd
\lambda , x
\bigr)
— розв’язки рiвняння
Штурма – Лiувiлля на ребрi, якi задовольняють умови s
\bigl( \surd
\lambda , 0
\bigr)
= s\prime
\bigl( \surd
\lambda , 0
\bigr)
- 1 = 0 i c
\bigl( \surd
\lambda , 0
\bigr)
-
- 1 = c\prime
\bigl( \surd
\lambda , 0
\bigr)
= 0.
Наслiдок 2. Якщо qj \equiv 0 для всiх j, то власнi значення задачi (1) – (5), (6), (7) можна
подати як об’єднання пiдпослiдовностей
\bigl\{
\~\lambda k
\bigr\} \infty
k=1
=
2g\bigcup
i=1
\Bigl\{
\~\lambda
(i)
k
\Bigr\} \infty
k=1
, занумерованих так, що
\~\lambda
(i)
k \leq \~\lambda
(i)
k+1\sqrt{}
\~\lambda
(i)
k =
2\pi (k - 1)
l
\pm 1
l
\mathrm{a}\mathrm{r}\mathrm{c}\mathrm{c}\mathrm{o}\mathrm{s}\alpha i для i = 1, 2, . . . , p - r, k = 1, 2, . . . , (14)\sqrt{}
\~\lambda
(i)
k =
\pi (k - 1)
l
, i = p - r + 1, p - r + 2, . . . , p, r = 1, 2, . . . . (15)
Тут \alpha 1, \alpha 2, . . . , \alpha p - r — коренi многочлена PT, \^T (z).
Доведення. Якщо qj \equiv 0, то s
\bigl( \surd
\lambda , l
\bigr)
=
\mathrm{s}\mathrm{i}\mathrm{n}
\surd
\lambda l\surd
\lambda
, c
\bigl( \surd
\lambda , l
\bigr)
= \mathrm{c}\mathrm{o}\mathrm{s}
\surd
\lambda l i
\phi D(\lambda ) =
\mathrm{s}\mathrm{i}\mathrm{n}r - 1
\surd
\lambda l\bigl( \surd
\lambda
\bigr) r - 1 PT, \^T
\bigl(
\mathrm{c}\mathrm{o}\mathrm{s}
\surd
\lambda l
\bigr)
.
Звiдси випливають асимптотичнi розвинення (14), (15).
Знову використовуючи теорему 5.4 [9], отримуємо таку теорему.
Теорема 4. Власнi значення задачi (1) – (5), (6), (7) можна подати як об’єднання пiдпослi-
довностей \{ \lambda k\} \infty k=1 =
2g\bigcup
i=1
\Bigl\{
\lambda
(i)
k
\Bigr\} \infty
k=1
, занумерованих так, що \lambda (i)k \leq \lambda
(i)
k+1 i
\sqrt{}
\lambda
(i)
k =
k\rightarrow \infty
2\pi (k - 1)
l
\pm 1
l
\mathrm{a}\mathrm{r}\mathrm{c}\mathrm{c}\mathrm{o}\mathrm{s}\alpha i +O
\biggl(
1
k
\biggr)
для i = 1, 2, . . . , p - r, k = 1, 2, . . . , (16)\sqrt{}
\lambda
(i)
k =
k\rightarrow \infty
\pi (k - 1)
l
+O
\biggl(
1
k
\biggr)
, i = p - r + 1, p - r + 2, . . . , p, k = 1, 2, . . . . (17)
4. Основнi результати. В цьому пунктi ми знайдемо верхнi межi для дiаметра рiвносторон-
нього метричного дерева, якi можна отримати використовуючи асимптотики власних значень
задачi (1) – (5) та власних значень задачi (1) – (3), (6), (7). Як ми бачили у попередньому пунктi,
знаючи головнi члени асимптотик (11), (12) або (16), (17), ми можемо знайти довжину ребра
l та кiлькiсть p вершин дерева. Знаючи спектр \{ \lambda k\} \infty k=1, ми можемо знайти всi коефiцiєнти
\alpha i — власнi значення дискретного лапласiана цього дерева у випадку задачi (1) – (5) та власнi
значення модифiкованого дискретного лапласiана \^D
- 1
2
T
\^A \^D
- 1
2
T внутрiшнього дерева у випадку
задачi (1) – (3), (6), (7) як точки накопичення послiдовностi
\bigl\{
\mathrm{c}\mathrm{o}\mathrm{s}
\bigl( \surd
\lambda k
\bigr) \bigr\} \infty
k=1
.
У роботi [10] для задачi з умовами Неймана на висячих вершинах доведено, що якщо
кiлькiсть вершин дерева не перевищує 8, то множина \{ \alpha i\} однозначно визначає форму дерева.
Проте вже у випадку кiлькостi вершин 9 iснують два неiзометричних дерева з однаковими
спектрами [14]. В цiй же роботi наведено два приклади пар неiзометричних дерев з кiлькiстю
вершин 10 з однаковими спектрами задачi з умовами Неймана на висячих вершинах (див. рис. 2
у роботi [14]). У кожному з цих двох випадкiв коспектральнi дерева мають рiзнi дiаметри. Отже,
ISSN 1027-3190. Укр. мат. журн., 2022, т. 74, № 8
ВЕРХНЯ МЕЖА ДЛЯ ДIАМЕТРА ДЕРЕВА У КВАНТОВIЙ ТЕОРIЇ ГРАФIВ 1025
дiаметр дерева є характеристикою, за якою можна, принаймнi у деяких випадках, вiдрiзняти
коспектральнi дерева. Таким чином, знаходження верхньої межi для дiаметра дерева є важливим
питанням.
Ми спочатку отримаємо оцiнку дiаметра дерева для випадку умов Неймана на висячих
вершинах, тобто використовуючи спектр задачi (1) – (5).
Теорема 5. Дiаметр метричного рiвностороннього дерева T не перевищує l(m + 1), де
m — кiлькiсть рiзних елементiв у множинi коефiцiєнтiв \{ \alpha i\} p - 1
i=2 у других членах асимпто-
тичних розвинень (11) власних значень задачi Неймана (1) – (5).
Доведення. Скористаємося теоремою 2 [3]. З цiєї теореми випливає, що кiлькiсть рiзних
власних значень дискретного лапласiана \~A не менша, нiж кiлькiсть ребер у найдовшому прос-
тому ланцюгу в деревi плюс 1.
Нехай вiдомi асимптотики (11). Власнi значення \alpha 1 = 1 та \alpha p = - 1 однократнi (див.
[5], лема 1.7, твердження (iv) та (v)), i, отже, кiлькiсть рiзних елементiв у множинi \{ \alpha i\} p - 1
i=2
дорiвнює кiлькостi рiзних власних значень матрицi \~A мiнус 2. Використовуючи теорему 2 [3],
отримуємо твердження теореми 5.
Розглянемо тепер задачу Дiрiхле (1) – (3), (6), (7).
Теорема 6. Метричний дiаметр рiвностороннього дерева T не перевищує ( \^m + 1)l, де
\^m — кiлькiсть рiзних коефiцiєнтiв серед \alpha i у розвиненнях (16) для власних значень задачi
Дiрiхле (1) – (3), (6), (7).
Доведення. Скористаємося теоремою 3. Для внутрiшнього дерева \^T , отриманого з дерева T
видаленням висячих вершин та iнцидентних з ними ребер, матриця \^A має розмiр (p - r)\times (p - r),
де r — кiлькiсть висячих вершин у дерева T. Рiвняння
\bigl(
\lambda \^DT - \^A
\bigr)
Y = 0 має нетривiальний
розв’язок при тих \lambda , якi є власними значеннями матрицi \^D - 1/2 \^A \^D - 1/2. Ми знову скориста-
ємося теоремою 2 [3], але вже для внутрiшнього дерева. За цiєю теоремою кiлькiсть рiзних
власних значень \^m матрицi \^D - 1/2 \^A \^D - 1/2 не менша, нiж комбiнаторний дiаметр дерева \^T
плюс 1. Кiлькiсть \^m рiзних коефiцiєнтiв серед \alpha i у розвиненнях (16) для власних значень
задачi Дiрiхле (1) – (3), (6), (7) не менша, нiж комбiнаторний дiаметр дерева \^T плюс 1.
Вочевидь, комбiнаторний дiаметр дерева T на 2 бiльший, нiж комбiнаторний дiаметр дерева
\^T . Отже, приходимо до висновку теореми.
Зауваження. Для багатьох графiв знайденi верхнi межi збiгаються з дiаметрами. Але на-
веденi нижче приклади показують, що не для всiх.
5. Приклади. 1. Розглянемо задачу Неймана на рiвнобiчному графi P4 (простий ланцюг з
чотирма вершинами), дiаметр якого дорiвнює 3l. У цьому випадку D = \mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}\{ 1, 2, 2, 1\} i
A =
\left(
0 1 0 0
1 0 1 0
0 1 0 1
0 0 1 0
\right) .
Знаходимо \alpha 1 = 1, \alpha 2 =
1
2
, \alpha 3 = - 1
2
, \alpha 4 = - 1 i, отже, m = 2 i (m+ 1)l = 3l. Таким чином,
дiаметр дерева дорiвнює (m+ 1)l.
2. Розглянемо задачу Дiрiхле на тому ж рiвнобiчному графi P4. У цьому випадку внутрiш-
нiй пiдграф — це P2. В цьому випадку \^D = \mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}\{ 2, 2\} i
ISSN 1027-3190. Укр. мат. журн., 2022, т. 74, № 8
1026 О. П. БОЙКО, О. М. МАРТИНЮК, В. М. ПИВОВАРЧИК
Рис. 1. Граф-сніжинка, х - умова Діріхле, - умова
Неймана або узагальнена умова Неймана.
Рис. 1. Граф-снiжинка: \times — умова Дiрiхле, \bullet — умова
Неймана або узагальнена умова Неймана.
\^A =
\Biggl(
0 1
1 0
\Biggr)
.
Отже, многочлен, який фiгурує у теоремi 3, має вигляд PT, \^T (z) = 4z2 - 1. Вiн має коренi
\alpha 1 =
1
2
, \alpha 2 = - 1
2
, \^m = 2. Таким чином, ( \^m+ 1)l = 3l, що дорiвнює дiаметру дерева.
3. Розглянемо задачу Дiрiхле на графi-снiжинцi (див. рис. 1). Зазначимо, що скiнченнови-
мiрну спектральну задачу на такому графi було розглянуто у [15]. Внутрiшнiй пiдграф \^G — це
зiрковий граф. Його матриця \^D = \{ 3, 3, 4, 3\} , а його матриця сумiжностi
\^A =
\left(
0 0 0 1
0 0 0 1
0 0 0 1
1 1 1 0
\right) .
У цьому випадку многочлен, який фiгурує у теоремi 3, має вигляд PT, \^T = 108z4 - 33z2. Отже,
\alpha 1 =
\sqrt{}
11
36
, \alpha 2 = \alpha 3 = 0, \alpha 4 = -
\sqrt{}
11
36
i \^m = 3, ( \^m + 1)l = 4l. Таким чином, дiаметр дерева
дорiвнює ( \^m+ 1)l.
4. Розглянемо задачу Неймана на рiвнобiчному Н-графi (див. рис. 2). Дiаметр графа дорiв-
нює 3l. У цьому випадку D = \mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}\{ 1, 1, 1, 1, 3, 3\} i
A =
\left(
0 0 0 0 1 0
0 0 0 0 1 0
0 0 0 0 0 1
0 0 0 0 0 1
1 1 0 0 0 1
0 0 1 1 1 0
\right)
.
ISSN 1027-3190. Укр. мат. журн., 2022, т. 74, № 8
ВЕРХНЯ МЕЖА ДЛЯ ДIАМЕТРА ДЕРЕВА У КВАНТОВIЙ ТЕОРIЇ ГРАФIВ 1027
Рис 2. Н граф з умовами Неймана у висячих вершинах і
узагальненими умовами Неймана у внутрішних вершинах.
Рис. 2. Н-граф з умовами Неймана у висячих вершинах
i узагальненими умовами Неймана у внутрiшнiх
вершинах.
Рис.3. Декорований Н - граф.Рис. 3. Декорований Н-граф.
Таким чином, \alpha 1 = 1, \alpha 2 =
2
3
, \alpha 3 = \alpha 4 = 0, \alpha 5 = - 2
3
, \alpha 6 = - 1 i m = 3 i, отже, дiаметр
графа менший, нiж (m+ 1)l.
5. Розглянемо задачу Дiрiхле на графi, зображеному на рис. 3. У цьому випадку \^D =
= \mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}\{ 3, 3, 3, 4, 3, 3\} i
\^A =
\left(
0 0 0 0 0 1
0 0 0 0 1 0
0 0 0 0 1 0
0 0 0 0 0 1
0 1 1 0 0 1
1 0 0 1 1 0
\right)
,
а многочлен PT, \^T = 972z6 - 513z4 + 42z2. Вiн має коренi \alpha 1 \approx - 0,814, \alpha 2 \approx - 0,577,
\alpha 3 = \alpha 4 = 0, \alpha 5 \approx 0,577, \alpha 6 \approx 0,814 та m = 5 i, отже, дiаметр графа 5l менший, нiж
( \^m+ 1)l = 6l.
ISSN 1027-3190. Укр. мат. журн., 2022, т. 74, № 8
1028 О. П. БОЙКО, О. М. МАРТИНЮК, В. М. ПИВОВАРЧИК
Лiтература
1. G. Berkolaiko, P. Kuchment, Introduction to quantum graphs, Amer. Math. Soc., Providence, R.I. (2013).
2. F. Barioli, S. Fallat, On two conjectures regarding an inverse eigenvalue problem for acyclic symmetric matrices,
Electron. J. Linear Algebra, 11, 41 – 50 (2004).
3. A. Leal Duarte, C. R. Johnson, On the minimum number of distinct eigenvalues for a symmetric matrix whose graph
is a given tree, Math. Inequal. Appl., 5, № 2, 175 – 180 (2002).
4. В. М. Пивоварчик, Про мiнiмальну кiлькiсть рiзних власних значень в задачi на деревi зi стiльтьєсiвських
струн, Укр. мат. журн., 72, № 1, 135 – 141 (2020).
5. Fan R. K. Chung, Spectral graph theory, Amer. Math. Soc., Providence, R.I. (1997).
6. C. Cattaneo, The spectrum of the continuous Laplacian on a graph, Monatsh. Math., 124, № 3, 215 – 235 (1997).
7. P. Exner, A duality between Schrödinger operators on graphs and certain Jacobi matrices, Ann. Inst. H. Poincaré A,
66, 359 – 371 (1997).
8. J. Friedman, J.-P. Tillich, Wave equations for graphs and the edge-based Laplacian, Pacific J. Math., 216, № 2,
229 – 266 (2004).
9. R. Carlson, V. Pivovarchik, Spectral asymptotics for quantum graphs with equal edge lengths, J. Phys. A, 41,
Article 145202 (2008).
10. A. Chernyshenko, V. Pivovarchik, Recovering the shape of a quantum graph, Int. Equat. Oper. Theory, 92, Article 23
(2020).
11. A. Chernyshenko, V. Pivovarchik, Cospectral graphs (2022); arXiv:2112.14235 [math-ph] 23 Mar 22.
12. M. Möller, V. Pivovarchik, Direct and inverse finite-dimensional spectral problems on graphs, Operator Theory: Adv.
and Appl., 283, Birkhäuser/Springer (2020); https://www.springer.com/gp/book/9783030604837.
13. Ю. В. Покорный, О. М. Пенкин, В. Л. Прядиев, А. В. Боровских, К. П. Лазарев, С. А. Шабров, Дифференци-
альные уравнения на геометрических графах, Физматлит, Москва (2005).
14. M.-E. Pistol, Generating isospectral but not isomorphic quantum graphs; arXiv: 2104.12885 [math. SP] 19 Sep 21.
15. V. Pivovarchik, On multiplicities of eigenvalues of a boundary value problem on a snowflake graph, Linear Algebra,
Appl., 571, 78 – 91 (2019).
Одержано 23.02.22
ISSN 1027-3190. Укр. мат. журн., 2022, т. 74, № 8
|
| id | umjimathkievua-article-7176 |
| institution | Ukrains’kyi Matematychnyi Zhurnal |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2026-03-24T03:31:51Z |
| publishDate | 2022 |
| publisher | Institute of Mathematics, NAS of Ukraine |
| record_format | ojs |
| resource_txt_mv | umjimathkievua/c2/14eb770382da9e2a0d35c56e559bf0c2.pdf |
| spelling | umjimathkievua-article-71762022-10-24T09:23:21Z Upper bound for the diameter of a tree in the quantum graph theory О диаметре дерева в теории квантовых графов Верхня межа для діаметра дерева у квантовій теорії графів Boyko, O. P. Martynyuk, O. M. Pivovarchik, V. M. Бойко, Ольга Мартынюк, Ольга Бойко, О. П. Мартинюк, О. М. Пивоварчик, В. М. спектральна задача, власне значення, крайова умова Ноймана, умова Кірхгофа, спектр, дерево мана, spectral problem, eigenvalue, Neumann boundary condition, Kirchhoff's condition, spectrum, tree UDC 519.177We study two Sturm – Liouville spectral problems on an equilateral tree with continuity and Kirchhoff conditions at internal vertices and Neumann conditions at pendant vertices (first problem) and with Dirichlet conditions at pendant vertices (second problem). The spectrum of each of these problems consists of infinitely many normal (isolated Fredholm) eigenvalues. It is shown that, knowing the asymptotics of the eigenvalues, it is possible to estimate the diameter of a tree from above for each of these problems. Рассматриваются спектральные задачи, породженые уравнением Штурма-Лиувилля на равностороннем дереве с краевыми условиями Неймана на висячих вершинах и условиями непрерывности и Кирхгоффа во внутренних вершинах. Показано, что, используя асимптотики собственных значений, можно получить оценку сверху диаметра&nbsp; дерева. УДК 519.177 Розглянуто двi спектральнi задачi Штурма – Лiувiлля на рiвносторонньому деревi з умовами неперервностi i Кiрхгофа у внутрiшнiх вершинах та умовами Неймана у висячих вершинах i з умовами Дiрiхле у висячих вершинах вiдповiдно. Спектр кожної з цих задач складається з нескiнченної кiлькостi нормальних (iзольованих фредгольмових) власних значень. Показано, що знаючи асимптотики власних значень, можна оцiнити зверху дiаметр дерева для кожної з цих задач. Institute of Mathematics, NAS of Ukraine 2022-10-04 Article Article application/pdf https://umj.imath.kiev.ua/index.php/umj/article/view/7176 10.37863/umzh.v74i8.7176 Ukrains’kyi Matematychnyi Zhurnal; Vol. 74 No. 8 (2022); 1020 - 1028 Український математичний журнал; Том 74 № 8 (2022); 1020 - 1028 1027-3190 uk https://umj.imath.kiev.ua/index.php/umj/article/view/7176/9284 Copyright (c) 2022 Вячеслав Миколайович Пивоварчик, Ольга Бойко, Oльга Мартинюк |
| spellingShingle | Boyko, O. P. Martynyuk, O. M. Pivovarchik, V. M. Бойко, Ольга Мартынюк, Ольга Бойко, О. П. Мартинюк, О. М. Пивоварчик, В. М. Upper bound for the diameter of a tree in the quantum graph theory |
| title | Upper bound for the diameter of a tree in the quantum graph theory |
| title_alt | О диаметре дерева в теории квантовых графов Верхня межа для діаметра дерева у квантовій теорії графів |
| title_full | Upper bound for the diameter of a tree in the quantum graph theory |
| title_fullStr | Upper bound for the diameter of a tree in the quantum graph theory |
| title_full_unstemmed | Upper bound for the diameter of a tree in the quantum graph theory |
| title_short | Upper bound for the diameter of a tree in the quantum graph theory |
| title_sort | upper bound for the diameter of a tree in the quantum graph theory |
| topic_facet | спектральна задача власне значення крайова умова Ноймана умова Кірхгофа спектр дерево мана, spectral problem eigenvalue Neumann boundary condition Kirchhoff's condition spectrum tree |
| url | https://umj.imath.kiev.ua/index.php/umj/article/view/7176 |
| work_keys_str_mv | AT boykoop upperboundforthediameterofatreeinthequantumgraphtheory AT martynyukom upperboundforthediameterofatreeinthequantumgraphtheory AT pivovarchikvm upperboundforthediameterofatreeinthequantumgraphtheory AT bojkoolʹga upperboundforthediameterofatreeinthequantumgraphtheory AT martynûkolʹga upperboundforthediameterofatreeinthequantumgraphtheory AT bojkoop upperboundforthediameterofatreeinthequantumgraphtheory AT martinûkom upperboundforthediameterofatreeinthequantumgraphtheory AT pivovarčikvm upperboundforthediameterofatreeinthequantumgraphtheory AT boykoop odiametrederevavteoriikvantovyhgrafov AT martynyukom odiametrederevavteoriikvantovyhgrafov AT pivovarchikvm odiametrederevavteoriikvantovyhgrafov AT bojkoolʹga odiametrederevavteoriikvantovyhgrafov AT martynûkolʹga odiametrederevavteoriikvantovyhgrafov AT bojkoop odiametrederevavteoriikvantovyhgrafov AT martinûkom odiametrederevavteoriikvantovyhgrafov AT pivovarčikvm odiametrederevavteoriikvantovyhgrafov AT boykoop verhnâmežadlâdíametraderevaukvantovíjteoríígrafív AT martynyukom verhnâmežadlâdíametraderevaukvantovíjteoríígrafív AT pivovarchikvm verhnâmežadlâdíametraderevaukvantovíjteoríígrafív AT bojkoolʹga verhnâmežadlâdíametraderevaukvantovíjteoríígrafív AT martynûkolʹga verhnâmežadlâdíametraderevaukvantovíjteoríígrafív AT bojkoop verhnâmežadlâdíametraderevaukvantovíjteoríígrafív AT martinûkom verhnâmežadlâdíametraderevaukvantovíjteoríígrafív AT pivovarčikvm verhnâmežadlâdíametraderevaukvantovíjteoríígrafív |