Extremal degree-based indices of general polyomino chains via dynamic programming

Imagine you are an architect tasked with building the most efficient "molecular city" possible using only square bricks. In the world of chemistry, these square bricks represent atoms, and the way they connect determines how the molecule behaves (like how well it dissolves in water or how high it boils).

This paper is about finding the perfect arrangement of these square bricks to maximize a specific "score" (called a topological index). The authors didn't just guess; they built a mathematical machine to solve this puzzle.

Here is the breakdown of their work using simple analogies:

1. The Problem: The "Lego" Puzzle

Think of a polyomino chain as a long snake made of square Lego bricks glued edge-to-edge.

Restricted Chains: Imagine you are only allowed to build this snake by adding bricks strictly to the right or down. It's a very orderly, predictable process.
General Chains: Now, imagine you can add bricks anywhere—up, down, left, right, or even twisting back on yourself. This creates a much more chaotic and complex world.

The authors wanted to know: If I have exactly $N$ bricks, what is the exact shape that gives the highest "score" for a specific chemical property?

2. The Old Way vs. The New Way

The Old Way (The "One-to-One" Trap):
In the past, scientists studied the "Restricted" chains. Because the rules were strict (only right/down), there was a perfect one-to-one match between the order you added bricks and the shape you got. It was like following a recipe where every step leads to exactly one cake.

The New Way (The "General" Chaos):
When you allow bricks to go in any direction, the recipe breaks. You can follow different instructions and end up with the same shape, or follow instructions that look valid but result in a shape that physically can't exist (like bricks overlapping). This made it impossible to use old math tricks to find the best shape.

3. The Solution: The "Action" Translator

The authors invented a clever Dynamic Programming framework. Think of this as a translator that converts a complex 3D building problem into a simple 1D string of instructions.

Instead of worrying about the exact coordinates of every brick, they broke the building process down into "Actions":

SS (Same-Same): Keep going straight.
SC (Same-Change): Go straight, then turn.
CS (Change-Same): Turn, then go straight.
TT (Tight Turn): A sharp, specific kind of twist.

They realized that the "score" of the molecule depends only on the last few actions you took, not the whole history. This is the key to Dynamic Programming: instead of checking every possible building path (which would take forever), you only need to remember the best score you could get ending with a specific action.

4. The "Safety Zone" Check

Here is the tricky part: Just because a string of actions (like "Straight, Turn, Straight") makes sense mathematically, doesn't mean you can actually build it without the bricks crashing into each other.

The authors created a "Safety Zone" algorithm (Algorithms 1, 2, and 3 in the paper).

Imagine the building site has invisible "no-go" zones.
Their algorithm acts like a safety inspector. It takes a theoretical string of actions and checks: "If I build this, will the new brick hit an old one?"
If the answer is "Yes," it tweaks the instructions slightly (like flipping a turn from Left to Right) to ensure the structure is physically possible.

5. The Big Discovery: The "Mod 4" Rhythm

When they applied this system to a specific score called the Generalized Randić Index (specifically where the parameter $\alpha = -1$ ), they found a beautiful pattern.

The best shape depends entirely on how many bricks you have, specifically looking at the remainder when you divide that number by 4.

If you have 3, 7, 11... bricks (remainder 3), the best shape is a specific zig-zag pattern.
If you have 4, 8, 12... bricks (remainder 0), the best shape is a slightly different variation.
And so on for remainders 1 and 2.

They didn't just find one best shape; they found families of shapes. For example, if you have a huge number of bricks, there might be dozens of different ways to arrange them that all tie for the "best" score.

6. Why This Matters

For Chemists: It tells them exactly how to arrange molecules to get specific properties (like better solubility for medicine).
For Mathematicians: They solved a problem that had been open since 2015.
For Everyone: It shows that even in a chaotic system (general chains), there is an underlying rhythm (the Mod 4 pattern) that can be found using a smart, step-by-step computer strategy.

Summary Analogy

Imagine you are trying to find the fastest route through a massive, twisting maze.

Old method: You try every single path until you find the winner. (Takes forever).
This paper's method: You realize that the speed of the path only depends on the last few turns you made. You build a "map of the best last turns" (Dynamic Programming). You then use a "traffic cop" (the Safety Algorithm) to ensure your theoretical route doesn't crash into walls.
Result: You instantly know the fastest route for any maze size, and you discover that the fastest routes follow a repeating 4-step rhythm.

The authors have essentially handed chemists and mathematicians a GPS for finding the perfect molecular shapes.

Here is a detailed technical summary of the paper "Extremal degree-based indices of general polyomino chains via dynamic programming" by Manuel Montes-y-Morales, Saylé Sigarreta, and Hugo Cruz-Suárez.

1. Problem Statement

The paper addresses the problem of identifying extremal general polyomino chains (graphs formed by gluing unit squares edge-to-edge where the inner dual is a path) that maximize or minimize specific degree-based topological indices.

Context: While extremal problems for restricted polyomino chains (where growth is limited to specific directions, e.g., right or down) have been studied, the class of general polyomino chains presents a significantly larger configuration space.
The Challenge: In general chains, there is no one-to-one correspondence between a sequence of growth instructions and a unique geometric realization. A local description of a chain's growth does not uniquely determine a globally realizable geometry (i.e., a sequence of instructions might theoretically describe a chain that self-intersects or creates invalid cells).
Specific Goal: The authors aim to resolve an open problem posed in 2015 regarding the generalized Randić index ( $R_\alpha$ ) with parameter $\alpha = -1$ (also known as the second modified Zagreb index). They seek to determine, for any number of squares $n$ , which general polyomino chains maximize $R_{-1}$ .

2. Methodology

The authors propose a Dynamic Programming (DP) framework that decouples the geometric realizability constraints from the optimization of the topological index. The methodology proceeds in four main stages:

A. Encoding via "Links" and "Actions"

Instead of working directly with geometric coordinates, the authors encode chains using a sequence of links ( $L_k \in \{1, 2, 3\}$ ) representing how a new square is attached.

Link Types:
- Type 1: Continues in the same direction.
- Type 2: Changes direction but reuses the previous orientation.
- Type 3: Changes direction and flips the orientation (tight turn).
Local Realizability: Not all link sequences form valid chains. However, the authors define locally realizable sequences (those without consecutive forbidden patterns like $(2,3)$ or $(3,3)$ ).
Action Abstraction: To facilitate DP, they group consecutive links into actions ( $SS, SC, CS, CC, TT$ ). The contribution of a new square to the degree-based index depends only on the last three links (or the current action). This allows the index to be calculated recursively:
$TIf(\text{Chain}_n) = TIf(\text{Chain}_{n-1}) + \text{contribution}(\text{Action}_n)$

B. Handling Validity (The "Parity Correction")

The core difficulty is that an optimal sequence of actions might not correspond to a valid geometric chain. The authors introduce Algorithms 1 and 2 to bridge this gap:

Algorithm 1 (Parity Correction): Takes a sequence of compressed actions and modifies it to ensure the "direction change parity" is even at specific points. This guarantees that the resulting chain does not self-intersect in a way that violates the polyomino definition.
Algorithm 2 (Translation): Converts the corrected action sequence back into a sequence of links ($1, 1, L_3, \dots, L_n$).
Theorem 4.5: Proves that the link sequence generated by this pipeline is globally realizable (forms a valid general polyomino chain) and preserves the degree-based index value.

C. Dynamic Programming Formulation

The authors define $M_f(n, S)$ and $M_f(n, C)$ as the maximum index values for chains of size $n$ ending in specific action types.

Recurrence Relations: Based on the local additivity of the index, they derive recurrences for $n \geq 6$ $n \geq 6$ :
- $M_f(n, S) = \max(M_f(n-1, S) + g(SS), M_f(n-1, C) + g(CS))$
- $M_f(n, C) = \max(\dots, M_f(n-3, S) + g(ST), \dots)$
Complexity: The optimization step runs in $O(n)$ time.

D. Reconstruction and Exhaustive Analysis

While the DP finds the optimal value and one optimal action sequence, finding all extremal chains requires handling "pivots" (points where multiple instruction choices exist, specifically in $SC$ actions).

Algorithm 4: Generates all instruction sequences from an action sequence.
Lemma 5.5: Provides specific criteria to fix pivots in certain patterns, reducing the search space.
Exhaustive Analysis: For small $n$ or specific cases, the authors verify validity by checking all generated instruction sequences against geometric constraints (Lemma 2.6).

3. Key Contributions

General Framework: A unified, constructive DP approach for extremal problems on general polyomino chains for any degree-based index, overcoming the lack of unique geometric encoding in the general case.
Validity Guarantee: The introduction of Algorithms 1 and 2 provides a rigorous method to convert abstract action sequences into valid geometric chains without losing the optimal index value.
Resolution of Open Problem: The paper solves the 2015 open problem for $R_{-1}$ ( $\alpha = -1$ ), characterizing the exact families of chains that maximize this index for any $n$ .
Structural Characterization: The authors identify that the extremal configurations depend explicitly on the residue class of $n \pmod 4$ .

4. Main Results (Specific to $R_{-1}$ )

For a general polyomino chain with $n$ squares, the maximizing configurations for $R_{-1}$ are determined by $n = k + 4m$ (where $k \in \{3, 4, 5, 6\}$ ):

Case $n = 3 + 4m$ : The unique extremal family is $C^{m+1}_3$ (chains with $m+1$ horizontal segments of length 3).
Case $n = 4 + 4m$ : The extremal family is $C^{m,1}_{3,4}$ (chains with $m$ segments of length 3 and one of length 4). There are $m+1$ such chains.
Case $n = 5 + 4m$ : Three families maximize the index: $\bar{C}^{m+1}_3$ , $C^{m,1}_{3,5}$ , and $C^{m-1,2}_{3,4}$ . The total number of maximal chains is $\frac{(m+1)(m+4)}{2}$ .
Case $n = 6 + 4m$ : Five families maximize the index, including $C^{m,1}_{3,6}$ , $\bar{C}^{m,1}_{3,4}$ , $\bar{C}^{m,1}_{3,4}$ (vertical variant), $C^{m-1,1,1}_{3,4,5}$ , and $C^{m-2,3}_{3,4}$ . The total count is $\frac{(m+1)(m+2)(2m+18)}{12}$ .

The maximum value is given by the formula:
$M(n) = \frac{11}{18} + \frac{1}{3k} + \frac{143}{144}m$

5. Significance

Theoretical Impact: The work bridges the gap between combinatorial graph theory and chemical graph theory by providing a systematic way to handle "general" structures that were previously intractable due to geometric constraints.
Methodological Innovation: The separation of the optimization (DP on actions) from the realizability (Algorithms 1 & 2) is a powerful technique that can be applied to other recursive graph families.
Practical Application: The results provide exact structural descriptions for molecules modeled as polyomino chains that optimize specific physicochemical properties (correlated with $R_{-1}$ ).
Open Problems: The authors note that while they can generate one extremal chain efficiently, generating all valid extremal chains remains computationally hard ( $O(2^{n/2})$ ) due to the complexity of verifying geometric validity for all pivot choices. They call for further research into necessary and sufficient conditions for validity.

The paper includes a link to the implementation code, which computes these extremal chains in linear time for the value and reconstruction, and handles the exhaustive analysis for smaller cases.