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

де позначає множину вершин графа , а позначає довжину найкоротшого шляху між вершинами та .

Триаметр розширює поняття діаметра графа, що фіксує найдовший шлях між будь-якими двома вершинами у графі. Триаметральною трійкою називають множину із трьох вершин, на яких досягається .

Історія

Графовий параметр триаметр пов'язаний із задачею про призначення — проблемою розподілу частот між передавачами в деякий оптимальний спосіб уникаючи інтерференцій хвиль. та ін. ввели поняття зв'язного простого графа (2005). Потім (2012, 2015) точні нижні оцінки на зв'язного графа були отримані у термінах нововизначеного параметра названого триаметром графа. Крім цього, поняття триаметра також має застосування у метричних політопах.

У 2014 році Хеннінг та Йео довели гіпотезу про нижню оцінку сильного числа домінувань зв'язного графа у термінах його триаметра. Саха та Паніграхі називали цей параметр -значенням графа у своїй роботі.

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

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

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

Вперше метричні властивості триаметра були дослідженні А. Дасом. Для триаметра будь-якого зв'язного графа виконуються точні оцінки у термінах його діаметра та радіуса:

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

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

Якщо є деревом із більш ніж листочками, то навіть строгіша оцінка виконується. Для будь-якого зв'язного графа із вершинами виконується нижня оцінка . Більш того, рівність досягається тоді й тільки тоді, коли є деревом із або листочками.

Загальна точна нижня оцінка для всіх пар також відома. Нехай є деревом із вершинами та листочками, тоді виконується така нерівність:

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

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

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

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

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

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

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

Також, (ТД) не виконується для гіперкубів і, як наслідок, для .

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

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

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

Див. також

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

Джерела

Посилання

, "Graph Triameter", MathWorld Written on the Wall II (Conjectures of Graffiti.pc)