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

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

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)}$.

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

Metric properties

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}}}$$

Bounds for trees

A tree T with tr(T) = 20 representing tight lower triameter bound for n=17, l=5.

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:

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

Diameter–triameter interplay

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

The graph G has tr(G) = d(u,v,w) = 12 and diam(G) = d(x,y) = 5. The triametral triple u, v, w does not contain a diametral pair, and the diametral pair x, y cannot be extended to a triametral triple.

(TD) Any triametral triple in a graph contains a diametral pair.

(DT) Any diametral pair in a graph can be extended to a triametral triple.

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}}$.

A pair of distance hereditary graphs being a counterexample to diameter–triameter interplay. The triametral triple u, v, w of the graph on the left does not contain a peripheral vertex, while the peripheral vertex x of the graph on the right cannot be extended to a triametral triple. Both graphs are distance hereditary, the graph on the left is also a median graph.

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

Open problems

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]?

See also

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