Self-reverse labelings of distance magic graphs

This paper introduces the concept of self-reverse distance magic labelings for regular graphs, demonstrates their existence in several infinite families of tetravalent graphs, presents a novel construction method to generate new such graphs, and provides a complete classification of connected tetravalent graphs up to order 30 that admit these labelings.

The Gist

Imagine you have a group of friends standing in a circle, holding hands. Now, imagine you give each friend a unique number tag, from 1 up to the total number of people in the group.

In the world of math, a "Distance Magic Graph" is a very special arrangement of friends where a magical rule applies: No matter which friend you pick, if you add up the numbers of all their immediate neighbors, you always get the exact same total.

It's like a perfectly balanced scale. If you pick Friend A, their neighbors' numbers sum to 100. If you pick Friend B, their neighbors also sum to 100. It works for everyone.

The New Twist: The "Self-Reverse" Labeling

The authors of this paper discovered a special, super-organized way to assign these numbers. They call it a "Self-Reverse" labeling.

Think of it like a mirror or a seesaw.

• If you have a friend with the number 1, there is a "partner" friend with the number -1 (or in their math version, the number that balances it out to zero).
• If you have a friend with 5, their partner has -5.
• The rule is: If Friend A is friends with Friend B, then Friend A's "mirror partner" must be friends with Friend B's "mirror partner."

It's as if the whole group is perfectly symmetrical. If you flipped the group over a mirror, the friendship connections would look exactly the same, just with the numbers swapped.

Why is this cool? (The "Shadow" Analogy)

The authors realized that when a graph has this "Self-Reverse" property, you can describe the whole complex group by looking at a much smaller, simpler "shadow" version of it.

Imagine a massive, intricate castle. Usually, to describe the castle, you need blueprints for every single room, window, and door. But if the castle is perfectly symmetrical (like a snowflake), you only need to draw one small slice of it. You can then say, "Just copy this slice, flip it, and glue it together," and you get the whole castle.

In math terms, this "slice" is called a Quotient Graph. The authors found that for many complex 4-connected graphs (graphs where everyone has exactly 4 friends), this "Self-Reverse" trick lets them shrink the problem down to a tiny, manageable puzzle.

What Did They Actually Do?

1. The "Merge" Machine: They invented a new way to build big magic graphs from smaller ones. Imagine taking two small, perfectly balanced groups of friends and stitching them together in a specific pattern. They proved that if you do this right, the new, bigger group is also magically balanced.
2. The Great Hunt: They used computers to check every possible small group of friends (up to 30 people) to see which ones could be arranged this way.
   • They found that for groups of even sizes (6, 8, 10...), it's usually easy to find these magic arrangements.
   • For groups of odd sizes, it's much harder. They found that you generally need at least 21 people to make it work, and there are some "forbidden" sizes (like 19) where it's impossible.
3. The "Symmetry" Surprise: They looked for groups that are not just balanced, but also Vertex-Transitive. This is a fancy way of saying: "Every single person in the group is exactly the same as every other person." In a normal party, the host might be different from the guests. In a Vertex-Transitive party, everyone is interchangeable.
   • They found that these "Super-Symmetric" magic groups are extremely rare.
   • They found a few weird ones that don't follow the usual patterns (like the famous "Petersen Graph" appearing as a shadow of a 20-person group).

The Big Questions Left Behind

The paper ends by asking some fascinating questions for future explorers:

• The Odd One Out: Can we find a group with an odd number of people that is perfectly symmetrical (everyone is interchangeable) AND follows the magic sum rule? So far, no one has found one.
• The Mirror Test: Are there any super-symmetric groups that cannot be arranged in this "Self-Reverse" mirror way?
• The Infinite Search: Are there infinite families of these rare, super-symmetric magic groups that we haven't discovered yet?

In a Nutshell

This paper is like a guidebook for building perfectly balanced social networks. The authors found a secret "mirror trick" that makes building these networks easier, discovered a machine to combine small networks into big ones, and mapped out exactly which sizes of groups can exist. They also highlighted that the most perfectly symmetrical versions of these groups are like unicorns: incredibly rare and mysterious, waiting for the next explorer to find them.

Technical Summary

Here is a detailed technical summary of the paper "Self-reverse labelings of distance magic graphs" by Petr Kovář, Ksenija Rozman, and Primož Šparl.

1. Problem Statement

The paper addresses the classification and structural analysis of distance magic graphs, specifically focusing on regular graphs (graphs where every vertex has the same degree). A graph $\Gamma$ of order $n$ is distance magic if its vertices can be labeled bijectively with integers such that the sum of the labels of the neighbors of any vertex is constant.

While the general class of distance magic graphs is diverse and lacks a universal construction method, the authors restrict their scope to regular graphs, particularly tetravalent (4-regular) graphs. The core problem is to investigate a specific subclass of labelings called self-reverse distance magic labelings. The authors aim to:

1. Define and characterize self-reverse labelings.
2. Determine which orders $n$ admit connected tetravalent graphs with such labelings.
3. Develop a general construction method to generate new distance magic graphs from existing ones.
4. Analyze the existence of these labelings in highly symmetric graphs (vertex-transitive and edge-transitive).

2. Methodology and Definitions

2.1 Alternative Labeling Definition

The authors utilize an alternative definition of distance magic labelings for regular graphs of order $n$. Instead of labeling with $\{1, \dots, n\}$, they use the arithmetic progression $I_n = \{1-n, 3-n, \dots, n-1\}$ with a common difference of 2. A labeling $\ell$ is distance magic if the sum of neighbor labels for every vertex is 0. This is equivalent to the classical definition but simplifies algebraic manipulations.

2.2 Self-Reverse Labelings

A distance magic labeling $\ell$ is self-reverse if the involution that maps every vertex $v$ to its "antipodal" vertex $v_\ell$ (where $\ell(v) + \ell(v_\ell) = 0$) is an automorphism of the graph.

• Implication: This property allows the graph to be viewed as a 2-fold cover (specifically a regular $\mathbb{Z}_2$-cover) of a smaller quotient graph.
• Structure: The vertex set is partitioned into pairs $\{v, v_\ell\}$. The quotient graph has vertices representing these pairs. Edges in the quotient are either "solid" (representing a perfect matching between pairs) or "dashed" (representing all possible edges between pairs), or semiedges (if $v \sim v_\ell$).

2.3 Degeneracy

The authors distinguish between degenerate and non-degenerate self-reverse labelings:

• Degenerate: Occurs if there exist adjacent vertices $u, v$ such that $u$ is adjacent to both $v$ and $v_\ell$. The authors prove that for tetravalent graphs, degenerate self-reverse labelings exist only for wreath graphs ($W(m)$), which are lexicographic products of cycles and edgeless graphs of order 2.
• Non-degenerate: The primary focus of the paper, as these labelings correspond to more complex, non-wreath graph structures.

2.4 General Construction (The Merge Operation)

The paper introduces a novel construction, Construction 5.1, called the merge of two graphs $\Gamma$ and $\Gamma'$:

• Process: Select a cycle (cyclet) $C$ in $\Gamma$ and $C'$ in $\Gamma'$ of the same even length $d$. Remove the edges of these cycles and reconnect the vertices by adding edges $u_i v_{i+1}$ and $v_i u_{i+1}$.
• Conditions for Distance Magic: If $\Gamma$ and $\Gamma'$ are distance magic, and specific conditions regarding balanced bipartitions and alternating cycles are met (Proposition 5.2), the resulting merged graph is distance magic.
• Self-Reverse Preservation: Corollary 5.3 establishes that if the original labelings are self-reverse and the cycles satisfy specific symmetry conditions (e.g., $u_{i+d/2} = u_\ell$), the resulting merged graph admits a self-reverse distance magic labeling.

3. Key Results

3.1 Classification of Orders (Theorem 6.1)

The authors provide a complete classification of integers $n$ for which a connected tetravalent graph admitting a self-reverse distance magic labeling exists:

• Even Orders: Exist for all $n \ge 6$.
• Odd Orders: Exist for all $n \ge 21$.
• Non-degenerate/Non-wreath:
  • Non-degenerate labelings exist for $n \in \{8, 16, 18, 20, 21\}$ and all $n \ge 23$.
  • Graphs that are not wreath graphs exist for all $n \ge 18$, except $n=19$ and $n=22$.

3.2 Computational Data (Orders up to 30)

Using computational enumeration, the authors determined the number of non-equivalent non-degenerate self-reverse labelings for connected tetravalent graphs up to order 30.

• Key Finding: For $n \ge 23$, at least one such graph exists.
• Symmetry Analysis: They analyzed vertex-transitive graphs.
  • No connected tetravalent vertex-transitive distance magic graph of odd order (up to 29) was found.
  • For even orders, only five non-wreath vertex-transitive examples exist up to order 30 (orders 18, 20, 24, 24, 30).
  • Notable examples include the Cartesian product $C_3 \square C_6$ (order 18) and specific circulants.

3.3 Quotient Graphs

The study reveals that the quotient graphs of these self-reverse labelings are often highly structured. For instance, a specific tetravalent graph of order 20 yields the Petersen graph (with semiedges) as its quotient.

4. Significance and Future Directions

• Structural Insight: The concept of self-reverse labelings provides a powerful tool for encoding complex distance magic graphs via smaller quotient graphs and voltage assignments, linking the field to graph cover theory.
• Construction Method: The "merge" operation offers a systematic way to generate infinite families of new distance magic graphs from known ones, addressing the lack of general construction methods in the field.
• Symmetry and Rarity: The results highlight that while distance magic graphs are common, those that are both distance magic and vertex-transitive (especially with self-reverse labelings) are extremely rare.
• Open Questions: The paper concludes with several open problems:
  1. Do connected tetravalent vertex-transitive distance magic graphs of odd order exist?
  2. Characterize all connected tetravalent edge-transitive distance magic graphs.
  3. Are there infinitely many connected tetravalent vertex-transitive distance magic graphs that are not Cayley graphs? (The paper identifies one such example of order 20).

Conclusion

This paper significantly advances the theory of distance magic graphs by introducing the self-reverse property, which simplifies the structural analysis of regular graphs. By combining theoretical proofs (classification of orders, construction methods) with extensive computational data, the authors establish a comprehensive framework for understanding tetravalent distance magic graphs and identify specific gaps in the existence of highly symmetric examples, setting the stage for future research in algebraic graph theory.