Триаметр (теорія графів)

У теорії графів, триаметр — це метрична властивість (інваріант) графа, що узагальнює поняття діаметра графа. Триаметр визначається як максимум сум попарних відстаней між трьома вершинами у зв'язному графі ${\textstyle G}$ та позначається як

$${\displaystyle \mathop {\mathrm {tr} } (G)=\max\{d(u,v)+d(v,w)+d(u,w)\mid u,v,w\in V\},}$$

де ${\textstyle V}$ позначає множину вершин графа ${\textstyle G}$, а ${\textstyle d(u,v)}$ позначає довжину найкоротшого шляху між вершинами ${\textstyle u}$ та ${\textstyle v}$.

Триаметр розширює поняття діаметра графа, що фіксує найдовший шлях між будь-якими двома вершинами у графі. Триаметральною трійкою називають множину із трьох вершин, на яких досягається ${\textstyle \mathop {\mathrm {tr} } (G)}$.

Історія

Графовий параметр триаметр пов'язаний із задачею про призначення — проблемою розподілу частот між передавачами в деякий оптимальний спосіб уникаючи інтерференцій хвиль. Чартренд^[en] та ін. ^[1] ввели поняття радіо ${\textstyle k}$-розфарбування^[en] зв'язного простого графа (2005). Потім (2012, 2015) точні нижні оцінки на радіо ${\textstyle k}$-хроматичне число^[en] зв'язного графа були отримані у термінах нововизначеного параметра названого триаметром графа.^{[2] [3] [4]} Крім цього, поняття триаметра також має застосування у метричних політопах.^[5]

У 2014 році Хеннінг та Йео довели Граффіті^[en] гіпотезу про нижню оцінку сильного числа домінувань зв'язного графа у термінах його триаметра.^[6] Саха та Паніграхі називали цей параметр ${\textstyle M}$-значенням графа у своїй роботі.^[4]

Поняття триаметра було вперше формально введено та досліджено у 2021 році А. Дасом. Він дослідив його зв'язки з іншими графовими параметрами такими як діаметр, радіус, обхват та число домінувань.^[7] Спираючись на цей фундамент, А. Гак, С. Козеренко та Б. Олійник продовжили дослідження у 2022 році, дослідили взаємозв'язок між триаметром та діаметром для деяких родин графів і встановили точну нижню межу для триаметра дерев у термінах кількостей їх вершин та листків.^[8]

Нещодавно К. Джея Дейзі, С. Ніхіша та П. Джеянті пов'язали триаметр з теорією кілець, у своєму дослідженні триаметра графа дільника нуля^[en] комутативного кільця з тотожністю.^[9]

Метричні властивості

Вперше метричні властивості триаметра були дослідженні А. Дасом.^[7] Для триаметра будь-якого зв'язного графа ${\textstyle G}$ виконуються точні оцінки у термінах його діаметра та радіуса: $${\displaystyle {\begin{aligned}2\mathop {\mathrm {diam} } (G)\leq &\mathop {\mathrm {tr} } (G)\leq 3\mathop {\mathrm {diam} } (G),\\2\mathop {\mathrm {rad} } (G)\leq &\mathop {\mathrm {tr} } (G)\leq 6\mathop {\mathrm {rad} } (G).\end{aligned}}}$$

Оцінки для дерев

Дерево T, що має tr(T) = 20 та ілюструє точну нижню оцінку триаметра дерев для n=17, l=5.

Для дерев trees можна дати строгіші оцінки:^[7]

$${\displaystyle 4\mathop {\mathrm {rad} } (G)-2\leq \mathop {\mathrm {tr} } (G)\leq 6\mathop {\mathrm {rad} } (G),}$$ Якщо ${\textstyle G}$ є деревом із більш ніж ${\textstyle 2}$ листочками, то навіть строгіша оцінка ${\textstyle \mathop {\mathrm {tr} } (G)\geq 4\mathop {\mathrm {rad} } (G)}$ виконується. Для будь-якого зв'язного графа ${\textstyle G}$ із ${\textstyle n\geq 3}$ вершинами виконується нижня оцінка ${\textstyle \mathop {\mathrm {tr} } (G)\leq 2n-2}$. Більш того, рівність досягається тоді й тільки тоді, коли ${\textstyle G}$ є деревом із ${\textstyle 2}$ або ${\textstyle 3}$ листочками.

Загальна точна нижня оцінка для всіх пар ${\textstyle (n,l)}$ також відома.^[8] Нехай ${\textstyle T}$ є деревом із ${\textstyle n\geq 4}$ вершинами та ${\textstyle l\geq 3}$ листочками, тоді виконується така нерівність:

$${\displaystyle \mathop {\mathrm {tr} } (T)\geq 6\left\lfloor {\frac {n-1}{l}}+2\min\{(n-1){\bmod {l}},3\}\right\rfloor .}$$

Взаємозв'язок діаметра й триаметра

Ключове питання полягає у тому, який взаємозв'язок зберігається між діаметром та триаметром графа для різних родин графів:^{[7] [8]}

Граф G, що має tr(G) = d(u,v,w) = 12 та diam(G) = d(x,y) = 5. Триаметральна трійка u, v, w не містить діаметральної пари, водночас діаметральна пара x, y не може бути розширена до триаметральної трійки.

(ТД) Кожна триаметральна трійка вершин містить діаметральну пару.

(ДТ) Кожна діаметральна пара вершин може бути розширена до триаметральної трійки.

Насправді обидві властивості (ТД) та (ДТ) виконуються для дерев та графів блоків. Для симетричного графа кожна їх пара вершин (навіть недіаметральна) може бути розширена до триаметральної трійки, з чого випливає (ДТ); хоча, перша властивість (ТД) не виконується для них.

Також є послаблені версії цих властивостей:^[8]

(ТД${\textstyle '}$) Кожна триаметральна трійка містить периферійну вершину.

(Д${\textstyle '}$Т) Кожна периферійна вершина може бути розширена до триаметральної трійки.

Ані модулярні^[en] ані дистанційно-успадковувані графи не задовольняють жодній із цих властивостей, навіть слабшим версіям. Для контрприкладу (Д${\textstyle '}$Т) див. граф зліва на малюнку, насправді він є одночасно модулярним^[en] та дистанційно-успадковуваним. Для (ТД${\textstyle '}$) контрприкладом дистанційно-успадковуваних графів є граф справа на малюнку, а для модулярних^[en] це повний двочастковий граф ${\textstyle K_{2,3}}$.

Пара дистанційно-успадковуваних графів, що є контрприкладами взаємозв'язку діаметра й триаметра. Триаметральна трійка u, v, w графа зліва не містить периферійну вершину, в той час як периферійна вершина x графа справа не може бути розширена до триаметральної трійки. Обидва графи є дистанційно-успадковуваними, граф зліва також є медіанним графом^[en].

Також, (ТД) не виконується для гіперкубів і, як наслідок, для медіанних графів^[en].

Відкриті проблеми

Кілька відкритих проблем щодо триаметра:

• Чи виконується (ДТ) для медіанних графів^[en]? Це цікаве питання, оскільки медіанні графи^[en] є узагальненням дерев та гіперкубів, для яких ця властивість виконується. Мета-Гіпотеза, поставлена Г. Мюлдером,^[10] говорить, що будь-яка (змістовна) властивість, яка виконується водночас для дерева та для гіперкубів також виконується для всіх медіанних графів^[en]. Варто зазначити, що жодна із властивостей (навіть слабших версій) взаємозв'язку діаметра й триаметра не виконується для модулярних графів^[en], які є узагальненням медіанних графів^[en].

Додатково можна дослідити, чи виконується (Д${\textstyle '}$Т) або (ТД${\textstyle '}$) для медіанних графів^[en].

• Чи можна дати кращу нижню оцінку триаметра у термінах найбільшого ${\textstyle \Delta (G)}$ та найменшого ${\textstyle \sigma (G)}$ степеня вершини графа ${\textstyle G}$?^[7]

Див. також

• Діаметр (теорія графів)
• Відстань (теорія графів)
• Дерево (теорія графів)