Extremal degree-based topological indices of general polyomino chains via dynamic programming
Date
2026-02
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Benemérita Universidad Autónoma de Puebla
Abstract
"Based on the results of our works Maximum augmented Zagreb index on polyomino chains, which was published in the journal Applied Mathematics and Computation, and Extremal degree-based indices of general polyomino chains via dynamic programming, which is already submitted in a peer reviewed journal, in this work, we focus on the problem of finding extremal graphs with respect to degree-based topological indices, which is a major area in chemical graph theory and plays a fundamental role in the design of chemical compounds, especially as part of the QSPR analysis. In particular, we center our study in polyomino chains, which is an important graph family in the context of the extremal problem. Dividing the problem into a restricted setting and the general setting of the problem, we develop a dynamic programming framework, by means of a new encoding of polyomino chains based on local geometric descriptions which we call actions, for identifying extremal polyomino chains with respect to any degree-based topological index. Specifically, for the restricted version of the problem, our approach provides an explicit recurrence and a constructive algorithm that enable both the computation of an extremal retricted polyomino chain in linear time with respect to the number of squares and the enumeration of all extremal restricted polyomino chains in linear time with respect to their amount, being able to retrieve all non-isomorphic extremal restricted polyominoes in quadratic time with respect to the amount of extremal restricted chains".
Description
Keywords
Citation
Collections
Document Viewer
Select a file to preview:
Can't see the file? Try reloading