Two-terminal reliability of Markov-dependent directed polyomino-chain networks and its relation to the Gutman index

Document Type : Original Scientific Paper

Authors

Department of Mathematics‎, ‎Shahed University‎, ‎Tehran‎, ‎Iran

10.22034/jsmta.2026.25047.1239

Abstract

This paper introduces an exact two-terminal reliability framework for communication networks whose topologies are modeled by directed polyomino chains‎. ‎Here‎, ‎``directed'' specifies the prescribed growth and attachment convention; communication links themselves are undirected‎. ‎The skeleton graph of a polyomino chain is interpreted as a modular communication network‎, ‎in which vertices represent communication nodes and edges represent links subject to independent failures‎. ‎Two boundary interfaces are used to define the source and destination terminals‎. ‎For a fixed directed attachment sequence‎, ‎the two-terminal reliability is defined as the probability that the source and destination remain connected after random link failures‎. ‎To compute this quantity for arbitrary chain lengths‎, ‎we develop a finite transfer-matrix method based on the connectivity partition of the source and the three active boundary vertices of the terminal square‎. ‎Separate transfer matrices are constructed for linear and kink attachments‎. ‎This approach avoids exhaustive enumeration of all link-failure configurations and yields exact reliability polynomials for deterministic directed polyomino chains‎. ‎We further consider random network topologies generated by a stationary two-state Markov attachment process‎. ‎A block-matrix representation is derived for the mean two-terminal reliability‎, ‎incorporating both the dependence in the geometric growth of the chain and the independent failures of communication links‎. ‎In addition‎, ‎the Gutman index of the original polyomino-chain graph is considered as a structural descriptor of the network topology‎. ‎Rather than assuming an a priori monotone relation between the Gutman index and communication reliability‎, ‎the proposed framework enables their exact comparison within directed polyomino chains‎. ‎The resulting model provides a mathematically tractable setting for studying the interplay between topological structure‎, ‎dependent network geometry‎, ‎and reliability performance.

Keywords

Main Subjects


Akyildiz, I.F., Su, W., Sankarasubramaniam, Y. and Cayirci, E. (2002). Wireless sensor networks: a survey. Computer Networks, 38(4):393–422.
Ali, A., Raza, Z. and Bhatti, A.A. (2016). Bond incident degree (BID) indices of polyomino chains: A unified approach. Applied Mathematics and Computation, 287:28–37.
Azami, L. and Jafari Rad, N. (2025). Gutman index of polyomino chains. Journal of Discrete Mathematics and Its Applications, 10(4):375–392.
Ball, M.O. (1986). Computational complexity of network reliability analysis: an overview. IEEE Transactions on Reliability, 35(3):230–239.
Colbourn, C.J. (1987). The Combinatorics of Network Reliability. New York: Oxford University Press.
Deng, H., Balachandran, S., Ayyaswamy, S.K. and Venkatakrishnan, Y.B. (2014). The harmonic indices of polyomino chains. National Academy Science Letters, 37(5):451–455.
Dobrynin, A.A. and Kochetova, A.A. (1994). Degree distance of a graph: A degree analog of the Wiener index. Journal of Chemical Information and Computer Sciences, 34(5):1082–1086.
Golomb, S.W. (1994). Polyominoes: Puzzles, Patterns, Problems, and Packings. 2nd edition, Princeton University Press.
Gutman, I. (1994). Selected properties of the Schultz molecular topological index. Journal of Chemical Information and Computer Sciences, 34(5):1087–1089.
Sigarreta, S.C., Sigarreta, S.M. and Cruz-Suárez, H. (2022). On degree-based topological indices of random polyomino chains. Mathematical Biosciences and Engineering, 19(9):8760–8773.
Sigarreta, S. and Cruz-Suárez, H. (2024). Zagreb connection indices on polyomino chains and random polyomino chains. Open Mathematics, 22(1):20240057.
Tanguy, C. (2007). What is the probability of connecting two points? Journal of Physics A: Mathematical and Theoretical, 40(47):14099–14116.
Wiener, H. (1947). Structural determination of paraffin boiling points. Journal of the American Chemical Society, 69(1):17–20.
Yarahmadi, Z., Ashrafi, A.R. and Moradi, S. (2012). Extremal polyomino chains with respect to Zagreb indices. Applied Mathematics Letters, 25(2):166–171.

Articles in Press, Corrected Proof
Available Online from 21 November 2026
  • Receive Date: 09 August 2026
  • Revise Date: 15 October 2026
  • Accept Date: 31 October 2026
  • First Publish Date: 21 November 2026
  • Publish Date: 21 November 2026