On degree–based topological indices of random polyomino chains

1.   Introduction

A numerical quantity $TI$ associated with a graph $G$ satisfying the equation $TI(G) = TI(G^{'})$ for every graph $G^{'}$ isomorphic to $G$ is called a graph invariant. In chemical graph theory, graph invariants that are applied in chemical investigations are known as topological indices. The goal of defining a topological index is to associate each chemical structure with a numerical value and thus investigate its properties. In fact, topological indices have found applications in Chemistry ^[1,2], Computational Linguistics ^[3], Ecology ^[4]. Nowadays, a vast number of topological indices exist in the literature ^[5]. In this paper, we pay our attention to only degree-based topological indices; whose general form is:

where $f$ is some real valued function with the property $f(x, y) = f(y, x)$ for $x, y \in \{1, 2\dots\}$ and $d_{v}$ is the degree of a node $v \in V(G)$. In the development of applications, degree-based topological indices have become a powerful tool, for instance, Forgotten index ($f(x, y) = x^{2}+y^{2}$) reflects the structure-dependency of total $\pi$-electron energy $E_{\pi}$ and measures the physical-chemical properties of molecular structures ^[6,7], the $GA$ index ($f(x, y) = 2\frac{\sqrt{xy}}{x+y}$) can be used as predictive tool in QSPR/QSAR researches ^[8] and the atom-bond connectivity index ($f(x, y) = \sqrt{\frac{x+y-2}{xy}}$) has proven to be a valuable predictive index in study of heat of formation in alkanes ^[9].

On the other hand, a polyomino system is a finite 2-connected plane graph such that each interior face (say a cell) is surrounded by a regular square of length one. In a polyomino system, two squares are said to be adjacent if they share a side. A polyomino chain is a polyomino system in which the joining of the centres of its adjacent cells forms a path $c_{1} c_{2} \ldots c_{n}$, where $c_{i}$ is the centre of the $i^{\rm {th }}$ cell. Hence, in a polyomino chain every square is adjacent with at most two other squares. If a square has only one adjacent square, it is called terminal, if it has two adjacent squares having no vertex of degree 2, it is called medial, and if it has two adjacent squares such that it has a vertex of degree 2, it is called kink. A polyomino chain without kinks is called linear chain $Li_{n}$. A polyomino chain consisting of only kinks and terminal squares is known as zigzag chain $Z_{n}$ (see Figure 1). A maximal linear chain (containing the terminal squares and kinks at its end) in the polyomino chains is called a segment of the polyomino chain.

The name polyomino was introduced in 1953 in analogy to dominoes by Solomon W. Golomb ^[10] and since then polyomino systems have been widely studied, as a matter of fact, in organic chemistry, especially in polycyclic aromatic compounds. At the present time, recent works on the polyomino chains include perfect matchings ^[11,12], finding formulas for calculating several topological indices ^{[13,14,15,16]} and extremal problems ^{[17,18,19,20,21,22]}. Specifically, random polyomino chains have attracted substantial attention from researchers in recent years ^{[23,24,25,26,27]}.

A random polyomino chain ($RPC_{n} = RPC(n, p_{1}, p_{2})$) could be constructed by the following way: for $n = 1$ and $n = 2$, $RPC_{n}$ are shown in Figure 2. For $n \geq 3$, a new square can be attached in two ways, which results in $RPC_{n}^{1}$ and $RPC_{n}^{2}$ with probability $p_{1}$ and $p_{2}$ respectively, where $0 < p_{1}, p_{2} < 1$ and $p_{1}+p_{2} = 1$, see Figure 3. For a random polyomino chain at time $n$, the value of a topological index is a random variable. Considering the arguments put forward in the previous paragraphs and by using a martingale approach, in this paper, we establish an asymptotic distribution for degree-based topological indices in a random polyomino chain. Moreover, their explicit analytical expressions of the expected value and variance are obtained. As a result, we show a general expression for calculating the degree-based topological indices for a polyomino chain. Finally, we compute the expected value of several degree-based topological indices, such as, Sombor, Forgotten, Zagreb index of a random polyomino chain.

2.   Random polyomino chain

In this section, we state and prove our main results. First, let $L_{n}$ denote the link selected at time $n\geq 3$, i.e., $L_{n}$ denotes a random variable with range $\{1, 2\}$ where $p_{i} = \mathbb{P}(L_{n} = i)$. For $i$, $j \in \{1, 2\}$, $TI_{n} = TI(RPC_{n})$, $RPC_{n}^{i}$ denotes a random polyomino chain at time $n\geq 3$ such that $L_{n} = i$, $TI_{n, i} = TI(RPC_{n}^{i})$, $RPC_{n}^{j, i}$ denotes a random polyomino chain at time $n \geq 4$ such that $L_{n-1} = j$ and $L_{n} = i$, $TI_{n, j, i} = TI(RPC_{n}^{j, i})$, $\alpha_{j, i} = TI_{4, j, i}-TI_{3, j}$, $\alpha_{i} = TI_{3, i}-TI_{2}$, $\alpha = \sum_{j = 1}^{2}\sum_{i = 1}^{2}\alpha_{j, i}p_{j}p_{i}$ and $\beta = \sum_{j = 1}^{2}\sum_{i = 1}^{2}\alpha_{j, i}^{2}p_{j}p_{i}$.

Remark 1. Note that, by definition:

1. $\alpha_{1, 1} = \alpha_{1} = 3f(3, 3),$

2. $\alpha_{1, 2} = 3f(3, 4)+f(2, 4)+f(2, 3)-2f(3, 3),$

3. $\alpha_{2, 1} = f(3, 4)-f(2, 4)+f(2, 3)+2f(3, 3),$

4. $\alpha_{2, 2} = f(4, 4)+2f(2, 4),$

5. $\alpha_{2} = 2f(3, 4)+2f(2, 4)-f(3, 3).$

Then, $\alpha_{2, 1}-\alpha_{1, 2} = \alpha_{1, 1}-\alpha_{2}$. In particular, when $f(x, y) = x^{a}+y^{a}$ with $a \in \mathbb{R}$ and $x, y \in \{1, 2, \dots\}$ the following conditions are satisfied:

1. $\alpha_{1, 1} = \alpha_{2, 1},$

2. $\alpha_{2, 2} = \alpha_{1, 2} = \alpha_{2}$.

Besides, in this case, $T I_{n} = \sum\limits_{v \in V(RPC_{n})}\left(d_{v}\right)^{a+1}$, due to the following identity

the validity of the previous expression can be consulted, for instance in ^[28].

Theorem 1. Let $RPC_{n} = RPC\left(n, p_{1}, p_{2}\right)$ be a random polyomino chain, then for $n \geq 3$

where

Proof. For $n \geq 4$, it follows from the definition of a random polyomino chain and by the definition of $TI(G)$ in Equation (1.1) the following almost-sure recursive relation of $TI_{n}$ conditional on $\mathbb{F}_{n-1}$ and the random vector $(L_{n-1}, L_{n})$

where $\mathbb{F}_{n-1}$ denotes the $\sigma$-field generated by the history of the growth of the random polyomino chain in the first $n-1$ stages. Now for $n \geq 4$, we take the expectation with respect to $(L_{n-1}, L_{n})$ to get

where, $\alpha_{j, i} = TI_{4, j, i}-TI_{3, j}$. Then, taking expectation, we obtain a recurrence relationship for $\mathbb{E}(TI_{n})$ with $n \geq 4$,

We solve Equation $(2.1)$ with the initial value $\mathbb{E}(TI_{3})$ and we obtain the result stated in the theorem,

where $\alpha = \sum\limits_{j = 1}^{2}\sum\limits_{i = 1}^{2}\alpha_{j, i}p_{j}p_{i}$. For $n \geq 4$, the expression for $\mathbb{E}(TI^{2}_{n})$ follows in a similar manner,

where $\beta = \sum\limits_{j = 1}^{2}\sum\limits_{i = 1}^{2}\alpha_{j, i}^{2}p_{j}p_{i}$, thus

then iterating, for $n \geq 3$ it is obtained that

For $n \geq 3$, the variance of $TI_{n}$ is obtained immediately by taking the difference between $\mathbb{E}(TI^{2}_{n})$ and $\mathbb{E}(TI_{n})^{2}$,

Finally, note that

where $\alpha_{i} = TI_{3, i}-TI_{2}$. In the same manner, we have

proving the theorem.

Observe that the following statements are equivalent

1. $\beta - \alpha^{2} = 0$.

2. $\alpha_{1, 1} = \alpha_{1, 2} = \alpha_{2, 2} = \alpha_{2, 1}$.

3. For $n\geq 2$, $TI_{n} = TI_{2}+\alpha(n-2)$ almost surely.

4. $f(3, 4) = (2f(4, 4)+f(2, 4))/3$, $f(3, 3) = (f(4, 4)+2f(2, 4))/3$ and $f(2, 3) = (-f(4, 4)+4f(2, 4))/3$.

Consequently, when $\beta - \alpha^{2} = 0$, $\frac{TI_{n}}{n}$ converges almost surely to $\alpha$ as $n \rightarrow \infty$. It is worth noting that by using the equivalences stated above we can conclude that, $TI_{n}$ is a deterministic sequence almost surely if and only if $\alpha_{1, 1} = \alpha_{1, 2} = \alpha_{2, 2} = \alpha_{2, 1}$. Hence, by Remark 3 if $f(x, y) = x^{a}+y^{a}$ with $a \in \mathbb{R}$ we have that $TI_{n}$ is a deterministic sequence almost surely if and only if $2\cdot3^{a+1} = 4^{a+1}+2^{a+1}, \; a \in \mathbb{R}$. The last equation has two unique solutions $a = 0, -1$, since for $a \in (-1, 0)$, $x^{a+1}$ is a strictly concave function on $\mathbb{R}^{+}$ hence $(\frac{4+2}{2})^{a+1} > \frac{4^{a+1}+2^{a+1}}{2}$ and for $a > 0$ or $a < -1$, $x^{a+1}$ is a strictly convex function on $\mathbb{R}^{+}$ hence $(\frac{4+2}{2})^{a+1} < \frac{4^{a+1}+2^{a+1}}{2}$. Therefore, $TI_{n}$ is a deterministic sequence almost surely if and only if $a\in\{0, -1\}$. This fact makes sense since

and

Now, we exploit a martingale formulation to investigate the asymptotic behavior of $TI_{n}$ when $\beta-\alpha^{2} > 0$.

Proposition 2. For $n \geq 3$, $\{M_{n} = TI_{n}-\alpha(n-3)\}_{n}$ is a martingale with respect to $\mathbb{F}_{n}$.

Proof. Observe that $\mathbb{E}(|M_{n}|) < +\infty$. For $n \geq 4$, by Theorem 1,

The proof is completed.

We use the notation $\stackrel{D}{\longrightarrow}$ to denote convergence in distribution and $\stackrel{P}{\longrightarrow}$ to denote convergence in probability. Here, $\mathrm{N}\left(\mu, \sigma^{2}\right)$ denotes a random variable with normal distribution with mean $\mu$ and variance $\sigma^{2}$.

Theorem 3. As $n \rightarrow \infty$,

Proof. For $k \geq 4$ and $j, i\in \{1, 2\}$, we have

where $\nabla M_{k} = M_{k}-M_{k-1}$ and $\nabla TI_{k} = TI_{k}-TI_{k-1}$. That is, given $\varepsilon > 0$, there exists an $N_{0}(\varepsilon) > 0$ such that, the sets $\left\{ |\nabla M_{k}| > \varepsilon\sqrt{n} \right\}$ are empty for all $n > N_{0}(\varepsilon)$. Then, we conclude that

converges to 0 almost surely, hence, $U_{n} \stackrel{P}{\longrightarrow}0$. Then, the Lindeberg's condition is verified. Next, the conditional variance condition is given by

Since,

Therefore, by the Martingale Central Limit Theorem ^[29], we thus obtain the stated result.

Finally, in order to apply the results obtained in this section, we compute the expected value of several important topological indices for a random polyomino chain (see Table 1).

3.   Polyomino chain

In this section, the goal is to obtain explicit analytical expressions to calculate $TI(PC_{n})$ where $PC_{n}$ is a polyomino chain with $n$ squares. Let $m \geq 1$ and $i \in\{1, 2, \ldots, m\}$ note that a polyomino chain $PC_{n}$ consists of a sequence of segments $s_{1}, s_{2}, \ldots, s_{m}$ (see Figure 4) with lengths $l\left(s_{i}\right) = l_{i}$ such that $\sum_{i = 1}^{m}l_{i} = n+m-1$, where $l_{i}$ is calculated by the number of squares in $s_{i}$.

Theorem 4. Let $PC_{n}$ be a polyomino chain having $n \geq 3$ squares and $m\geq 1$ segment(s) $s_{i}$ with $i = 1, 2, \dots, m$. Then

where, $I_{i} = \left\{ \begin{array}{lcc} 1 & if & l_{i} = 2 \\ \\ 0 & if & l_{i}\neq 2 \end{array}\right.$ and $\gamma = \sum\limits_{i = 2}^{m-1}I_{i}$.

Proof. Note that $PC_{n}$ is a realization of $RPC_{n}$, then we know the value of $L_{k}$ for $k = 3, 4, \dots, n$. Therefore, by using the ideas presented in Section 2 we have,

where $X_{j, i} = |\{k\in\{4, 5, \dots, n\}\; |\; L_{k-1} = j$ and $L_{k} = i$ in $PC_{n}\}|$ and $I_{1} = I_{\{l_{1} = 2\}}$. Now, if at time $k$ ($3\leq k\leq n$), $L_{k} = 2$ then the last segment in $PC_{k-1}$ is finished (so, a new segment is initiated in $PC_{k}$) and if at time $k$, $L_{k} = 1$ then a square is added to the last segment in $PC_{k-1}$. Hence, $X_{2} = |\{k\in\{3, 4, \dots, n\}\; |\; L_{k} = 2$ in $PC_{n}\}| = m-1$ and $X_{1} = |\{k\in\{3, 4, \dots, n\}\; |\; L_{k} = 1$ in $PC_{n}\}| = n-2-(m-1) = n-m-1$. Moreover, $X_{1, 2} = |\{i\in\{1, 2, \dots, m-1\}\; |\; l_{i}\neq2$ in $PC_{n}\}|$ and $X_{2, 1} = |\{i\in\{2, 3, \dots, m\}\; |\; l_{i}\neq2$ in $PC_{n}\}|$. We may write this as: $X_{1, 2} = m-\gamma-1-I_{1}$ and $X_{2, 1} = m-\gamma-1-I_{m}$, where,

Consequently, $X_{1, 1} = n-2m +\gamma-1+I_{1}+I_{m}$ and $X_{2, 2} = \gamma$, because of the following identities

Finally, we arrive at the desired result by replacing the values of $X_{j, i}$, $\alpha_{j, i}$ and $\alpha_{2}$.

Remark 2. 1. By using that $\sum\limits_{i = 1}^{m}l_{i} = n+m-1$, it is verified that, $X_{1, 1} = \sum\limits_{l_{i}\neq 2}(l_{i}-3)$.

2. On the other hand, by definition if $f(x, y) = x^{a}+y^{a}$ with $a \in \mathbb{R}$ then the coefficients of $\gamma$ and $I_{1}+I_{m}$ in Theorem 4 are zero and the coefficient of $m$ is zero, i.e., the general expression showed in Theorem 4 is independent of $m$ if and only if $2\cdot3^{a+1} = 4^{a+1}+2^{a+1}$ if and only if $a\in\{0, -1\}$.

3. Finally, by the way, in ^[30] the authors established a general expression for calculating the bond incident degree (BID) indices of a polyomino chain; which follows from Theorem 4. $BID$ indices form a subclass of the class all degree-based topological indices.

By definition if $PC_{n} = Li_{n}$, we deduce that $m = 1$ and $l_{1} = n$ and if $PC_{n} = Z_{n}$, then $m = n- 1$ and $l_{i} = 2$ for $i = 1, 2, \dots, m$. Therefore, the following corollary may be obtained directly by Theorem 4.

Corollary 1. Let $Li_{n}$ and $Z_{n}$ be linear and zigzag chains respectively with $n \geq 3$ squares. Then

$T I\left(Z_{n}\right) = (2f(2, 4)+f(4, 4))n+$$4f(2, 3)-3f(4, 4)+2f(3, 4)-4f(2, 4)+2f(2, 2).$

It is worth noting that in 2020, Buragohain et al. ^[31] introduced a novel generalized topological index for some chemical structures defined as

In ^[13] the authors studied the generalized $ISI_{(\alpha, \beta)}$-index and $(\alpha, \beta)$-Zagreb index of a linear chain. By using Corollary 1 the results showed in ^[13] can be obtained. In addition, taking $f(x, y) = x^{2}+y^{2}$ in Equation (1.1), we obtain the Forgotten index. Recently, in ^[15] the computation of the Forgotten index in a polyomino chain was given as follows:

Corollary 2. Let $n \geq 2$ and $PC_{n}$ be a polyomino chain with $m\geq 1$ segment(s). Then $F\left(PC_{n}\right) = 54 n+18m-40$.

Note that, the general expression obtained in Corollary 2 is independent of $\gamma, I_{1}$ and $I_{m}$; which makes sense because of Remark 4. In a similar manner, we can obtain the above result from Theorem 4. Finally, in the following results by using Theorem 4 we will compute $TI(PC_{n})$ of several kinds of polyomino chains.

Corollary 3. For the polyomino chain with $n\geq3$ squares and $2$ segments $s_{1}$ and $s_{2}$ satisfy $l_{1} = 2$and $l_{2} = n-1$, $PC_{n}^{1}$, we have the following:

and for $n\geq 4$

Corollary 4. For the polyomino chain with $n\geq5$ squares and $m \geq 3$ segments $s_{1}, s_{2}, \dots, s_{m}$ satisfy $l_{1} = l_{m} = 2$and $l_{2}, l_{3}, \dots, l_{m-1}\geq 3$, $PC_{n}^{2}$, we have the following:

Corollary 5. For the polyomino chain with $n\geq6$ squares and $m \geq 3$ segments $s_{1}, s_{2}, \dots, s_{m}$ satisfy $l_{1} = 2$ and $l_{2}, l_{3}, \ldots, l_{m} \geq 3$ or $l_{m} = 2$ and $l_{1}, l_{2}, \ldots, l_{m-1} \geq 3$, $PC_{n}^{3}$, we have the following:

Corollary 6. For the polyomino chain with $n\geq 7$ squares and $m \geq 3$ segments $s_{1}, s_{2}, \dots, s_{m}$ satisfy $l_{1}, l_{2}, \ldots, l_{m} \geq 3$, $PC_{n}^{4}$, we have the following:

Actually, the authors in ^[32,33,34] calculated several topological indices, such as, redefined Zagreb index, harmonic index and inverse sum index for $L_{n}$, $Z_{n}$ and $PC_{n}^{i}$ with $i = 1, 2$; which are deduced from Corollaries 1, 3 and 4. Besides, in ^[7,35,36] the authors computed Forgotten, {R}andić and generalized Zagreb index for $L_{n}$, $Z_{n}$ and $PC_{n}^{i}$ with $i = 1, 2, 3, 4$; hence we can deduce the results above mentioned by using Corollaries 1, 3, 4, 5 and 6. In fact the results showed in ^[7] can be verified directly by Corollary 2.

On the other hand, here a polyomino chain of dimension $n\geq 1$ with $k = k_{1}+ k_{2} + k_{3}$ where $k_{1}$ is the number of kinks, $k_{2}$ is the number of medials and $k_{3}$ is the number of terminals in a unit of polyomino chain will be denoted by $PC_{n, k}$. In Figure 5, a general representation of a polyomino chain $PC_{n, k}$ is depicted. Let $k\geq 3$, by definition of $PC_{n, k}$, we have: $m = 2n,$ $\gamma = n-1$, $I_{m} = 1$ and $I_{1} = I_{\{k = 3\}}.$ Hence, in the following corollary, we will compute $TI(PC_{n, k})$ for $k\geq 3$ by using Theorem 4.

Remark 3. Note that, by definition $PC_{n, 1} = Li_{n}$ and $PC_{n, 2} = Z_{2n}$.

Corollary 7. Let $k \geq 3$, $n\geq 1$, then we have

In fact, in ^[37] Hayat et al. computed the exact analytical expressions of the $ABC$, $GA$, $ABC_{4}$ and $GA_{5}$ index for $PC_{n, k}$ with $k = 3, 4, 5$. These results can be obtained as a consequence of Corollary 7.

4.   Conclusion

In this paper, we proposed a martingale approach to the study of topological indices in random polyomino chains. The expected value and variance have been determined and we formulated a martingale to characterize the asymptotic behavior of the topological indices. Moreover, we considered some particular topological indices, such as, the first Zagreb, Sombor, harmonic, geometric-arithmetic and second Zagreb index for a random polyomino chain. In fact, from the derived results, several known results about polyomino chains were obtained as corollaries. We believe the results obtained in this paper can provide theoretical support for the chemical research. By the way, the extremal random polyomino chains with respect to several well-known degree-based topological indices have been discussed in our next paper. Finally, it would be interesting to extend the work of this paper to $k$-polygonal chains. We expect to develop it in the future.

Acknowledgments

All three authors would like to thank two anonymous referees for valuable comments that definitely help improve the quality of the paper.

Conflict of interest

The authors declare there is no conflict of interest.