MAKASSAR, Indonesia Jan 2 2026/graphtheory/ Imagine drawing a road map on a sheet of paper. Intersections become points, roads become lines, and the spaces enclosed by those roads become regions. In graph theory, these are called vertices, edges, and faces. A study titled “H-Irregularity Strengths of Plane Graphs” asks a fascinating question: how can numbers be assigned to these elements so that repeated substructures can always be told apart?
The research focuses on plane graphs, meaning graphs drawn on a flat surface without edges crossing. The authors introduce two new mathematical measures: vertex–face H-irregularity strength and edge–face H-irregularity strength. Although the terminology sounds complex, the basic idea is simple.
Suppose a large graph contains several smaller patterns of the same type, called H-subgraphs. Researchers assign numbers either to the vertices and faces, or to the edges and faces. The numbers inside each H-subgraph are then added. A successful labeling gives every copy of H a different total weight. The “irregularity strength” is the smallest largest label needed to achieve that uniqueness.
This is similar to identifying identical-looking apartment blocks. Each block may have the same shape, but by combining numbers assigned to rooms, corridors, and shared spaces, every block receives a distinct total code. The challenge is to create these codes using the smallest possible range of numbers.
The study establishes general lower and upper bounds for both new parameters. It also proves exact values for two important graph families. The first is the ladder graph, which resembles two parallel paths connected by short rungs. Figures 1 and 2 on pages 4–5 show how labels 1 and 2 can distinguish overlapping ladder sections. In these examples, each neighboring sub-ladder has a weight exactly one greater than the previous one.
The second family combines a fan graph with another two-connected plane graph. A fan graph can be imagined as a line of points connected to one common center. By attaching this structure to another graph, the researchers show that repeated fan-based subgraphs can also be separated using carefully designed vertex–face or edge–face labels.
An especially interesting result is that these labeling measures are always finite for the plane graphs considered. The authors prove that labels based on powers of two can distinguish subgraphs through a binary-code-like system. In other words, the pattern of included faces acts like a mathematical fingerprint.
The work directly supports Sustainable Development Goal 4: Quality Education. It introduces new concepts for advanced graph theory, provides exact formulas and visual examples for teaching, and shows how abstract mathematics can develop systematic methods for identifying repeated structures. Such reasoning is valuable in mathematics, computer science, network design, and spatial modeling.
Ultimately, the study demonstrates that even when many parts of a planar network look alike, a carefully designed numerical system can give each part its own unmistakable identity.
Reference:
DOI: https://doi.org/10.3390/sym13020229
Contact:
Prof. Nurdin
+62 813-9519-0801
nurdin1701@unhas.ac.id
