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

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

$\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}$ виконуються точні оцінки у термінах його діаметра та радіуса: ${\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}}$

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

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

$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}$ листочками, тоді виконується така нерівність:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Див. також

Джерела

↑ Chartrand, Gary; Erwin, David; Zhang, Ping (2005). A graph labeling problem suggested by FM channel restrictions. Bulletin of the Institute of Combinatorics and its Applications. 43: 43—57. ISSN 2689-0674.
↑ Rao Kola, Srinivasa; Panigrahi, Pratima (2015). A lower bound for radio k-chromatic number of an arbitrary graph. Contributions to Discrete Mathematics. 10 (2): 45—57. ISSN 1715-0868.
↑ Saha, Laxman; Panigrahi, Pratima (2012). Antipodal number of some powers of cycles. Discrete Mathematics. 312 (9): 1550—1557. doi:10.1016/j.disc.2011.10.032. ISSN 1872-681X.
↑ ^а ^б Saha, Laxman; Panigrahi, Pratima (2015). A lower bound for radio k-chromatic number. Discrete Applied Mathematics. The Journal of Combinatorial Algorithms, Informatics and Computational Sciences. 192: 87—100. doi:10.1016/j.dam.2014.05.004. ISSN 1872-6771.
↑ Laurent, Monique (1996). Graphic vertices of the metric polytope. Discrete Mathematics. Т. 151. с. 131—153.
↑ Henning, Michael A.; Yeo, Anders (2014). A new lower bound for the total domination number in graphs proving a Graffiti.pc Conjecture. Discrete Applied Mathematics. 173: 45—52. doi:10.1016/j.dam.2014.03.013. ISSN 0166-218X.
↑ ^а ^б ^в ^г ^д Das, Angsuman (2021). Triameter of graphs. Discussiones Mathematicae. Graph Theory. 41 (2): 601—616. doi:10.7151/dmgt.2212. ISSN 2083-5892.
↑ ^а ^б ^в ^г Hak, Artem; Kozerenko, Sergiy; Oliynyk, Bogdana (2022). A note on the triameter of graphs. Discrete Applied Mathematics. The Journal of Combinatorial Algorithms, Informatics and Computational Sciences. 309: 278—284. doi:10.1016/j.dam.2021.12.011. ISSN 1872-6771.
↑ Jeya Daisy, K.; Nihisha, S.; Jeyanthi, P. (2025). Triameter of the Zero Divisor Graph of a Commutative Ring with Identity. Discrete Mathematics, Algorithms and Applications. doi:10.1142/S1793830925500624.
↑ Mulder, Henry Martyn (2016). What do trees and hypercubes have in common?. Graph theory—favorite conjectures and open problems. 1. Probl. Books in Math. Springer, [Cham]. с. 149—170. ISBN 978-3-319-31940-7.