ZZ Polynomial of Regular m-tier Benzenoid Strips as Extended Strict Order Polynomials of Associated Posets Part 1. Proof of Equivalence

In Part 1 of the current series of papers, we demonstrate the equivalence between the Zhang-Zhang polynomial ZZ(S, x) of a Kekuléan regular m-tier strip S of length n and the extended strict order polynomial E^◦_S(n, x + 1) of a certain partially ordered set (poset) S associated with S. The discovered equivalence is a consequence of the one-to-one correspondence between the set {K} of Kekulé structures of S and the set {µ : S ⊃ A → [ n ]} of strictly order-preserving maps from the induced subposets of S to the interval [ n ]. As a result, the problems of determining the Zhang-Zhang polynomial of S and of generating the complete set of Clar covers of S reduce to the problem of constructing the set L(S) of linear extensions of the corresponding poset S and studying their basic properties. In particular, the Zhang-Zhang polynomial of S can be written in a compact form as where des(w) and fix_S(w) denote the number of descents and the number of fixed labels, respectively, in the linear extension w ∈ L(S). A practical guide and a four-step, completely automatable algorithm for computing E^◦_S(n, x + 1) of an arbitrary strip S, followed by a complete account of ZZ polynomials for all regular m-tier benzenoid strips S with m = 1–6 and arbitrary n computed using the discovered equivalence between ZZ(S, x) and E^◦_S(n, x + 1), are presented in Parts 2 and 3, respectively, of the current series of papers. We would like to stress that the pursued by us approach is unprecedented in the existing literature on chemical graph theory and therefore it seems to deserve particular attention of the community, despite of its quite difficult exposition and connection to advanced concepts in order theory.