Expected Gutman index of Markov-dependent random polyomino chains

Document Type : Research Paper

Authors

Department of Mathematics, Shahed University, Tehran, Iran

Abstract

We introduce a Markov-dependent random model for polyomino chains in which each new square is attached linearly or as a kink according to a stationary two-state Markov chain. This model retains the geometric construction of classical random polyomino chains while allowing consecutive attachment types to be dependent.
 
We develop a direct recursive method based on weighted distance sums associated with the two exposed edges of the terminal square. This method yields exact recursive relations for the auxiliary distance quantities and leads to a closed formula for the expected Gutman index. The independent Bernoulli model is recovered when the two transition probabilities are equal. The deterministic linear and zigzag polyomino chains are also obtained as limiting cases.
 
Our results show that the expected Gutman index depends not only on the stationary frequency of kink attachments, but also on the dependence between consecutive attachments.

Keywords

Main Subjects


[1] A. Ali, Z. Raza and A. A. Bhatti, Bond incident degree (BID) indices of polyomino chains: a unified approach, Appl. Math. Comput., 287–288 (2016) 28–37.
[2] L. Azami and N. Jafari-Rad, Gutman index of polyomino chains, J. Disc. Math. Appl., 10 no. 4 (2025) 375–392.
[3] F. Buckley and F. Harary, Distance in graphs, Addison-Wesley Publishing Company, Advanced Book Program, Redwood City, CA, 1990.
[4] A. L. Chen and F. J. Zhang, Wiener index and perfect matchings in random phenylene chains, MATCH Commun. Math. Comput. Chem., 61 no. 3 (2009) 623–630.
[5] H. Deng, Wiener indices of spiro and polyphenyl hexagonal chains, Math. Comput. Modelling, 55 no. 3-4 (2012) 634–644.
[6] H. Deng, S. Balachandran, S. K. Ayyaswamy and Y. B. Venkatakrishnan, The harmonic indices of polyomino chains, Nat. Acad. Sci. Lett., 37 no. 5 (2014) 451–455.
[7] A. A. Dobrynin and A. A. Kochetova, Degree distance of a graph: A degree analog of the Wiener index, J. Chem. Inf. Comput. Sci., 34 no. 5 (1994) 1082–1086.
[8] S. W. Golomb, Polyominoes, Puzzles, patterns, problems, and packings. With diagrams by Warren Lushbaugh, Second edition, With an appendix by Andy Liu, Princeton University Press, Princeton, NJ, 1994.
[9] F. Guo, H. Wang, M. Yang and S. Wang, The limiting behaviors for the Gutman index and the Schultz index in a random (2k + 1)-polygonal chain, Filomat, 38 no. 7 (2024) 2487–2501.
[10] I. Gutman, Selected properties of the Schultz molecular topological index, J. Chem. Inf. Comput. Sci., 34 no. 5 (1994) 1087–1089.
[11] H. Hosoya, Topological index, a newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbons, Bulletin of the Chemical Society of Japan, 44 no. 9 (1971) 2332–2339.
[12] X. Liu and Q. Zhan, The expected values for the Gutman index and Schultz index of random polygonal chains, Molecules, 27 no. 20 (2022) 6838.
[13] L. Ma, H. Bian, B. J. Liu and H. Z. Yu, The expected values of the Wiener indices in the random phenylene and spiro chains, Ars Combin., 130 (2017) 267–274.
[14] M. Randi´c, Characterization of molecular branching, J. Am. Chem. Soc., 97 no. 23 (1975) 6609–6615.
[15] S. C. Sigarreta, S. M. Sigarreta and H. Cruz-Suarez, On degree-based topological indices of random polyomino chains, Math. Biosci. Eng., 19 no. 9 (2022) 8760–8773.
[16] S. Sigarreta and H. Cruz-Suarez, Zagreb connection indices on polyomino chains and random polyomino chains, Open Math., 22 no. 1 (2024) Paper No. 20240057, 14 pp.
[17] C. Tao, S. Tang and X. Geng, The limiting behaviors of the Gutman and Schultz indices in random 2k-sided chains, Axioms, 13 no. 8 (2024) 518.
[18] D. B. West, Introduction to graph theory, Prentice Hall, Inc., Upper Saddle River, NJ, 1996.
[19] H. Wiener, Structural determination of paraffin boiling points, J. Am. Chem. Soc., 69 no. 1 (1947) 17–20.
[20] Z. Yarahmadi, A. R. Ashrafi and S. Moradi, Extremal polyomino chains with respect to Zagreb indices, Appl. Math. Lett., 25 no. 2 (2012) 166–171.
[21] L. L. Zhang, Q. S. Li, S. C. Li and M. J. Zhang, The expected values for the Schultz index, Gutman index, multiplicative degree-Kirchhoff index and additive degree-Kirchhoff index of a random polyphenylene chain, Discrete Appl. Math., 282 (2020) 243–256.

Articles in Press, Corrected Proof
Available Online from 29 September 2026
  • Receive Date: 19 July 2026
  • Revise Date: 08 September 2026
  • Accept Date: 22 September 2026
  • Published Online: 29 September 2026