EN / KO

Activities

Seminars

Home Activities Seminars

FIELD
AI and Natural Sciences
DATE
Sep 17 (Thu), 2026
TIME
14:00 ~ 15:20
PLACE
7323
SPEAKER
Ahn, Hee-Kap
HOST
Chung, Jaehoon
INSTITUTE
POSTECH
TITLE
Diameter and Length of Metric Graphs
ABSTRACT
A metric graph is a metric space obtained from a finite collection of intervals whose endpoints are identified in groups. It can also be seen as a finite, edge-weighted graph where the continuum of points along the interior of each edge is taken into consideration, and each edge is locally isometric to an interval whose length is the edge-weight. The diameter of a metric graph $G$ is the maximum distance between all pairs of points of $G$. We show that the total length of a metric graph $G$ with $\leaves(G)$ leaves, cyclomatic number $\cyc(G)$, and diameter $\diam(G)$ is at most $\big(\cyc(G) + \max\big\{1, \leaves(G)/2 \big\}\big) \cdot \diam(G)$. Furthermore, we show that this bound is tight, and we characterize the metric graphs where equality holds. As an application, we provide tight bounds in certain cases for the diameter of metric graphs obtained from a cycle or a star by the identification of a fixed number of points (pairwise or in groups).
FILE