In graph theory, the triameter is a metric invariant that generalizes the concept of a graph's diameter. It is defined as the maximum sum of pairwise distances between any three vertices in a connected graph G {\textstyle G} and is denoted by
where V {\textstyle V} is the vertex set of G {\textstyle G} and d ( u , v ) {\textstyle d(u,v)} is the length of the shortest path between vertices u {\textstyle u} and v {\textstyle v} . It extends the idea of the diameter, which captures the longest path between any two of its vertices. A triametral triple is a set of three vertices achieving t r ( G ) {\textstyle \mathop {\mathrm {tr} } (G)} .
History The parameter of triameter is related to the channel assignment problem—the problem of assigning frequencies to the transmitters in some optimal manner and with no interferences. Chartrand et al.. introduced the concept of radio k {\textstyle k} -coloring of a connected simple graph in 2005. Then (2012, 2015) sharp lower bounds on radio k {\textstyle k} -chromatic number of connected graphs were provided in terms of a newly defined parameter called triameter of a graph. Apart from this, the concept of triameter also finds application in metric polytopes. In 2014, Henning and Yeo proved a Graffiti conjecture on lower bound of total domination number of a connected graph in terms of its triameter. Saha and Panigrahi denoted this parameter as M {\textstyle M} -value of a graph in their paper. The concept of triameter was first formally introduced in 2021 and studied by A. Das. He investigated its connections to other graph parameters such as diameter, radius, girth, and domination numbers. Building on this foundation, A. Hak, S. Kozerenko and B. Oliynyk extended the study in 2022 exploring an interplay between triameter and diameter for some graph families and establishing a tight lower bound for triameter of trees in terms of their order and number of leaves. Recently, K. Jeya Daisy, S. Nihisha, and P. Jeyanthi, linked triameter to the ring theory, they studied triameter of the zero-divisor graph of a commutative ring with identity.
Metric properties The metric properties of triameter were first studied by A. Das. The triameter of any connected graph G {\textstyle G} is tightly bounded by its diameter and radius in the following way: 2 d i a m ( G ) ≤ t r ( G ) ≤ 3 d i a m ( G ) , 2 r a d ( G ) ≤ t r ( G ) ≤ 6 r a d ( 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}}}
Bounds for trees
For the trees tighter bounds hold:
… excerpt ends here. Continue reading the full article.
