Extremal two-terminal reliability of directed polyomino-chain networks

Document Type : Original Scientific Paper

Authors

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

Abstract

We study the two-terminal reliability of directed polyomino-chain‎ ‎networks whose successive squares are attached by either linear or‎ ‎kink extensions‎. ‎The input and output interfaces are connected to‎ ‎the terminals by perfectly reliable links‎, ‎whereas all remaining‎ ‎links operate independently with the same probability‎. ‎Each network is encoded by a binary attachment word‎, ‎with‎ ‎0 and 1 representing linear and kink attachments‎, ‎respectively‎. ‎Starting from the finite-state transfer-matrix formulation of the‎ ‎model‎, ‎we establish an exact five-dimensional invariant reduction of‎ ‎the boundary-state dynamics‎. ‎The two reduced transition matrices‎ ‎corresponding to linear and kink extensions differ by a rank-one‎ ‎matrix‎. ‎Combining this fact with a reversal symmetry of directed‎ ‎polyomino chains‎, ‎we prove that replacing any linear attachment by a‎ ‎kink attachment strictly increases the two-terminal reliability‎. ‎More precisely‎, ‎if two attachment words satisfy the coordinatewise‎ ‎order η≼ζ  and η≠ζ‎, ‎then‎ Rη(r)<Rζ(r) ‎for 0<r<1. ‎Consequently‎, ‎within the recursively generated two-terminal network‎ ‎family with some fixed number of squares and the specified‎ ‎input/output interfaces‎, ‎the all-linear chain is the unique ‎‎‎‎minimizer and the all-kink chain is the unique maximizer of‎ ‎two-terminal reliability‎. ‎The result provides an exact extremal‎ ‎characterization for this explicitly defined family of planar‎ ‎communication networks; no ordering is claimed for arbitrary‎ ‎polyomino-chain networks or different terminal placements.

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.
Azami, L. and Jafari Rad, N. (2026). Two-terminal reliability of Markov-dependent directed polyomino-chain networks and its relation to the Gutman index. Unpublished manuscript under revision.
Ball, M.O. (1986). Computational complexity of network reliability analysis: an overview. IEEE Transactions on Reliability, 35(3):230–239.
Bertrand, H., Goff, O., Graves, C. and Sun, M. (2018). On uniformly most reliable two-terminal graphs. Networks, 72(2):200–216.
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.
Gong, S.-C. and Lin, L. (2024). On the construction of locally most reliable two-terminal graphs. Discrete Applied Mathematics, 356:393–402.
Gutman, I. (1994). Selected properties of the Schultz molecular topological index. Journal of Chemical Information and Computer Sciences, 34(5):1087–1089.
Montes-y-Morales, M., Sigarreta, S. and Cruz-Suárez, H. (2026). Maximum augmented Zagreb index on polyomino chains. Applied Mathematics and Computation, 519:129929.
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.
Xie, S., Zhao, H. and Yin, J. (2021). Nonexistence of uniformly most reliable two-terminal graphs. Theoretical Computer Science, 892:279–288.
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 20 November 2026
  • Receive Date: 21 July 2026
  • Revise Date: 27 October 2026
  • Accept Date: 03 November 2026
  • First Publish Date: 20 November 2026
  • Publish Date: 20 November 2026