MAKASSAR, Indonesia June 02 2026/graphtheory/ Imagine a delivery network with many roads, intersections, and shortcuts. To manage it efficiently, each road should be distinguishable from the others. In mathematics, this idea can be studied through graph theory, where intersections are represented as vertices and roads as edges. A recent study explains how a carefully selected group of vertices can be used to uniquely identify every edge in a complex network.
The research focuses on a concept called the edge metric dimension. In simple terms, researchers choose several reference vertices in a graph. They then measure the shortest distance from each edge to those reference points. Every edge receives a “distance signature,” much like a digital fingerprint. If no two edges share the same signature, the chosen vertices successfully distinguish all edges. The smallest number of reference vertices needed is called the edge metric dimension.
The study examines a special structure known as the comb product of a cycle and a graph with a dominant vertex. A cycle can be imagined as a circular route. At every point on this route, another smaller graph is attached, creating a structure that resembles a comb. In each attached graph, one dominant vertex is directly connected to all other vertices. This central position makes the dominant vertex similar to a hub in a transport, communication, or social network.
The authors introduced the idea of equivalent edges to help explain why some connections are difficult to distinguish. Equivalent edges share a common endpoint and appear to have the same distance from many other vertices. Because of this similarity, additional reference vertices are needed to tell them apart.
The main result provides a clear and general formula. For the comb product of a cycle graph (C_n) and a graph (D) with a dominant vertex, the edge metric dimension.
This means that the required number of reference vertices depends on the number of vertices in the cycle and the size of the attached graph. The result generalizes earlier findings that applied only to complete graphs. It also covers special structures such as star, fan, and wheel graphs.
Although the research is theoretical, its central idea is highly relevant to real networks. Distinguishing connections efficiently is important in navigation, sensor placement, communication monitoring, network security, and infrastructure design. Exact formulas help researchers understand how much information is needed to identify every connection without testing countless possibilities.
This study directly supports Sustainable Development Goal 4: Quality Education. It expands mathematical knowledge, provides new learning material for graph theory and discrete mathematics, and helps students understand how abstract reasoning can contribute to real-world problem solving. By translating advanced mathematics into accessible language, the study also encourages wider public interest in science.
Ultimately, the research shows that even complicated networks can be understood through simple ideas: distance, identity, and carefully chosen reference points.
Reference:
DOI: http://dx.doi.org/10.5614/ejgta.2026.14.1.2
Contact:
Prof. Nurdin
+62 813-9519-0801
nurdin1701@unhas.ac.id
