Some Extremal Problems Of Polyomino Chains

Combinatorial problem known as cell-growth problem which comes from ananalogy with the growth of animals can be presented as follows: starting froma single specified regular polygonal shape(say a cell), grows step by step in theplane by adding at each step a new cell of the same shape to its periphery suchthat there is at least one coincided side. If the basic shape is a square, the animalsare called the polyominoes . Polyominoes have a long history, going to the start ofthe 20th century. The mathematical research about polyominoes focuses mainlyon problems: tiling with polyominoes , polyominoes enumerations, matchingscounting, ordering polyominoes according to some parameters, etc. So far, manyresults have been achieved on these aspects. A polyomino is also a geometricplane figure made of the union of finitely many edge-connected squares from theregular square lattice. In statistical mechanics, the enumeration of independentsets of m×n square lattices and m×n hexagonal lattices are known as hardsquare problem and hard hexagon problem, respectively.In this paper we will consider some extremal problems concerning k-matchingsand k-independent sets and other parameters of a special kind of square lattice,the polyomino chain. Denote by Tn the set of polyomino chains with n squares.For any Tn∈Tn, denote by m_k(T_n) and i_k(T_n) the number of k-matchingsand k-independent sets of Tn, respectively. In this paper, we show that forany polyomino chain Tn∈Tn and any k≥0, mk(L_n)≥m_k(T_n)≥mk(Z_n)and i_k(L_n)≤i_k(T_n)≤i_k(Z_n), with the left equalities holding for all k only ifTn = Ln, and the right equalities holding for all k only if Tn = Zn, where Lnand Zn are the linear polyomino chain and the zig-zag polyomino chain, respec-tively. At last the upper and lower bounds of the Hosoya index( k m_k(T_n)) andMerrifield-Simmons index( k i_k(T_n)) of polyomino chains and their recursionsare given, respectively.