graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, 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 Distance is a numerical or occasionally qualitative measurement of how far apart objects, points, people, or ideas are. In physics or everyday usage, distance may refer to a physical length or an estimation based on other criteria (e.g. "two co ...

between any three vertices in a

connected graph In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) that need to be removed to separate the remaining nodes into two or more isolated subgrap ...

G

and is denoted by

\mathop(G) = \max\,

where

V

is the vertex set of

G

and

d(u,v)

is the length of the shortest

path A path is a route for physical travel – see Trail. Path or PATH may also refer to: Physical paths of different types * Bicycle path * Bridle path, used by people on horseback * Course (navigation), the intended path of a vehicle * Desir ...

between vertices

u

and

v

. It extends the idea of the

diameter In geometry, a diameter of a circle is any straight line segment that passes through the centre of the circle and whose endpoints lie on the circle. It can also be defined as the longest Chord (geometry), chord of the circle. Both definitions a ...

, which captures the longest

between any two of its vertices. A triametral triple is a

set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...

of three vertices achieving

\mathop(G)

History

The parameter of triameter is related to the channel

assignment problem The assignment problem is a fundamental combinatorial optimization problem. In its most general form, the problem is as follows: :The problem instance has a number of ''agents'' and a number of ''tasks''. Any agent can be assigned to perform any t ...

—the problem of assigning

frequencies Frequency is the number of occurrences of a repeating event per unit of time. Frequency is an important parameter used in science and engineering to specify the rate of oscillatory and vibratory phenomena, such as mechanical vibrations, audio ...

to the

transmitters In electronics and telecommunications, a radio transmitter or just transmitter (often abbreviated as XMTR or TX in technical documents) is an electronic device which produces radio waves with an antenna with the purpose of signal transmissi ...

in some optimal manner and with no interferences. Chartrand et al.. introduced the concept of radio

k

-coloring of a

connected Connected may refer to: Film and television * ''Connected'' (2008 film), a Hong Kong remake of the American movie ''Cellular'' * '' Connected: An Autoblogography About Love, Death & Technology'', a 2011 documentary film * ''Connected'' (2015 TV ...

br>simple graph
in 2005. Then (2012, 2015) sharp lower bounds on radio

k

-chromatic number of connected graphs were provided in terms of a newly defined parameter called triameter of a

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discret ...

. Apart from this, the concept of triameter also finds application in metric

polytopes In elementary geometry, a polytope is a geometric object with Flat (geometry), flat sides (''Face (geometry), faces''). Polytopes are the generalization of three-dimensional polyhedron, polyhedra to any number of dimensions. Polytopes may exist ...

. In 2014, Henning and Yeo proved a

Graffiti Graffiti (singular ''graffiti'', or ''graffito'' only in graffiti archeology) is writing or drawings made on a wall or other surface, usually without permission and within public view. Graffiti ranges from simple written "monikers" to elabor ...

conjecture on lower bound of total domination number of a

in terms of its triameter . Saha and Panigrahi denoted this parameter as

M

-value of a graph in their paper . The concept of triameter was first formally introduced in 2021 and studied b
A. Das
He investigated its connections to other graph parameters such as

radius

girth Girth may refer to: Mathematics * Girth (functional analysis), the length of the shortest centrally symmetric simple closed curve on the unit sphere of a Banach space * Girth (geometry), the perimeter of a parallel projection of a shape * 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

for some

graph families Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discret ...

and establishing a tight lower bound for triameter of

trees In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, e.g., including only woody plants with secondary growth, only p ...

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 In mathematics, and more specifically in combinatorial commutative algebra, a zero-divisor graph is an undirected graph representing the zero divisors of a commutative ring. It has elements of the ring (mathematics), ring as its vertex (graph theo ...

of a

commutative ring In mathematics, a commutative ring is a Ring (mathematics), ring in which the multiplication operation is commutative. The study of commutative rings is called commutative algebra. Complementarily, noncommutative algebra is the study of ring prope ...

with

identity Identity may refer to: * Identity document * Identity (philosophy) * Identity (social science) * Identity (mathematics) Arts and entertainment Film and television * ''Identity'' (1987 film), an Iranian film * ''Identity'' (2003 film), an ...

Metric properties

The metric properties of triameter were first studied by A. Das . The triameter of any

graph

G

is tightly bounded by its

an
radius
in the following way:

\begin
2 \mathop(G) \leq &\mathop(G) \leq 3 \mathop(G),\\
2 \mathop(G) \leq &\mathop(G) \leq 6 \mathop(G).
\end

Bounds for trees

For the

tighter bounds hold:

4 \mathop(G) - 2 \leq \mathop(G) \leq 6 \mathop(G),

G

is a

tree In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, e.g., including only woody plants with secondary growth, only ...

with more than

2

leaves, then the stronger lower bound

\mathop(G) \geq 4\mathop(G)

holds. For any connected graph

G

with

n \geq 3

vertices the lower bound

\mathop(G) \leq 2n - 2

takes place. Moreover, the equality holds if and only if

G

is a

with

2

3

leaves. The general tight lower bound for any given pair

(n, l)

is known . Let

T

be a

with

n\geq 4

vertices and

l\geq 3

leaves, then the following holds:

\mathop(T)\geq 6 \left\lfloor+2\min\\right\rfloor.

Diameter–triameter interplay

The key question is whether some relationships between

and triameter hold for various

(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

and block graphs. Every pair of vertices (even not diametral) in a

symmetric graph In the mathematical field of graph theory, a graph is symmetric or arc-transitive if, given any two ordered pairs of adjacent vertices (u_1,v_1) and (u_2,v_2) of , there is an automorphism :f : V(G) \rightarrow V(G) such that :f(u_1) = u_2 a ...

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:

(TD $'$ ) Any triametral triple contains a

peripheral A peripheral device, or simply peripheral, is an auxiliary hardware device that a computer uses to transfer information externally. A peripheral is a hardware component that is accessible to and controlled by a computer but is not a core compo ...

vertex.

(D $'$ T) Any

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

'

T) counterexample see the graph on the left in the

figure Figure may refer to: General *A shape, drawing, depiction, or geometric configuration *Figure (wood), wood appearance *Figure (music), distinguished from musical motif * Noise figure, in telecommunication * Dance figure, an elementary dance patt ...

, in fact it is both modular and distance hereditary. For (TD

'

) the distance hereditary counterexample is the graph on the right in the

, and for the modular it is a

complete bipartite graph In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17. Graph theory ...

K_

A pair of distance-hereditary graphs being a counterexample to diameter--triameter interplay

Also, (TD) does not hold for the

hypercubes In geometry, a hypercube is an N-dimensional space, ''n''-dimensional analogue of a Square (geometry), square (two-dimensional, ) and a cube (Three-dimensional, ); the special case for Four-dimensional space, is known as a ''tesseract''. It is ...

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

and

, for which (DT) holds. A Meta-Conjecture, stated by H. Mulder , suggests that any (sensible)

property Property is a system of rights that gives people legal control of valuable things, and also refers to the valuable things themselves. Depending on the nature of the property, an owner of property may have the right to consume, alter, share, re ...

shared by

and

is also shared by all median graphs. Notably, none of the diameter–triameter properties (even weaker ones) holds for modular graphs, which generalize median graphs.
Additionally, one could investigate if (D

'

T) or (TD

'

) hold for median graphs. * Can better lower triameter bounds be established in terms of the maximum

\Delta(G)

and minimum degree

\sigma(G)

References

{{Reflist, refs={{Cite journal , issn = 2689-0674 , volume = 43 , pages = 43–57 , last1 = Chartrand , first1 = Gary , last2 = Erwin , first2 = David , last3 = Zhang , first3 = Ping , title = A graph labeling problem suggested by FM channel restrictions , journal = Bulletin of the Institute of Combinatorics and Its Applications , date = 2005 {{Cite journal , issn = 1715-0868 , volume = 10 , issue = 2 , pages = 45–57 , last1 = Rao Kola , first1 = Srinivasa , last2 = Panigrahi , first2 = Pratima , title = A lower bound for radio k-chromatic number of an arbitrary graph , journal = Contributions to Discrete Mathematics , date = 2015 {{Cite journal , doi = 10.1016/j.disc.2011.10.032 , issn = 1872-681X , volume = 312 , issue = 9 , pages = 1550–1557 , last1 = Saha , first1 = Laxman , last2 = Panigrahi , first2 = Pratima , title = Antipodal number of some powers of cycles , journal = Discrete Mathematics , date = 2012 {{Cite journal , doi = 10.1016/j.dam.2014.05.004 , issn = 1872-6771 , volume = 192 , pages = 87–100 , last1 = Saha , first1 = Laxman , last2 = Panigrahi , first2 = Pratima , title = A lower bound for radio k-chromatic number , journal = Discrete Applied Mathematics. The Journal of Combinatorial Algorithms, Informatics and Computational Sciences , date = 2015 {{Cite book , volume = 151 , pages = 131–153 , last = Laurent , first = Monique , title = Discrete Mathematics , chapter = Graphic vertices of the metric polytope , date = 1996 {{Cite journal , doi = 10.1016/j.dam.2014.03.013 , issn = 0166-218X , volume = 173 , pages = 45–52 , last1 = Henning , first1 = Michael A. , last2 = Yeo , first2 = Anders , title = A new lower bound for the total domination number in graphs proving a Graffiti.pc Conjecture , journal = Discrete Applied Mathematics , date = 2014, doi-access = free {{Cite journal , doi = 10.7151/dmgt.2212 , issn = 2083-5892 , volume = 41 , issue = 2 , pages = 601–616 , last = Das , first = Angsuman , title = Triameter of graphs , journal = Discussiones Mathematicae Graph Theory , date = 2021, arxiv = 1804.01088 {{Cite journal , doi = 10.1016/j.dam.2021.12.011 , issn = 1872-6771 , volume = 309 , pages = 278–284 , last1 = Hak , first1 = Artem , last2 = Kozerenko , first2 = Sergiy , last3 = Oliynyk , first3 = Bogdana , title = A note on the triameter of graphs , journal = Discrete Applied Mathematics. The Journal of Combinatorial Algorithms, Informatics and Computational Sciences , date = 2022, arxiv = 2103.10806 {{Cite book , publisher = Springer,

ham Ham is pork from a leg cut that has been preserved by wet or dry curing, with or without smoking."Bacon: Bacon and Ham Curing" in '' Chambers's Encyclopædia''. London: George Newnes, 1961, Vol. 2, p. 39. As a processed meat, the term '' ...

, isbn = 978-3-319-31940-7 , pages = 149–170 , last = Mulder , first = Henry Martyn , title = Graph theory—favorite conjectures and open problems. 1 , chapter = What do trees and hypercubes have in common? , series = Probl. Books in Math. , date = 2016 {{Cite journal , doi = 10.1142/S1793830925500624 , last1 = Jeya Daisy , first1 = K. , last2 = Nihisha, first2 = S. , last3 = Jeyanthi , first3 = P. , title = Triameter of the Zero Divisor Graph of a Commutative Ring with Identity , journal = Discrete Mathematics, Algorithms and Applications , date = 2025

External links

* Weisstein Eric W.
"Graph Triameter"

MathWorld ''MathWorld'' is an online mathematics reference work, created and largely written by Eric W. Weisstein. It is sponsored by and licensed to Wolfram Research, Inc. and was partially funded by the National Science Foundation's National Science ...

Written on the Wall II (Conjectures of Graffiti.pc)
Graph distance Graph invariants Computational problems in graph theory Graph families

History

Metric properties

Bounds for trees

Diameter–triameter interplay

Open problems

See also

References

External links