Triameter (graph theory)

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 ${\textstyle G}$ and is denoted by

where ${\textstyle V}$ is the vertex set of ${\textstyle G}$ and ${\textstyle d(u,v)}$ is the length of the shortest path between vertices ${\textstyle u}$ and ${\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 ${\textstyle \mathop {\mathrm {tr} } (G)}$.

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..^[1] introduced the concept of radio ${\textstyle k}$-coloring of a connected simple graph in 2005. Then (2012, 2015) sharp lower bounds on radio ${\textstyle k}$-chromatic number of connected graphs were provided in terms of a newly defined parameter called triameter of a graph ^{[2] [3] [4]}. Apart from this, the concept of triameter also finds application in metric polytopes ^[5].

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 ^[6]. Saha and Panigrahi denoted this parameter as ${\textstyle M}$-value of a graph in their paper ^[4].

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 ^[7]. 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 ^[8].

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 ^[9]

The metric properties of triameter were first studied by A. Das ^[7]. The triameter of any connected graph ${\textstyle G}$ is tightly bounded by its diameter and radius in the following way: $${\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}}}$$

For the trees tighter bounds hold:^[7]

$${\displaystyle 4\mathop {\mathrm {rad} } (G)-2\leq \mathop {\mathrm {tr} } (G)\leq 6\mathop {\mathrm {rad} } (G),}$$ If ${\textstyle G}$ is a tree with more than ${\textstyle 2}$ leaves, then the stronger lower bound ${\textstyle \mathop {\mathrm {tr} } (G)\geq 4\mathop {\mathrm {rad} } (G)}$ holds. For any connected graph ${\textstyle G}$ with ${\textstyle n\geq 3}$ vertices the lower bound ${\textstyle \mathop {\mathrm {tr} } (G)\leq 2n-2}$ takes place. Moreover, the equality holds if and only if ${\textstyle G}$ is a tree with ${\textstyle 2}$ or ${\textstyle 3}$ leaves.

The general tight lower bound for any given pair ${\textstyle (n,l)}$ is known ^[8]. Let ${\textstyle T}$ be a tree with ${\textstyle n\geq 4}$ vertices and ${\textstyle l\geq 3}$ leaves, then the following holds:

The key question is whether some relationships between diameter and triameter hold for various graph families:^{[7] [8]}

In fact, both (TD) and (DT) hold for trees and block graphs. Every pair of vertices (even not diametral) in a symmetric graph can be extended to a triametral triple, which implies (DT); however, the first property (TD) does not hold for them.

There are weaker versions of these properties:^[8]

(TD${\textstyle '}$) Any triametral triple contains a peripheral vertex.

(D${\textstyle '}$T) Any peripheral vertex can be extended to a triametral triple.

Neither modular graphs nor distance hereditary graphs satisfy any of these properties, even weaker versions. For (D${\textstyle '}$T) counterexamle see the graph on the left in the figure, in fact it is both modular and ditance hereditary. For (TD${\textstyle '}$) the ditance hereditary counterexample is graph on the right in the figure, and for the modular it is a complete bipartite graph ${\textstyle K_{2,3}}$.

Also, (TD) does not hold for the hypercubes and, consequently, median graphs.

Several open problems regarding the triameter:

• Does (DT) hold for the median graphs? This is an interesting question because median graphs generalize trees and hypercubes, for which (DT) holds. A Meta-Conjecture, stated by H. Mulder ^[10], suggests that any (sensible) property shared by trees and hypercubes is also shared by all median graphs. Notably, none of the diamter–triamter properties (even weaker onces) holds for the modular graphs, which generalize median graphs.
  

Additionally, one could investigate if (D${\textstyle '}$T) or (TD${\textstyle '}$) hold for the median graphs.

• Can better lower triameter bounds be established in terms of the maximum ${\textstyle \Delta (G)}$ and minimum degree ${\textstyle \sigma (G)}$ ^[7]?

• Diameter (graph theory)
• Distance (graph theory)
• Tree (graph theory)
• Median graph

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