Extending Extremal Polygonal Arrays for the Merrifield-Simmons Index

Abstract

Polygonal array graphs have been widely investigated, and they represent a relevant area of interest in mathematical chemistry because they have been used to study intrinsic properties of molecular graphs. For example, to determine the Merrifield-Simmons index of a polygonal array $A_n$ that is the number of independent sets of that graph, denoted as $i(A_n)$.

In this paper we consider the problem of extending an initial polygonal array $A_n$ adding a new polygon p to form $A_{n+1}$, for minimizing or maximizing the Merrifield-Simmons index $i(A_{n+1}) = i(A_n \cup p)$. Our method does not require to compute $i(A_n)$ or $i(A_n \cup p)$, explicitly.

1 Introduction

Counting problems are not only mathematically interesting, but also they arise in many applications. Regarding hard counting problems, the computation of the number of independent sets of a graph G, denoted as i(G), has been a key in determining the frontier between efficient and intractable counting problems.

Polygonal array graphs have been widely investigated, and they represent a relevant area of interest in mathematical chemistry because they have been used to study intrinsic properties of molecular graphs. In addition, it is also of great importance to recognize substructures of those compounds and learn messages from the graphic model by clear elucidation of their structures and properties [6].

There are several works analyzing extremal values for the number of independent sets (known in mathematical chemistry as the Merrifield-Simmons index) on chain graphs [6, 7]. Merrifield and Simmons showed the correlation between i(G) and boiling points on polygonal chain graphs that represent chemical molecules. This index is a typical example of an invariant graph used in mathematical chemistry for quantifying relevant details of molecular structures.

In 1993, Gutman discussed the extremal hexagonal chains according to three topological invariants: Hosoya index, largest eigenvalue and Merrified-Simmons index. His work greatly stimulated the study of extremal polygonal chains.

On his seminal paper [3], Gutman showed extremal linear chains for Merrifield index in the particular case of hexagonal chains. He conjectured that the chain with the smallest Merrifield-Simmons index is unique and it corresponds to the zig-zag polyphenegraph.

L.Z. Zhang et al. [4, 5] showed Gutman’s conjecture. They showed that the minimum value for the Merrifield-Simmons index is achieved by the zig-zag polyphenegraph. Later on, Cao et al. [2] showed extremal poligonal chains for k-matchings (Hosoya index), considering the topology of polygonal arrays that provide maximum as well as minimum values for the Hosoya index. Their demonstrations are based on the use of the Z-polynomial (Z-counting polynomial).

The previous mentioned works are concerned to hexagonal chains, or to the Hosoya index. We consider in this paper, results for the Merrifield-Simmon index for any kind of polygonal arrays. We consider the problem of extending a polygonal array A by adding a new polygon p, preserving the structure of polygonal arrays and such that $i(A \cup p)$ is maximum. Instead of computing the Z-polynomial for the Merrifield-Simmon index as Cao et al. [2] suggested, our proofs are based on properties that are derived from the product between Fibonacci’s numbers with complementary indexes values. In fact, our method does not require compute i(G) explicity, and it can be adapted to compute other intrinsic properties on molecular graphs.

2 Polygonal Chains

Let $G=(V,E)$ be a molecular graph. Denote by n(G, k) the number of ways in which k mutually independent vertices can be selected in G. By definition, $n(G, 0) = 1$ and $n(G, 1) = |V(G)|$, for all graph G. Furthermore, $i(G) = \sum _{k\ge 0} n(G,k)$ is the Merrifield-Simmons index of G, that is, exactly the number of independent sets of G.

A polygonal chain is a graph $P_{k,t}$ obtained by identifying a finite number of t congruent regular polygons such that each basic polygon, except the first and the last one, is adjacent to exactly two basic polygons. When each polygon in $P_{k,t}$ has the same number of k nodes, then $P_{k,t}$ becomes a linear array of t k-gons. A special class of polygonal chains is the class of hexagonal chains, which are chains formed by n 6-gons. Hexagonal systems play an important role in mathematical chemistry as they are natural representations of catacondensed benzenoid hydrocarbons.

The propensity of carbon atoms to form compounds, made of hexagonal arrays fused along the edges gives a relevant importance to the study of chemical properties of benzenoid hydrocarbons. Those graphs have been widely investigated and represent a relevant area of interest in mathematical chemistry, since it is used for quantifying relevant details of the molecular structure of the benzenoid hydrocarbons [1, 6].

Let $H_n = h_1 h_2 \cdots h_n$ be a polygonal chain with n basic polygons, where each $h_i$ and $h_{i+1}$ have exactly one common edge $e_i, i = 1, 2, \ldots , n - 1$. A polygonal chain with at least two polygons has two end-polygons, $h_1$ and $h_{n}$, while $h_2, \ldots , h_{n-1}$ are the internal polygons of the chain. In a polygonal chain, each vertex has degree either 2 or 3. The vertices of degree 3 are exactly the end points of the common edges between two consecutive polygons.

The distance $d_G(x; y)$ from a vertex x to another vertex y is the minimum number of edges in an $x-y$ path of G. Similarly, we define the distance between two edges $e_1, e_2$ on the graph G as the minimum number of edges in an $e_1-e_2$ path of G.

Let $H_n$ be a polygonal chain with n basic polygons joined by one common edge between two consecutive basic polygons. If for each pair of consecutive joining edges $e_i$ and $e_{i+1}$ of the polygonal chain it holds that $d_{H_n}(e_i,e_{i+1}) = 2$ then $H_n$ is known as a linear polygonal chain ($L_n$), and if $d_{H_n}(e_i,e_{i+1}) = 1$ for each pair of consecutive common edges, then $H_n$ is known as a zig-zag polygonal chain ($Z_n$), see Fig. 1 for an example.

In recent years, several works have been done for determining the extremal graphs corresponding to the Hosoya and Merrifield-Simmons indexes [2, 6, 7]. For many graph classes that have been studied so far, the graph that minimizes the Merrifield-Simmons index is also the one that maximizes the Hosoya index, and vice versa, although its relation is still not totally understood.

Fig. 1.

Example of a zig-zag octagonal chain

3 Fibonacci Properties to Compute Indices of Polygonal Chains

It is known that for any simple path $P_n$ of size n ($P_n$ has n vertices), $P_n$ fulfills $i(P_n) = F_{n+2}$, where $F_n$ is the nth-Fibonacci number with initial values $F_0 = 0, F_1 = 1$.

Let us consider an isolated vertex as a linear path of size 1, since in this way $i(P_1) = F_3 = 2$. Thus, the size of any simple path is the number of vertices in it. Let $k > 0$ be a constant integer and let $P_i$ and $P_j$ be two disjointed simple paths, such that $i + j = k$. It is known that $i(P_i \cdot P_j) = i(P_i) \cdot i(P_j)=F_{i+2} \cdot F_{j+2}$. We want to determine for which pair (i, j), $i, j \ge 2$, the value of $i(P_i) \cdot i(P_j)$ is maximum when $j+i=k$, for any $k>0$ constant.

We apply Binet’s formula to state the computation of Fibonnaci numbers, i.e. $F_{t}=\frac{a^{t}-b^{t}}{a-b}$, where $a=\left( \frac{1+\sqrt{5}}{2}\right)$ and $b=\left( \frac{1-\sqrt{5}}{2}\right)$ are roots of the polynomial $r^{2}-r-1=0$. Furthermore, $a+b=1$ and $ab=-1$.

Let us define the sequence $\beta _{t,s}$, with $t \ge 1$ and $t \ge s \ge 1$ as follows

$$\begin{aligned} \beta _{t,s}= & {} F_{s}F_{t-s} \end{aligned}$$

(1)

We firstly show that the sequence $\beta _{t,s}$ becomes symmetric when $s>\left\lfloor \frac{t}{2}\right\rfloor$,

Lemma 1

For all j, such that $1\le j\le \left\lfloor \frac{t}{2}\right\rfloor -2$, the sequence $\beta _{t,s}$ satisfies the following

• 1. $\beta _{t,\left\lfloor \frac{t}{2}\right\rfloor -j} = \beta _{t,\left\lfloor \frac{t}{2}\right\rfloor +j}$ if t is even,

• 2. $\beta _{t,\left\lfloor \frac{t}{2}\right\rfloor -j} = \beta _{t,\left\lfloor \frac{t}{2}\right\rfloor +j+1}$ if t is odd,

Proof

From Eq. (1) we have

$$\begin{aligned} (a-b)^{2}\beta _{t,\left\lfloor \frac{t}{2}\right\rfloor -j}= & {} \left( a^{\left\lfloor \frac{t}{2}\right\rfloor -j}-b^{\left\lfloor \frac{t}{2}\right\rfloor -j}\right) \left( a^{t-\left\lfloor \frac{t}{2}\right\rfloor +j}-b^{t-\left\lfloor \frac{t}{2}\right\rfloor +j}\right) \\= & {} a^{t}-a^{\left\lfloor \frac{t}{2}\right\rfloor -j}b^{t-\left\lfloor \frac{t}{2}\right\rfloor +j}-a^{t-\left\lfloor \frac{t}{2}\right\rfloor +j}b^{\left\lfloor \frac{t}{2}\right\rfloor -j}+b^{t} \end{aligned}$$

$$\begin{aligned} (a-b)^{2}\beta _{t,\left\lfloor \frac{t}{2}\right\rfloor +j}= & {} a^{t}-a^{\left\lfloor \frac{t}{2}\right\rfloor +j}b^{t-\left\lfloor \frac{t}{2}\right\rfloor -j}-a^{t-\left\lfloor \frac{t}{2}\right\rfloor -j}b^{\left\lfloor \frac{t}{2}\right\rfloor +j}+b^{t} \end{aligned}$$

Thus,

$$\begin{aligned} (a-b)^{2}\beta _{t,\left\lfloor \frac{t}{2}\right\rfloor -j}= & {} a^{t}-a^{\left\lfloor \frac{t}{2}\right\rfloor -j}b^{t-\left\lfloor \frac{t}{2}\right\rfloor +j}-a^{t-\left\lfloor \frac{t}{2}\right\rfloor +j}b^{\left\lfloor \frac{t}{2}\right\rfloor -j}+b^{t}\\&-\,a^{\left\lfloor \frac{t}{2}\right\rfloor +j}b^{t-\left\lfloor \frac{t}{2}\right\rfloor -j}-a^{t-\left\lfloor \frac{t}{2}\right\rfloor -j}b^{\left\lfloor \frac{t}{2}\right\rfloor +j}\\&a^{\left\lfloor \frac{t}{2}\right\rfloor +j}b^{t-\left\lfloor \frac{t}{2}\right\rfloor -j}+a^{t-\left\lfloor \frac{t}{2}\right\rfloor -j}b^{\left\lfloor \frac{t}{2}\right\rfloor +j}\\= & {} (a-b)^{2}\beta _{t,\left\lfloor \frac{t}{2}\right\rfloor +j}+a^{\left\lfloor \frac{t}{2}\right\rfloor +j}b^{t-\left\lfloor \frac{t}{2}\right\rfloor -j}+a^{t-\left\lfloor \frac{t}{2}\right\rfloor -j}b^{\left\lfloor \frac{t}{2}\right\rfloor +j}\\&-\,a^{\left\lfloor \frac{t}{2}\right\rfloor -j}b^{t-\left\lfloor \frac{t}{2}\right\rfloor +j}-a^{t-\left\lfloor \frac{t}{2}\right\rfloor +j}b^{\left\lfloor \frac{t}{2}\right\rfloor -j}\\= & {} (a-b)^{2}\beta _{t,\left\lfloor \frac{t}{2}\right\rfloor +j}+a^{\left\lfloor \frac{t}{2}\right\rfloor -j}b^{t-\left\lfloor \frac{t}{2}\right\rfloor -j}\left[ a^{2j}-b^{2j}\right] \\&+\,a^{t-\left\lfloor \frac{t}{2}\right\rfloor -j}b^{\left\lfloor \frac{t}{2}\right\rfloor -j}\left[ b^{2j}-a^{2j}\right] \\= & {} (a-b)^{2}\beta _{t,\left\lfloor \frac{t}{2}\right\rfloor +j}+\left( a^{2j}-b^{2j}\right) \left( a^{\left\lfloor \frac{t}{2}\right\rfloor -j}b^{t-\left\lfloor \frac{t}{2}\right\rfloor -j}-a^{t-\left\lfloor \frac{t}{2}\right\rfloor -j}b^{\left\lfloor \frac{t}{2}\right\rfloor -j}\right) \\= & {} (a-b)^{2}\beta _{t,\left\lfloor \frac{t}{2}\right\rfloor +j}+\frac{\left( a^{2j}-b^{2j}\right) a^{2\left\lfloor \frac{t}{2}\right\rfloor }b^{2\left\lfloor \frac{t}{2}\right\rfloor }}{a^{\left\lfloor \frac{t}{2}\right\rfloor +j}b^{\left\lfloor \frac{t}{2}\right\rfloor +j}}\left( b^{t-2\left\lfloor \frac{t}{2}\right\rfloor }-a^{t-2\left\lfloor \frac{t}{2}\right\rfloor }\right) \end{aligned}$$

but t is even, that is $t=2r$ for some $r\in {\mathbb {Z}}$ and $t-2\left\lfloor \frac{t}{2}\right\rfloor =0$. Therefore, $b^{t-2\left\lfloor \frac{t}{2}\right\rfloor }-a^{t-2\left\lfloor \frac{t}{2}\right\rfloor }=b^{0}-a^{0}=0$.    $\square$

Thus, we might assume that $2\le s\le \left\lfloor \frac{t}{2}\right\rfloor$ then $s-1<t-s$. Now, we show that if s is even in $\beta _{t,s}$ then the sequence is increasing.

Lemma 2

The sequence $\beta _{t,2}$, $\beta _{t,4},$ $\beta _{t,6},$... that is $\left\{ \beta _{t,2p}\right\} _{t,p}$ satisfies $\beta _{t,2p} < \beta _{t,2(p+1)}$ for every $p\in \left\{ 1,2,...,\left\lfloor \frac{t}{4}\right\rfloor \right\}$ and all t.

Proof

We have,

$$\begin{aligned} \beta _{t,2p}= & {} \frac{\left( a^{2p}-b^{2p}\right) \left( a^{t-2p}-b^{t-2p}\right) }{\left( a-b\right) ^{2}}\\= & {} \frac{a^{t}-a^{2p}b^{t-2p}-a^{t-2p}b^{2p}+b^{t}}{(a-b)^{2}}\\ \beta _{t,2(p+1)}= & {} \frac{\left( a^{2p+2}-b^{2p+2}\right) \left( a^{t-2p-2}-b^{t-2p-2}\right) }{\left( a-b\right) ^{2}} \end{aligned}$$

$$\begin{aligned} \beta _{t,2p+2}= & {} \frac{a^{t}-a^{2p+2}b^{t-2p-2}-a^{t-2p-2}b^{2p+2}+b^{t}}{(a-b)^{2}}\\ (a-b)^{2}\beta _{t,2p+2}= & {} a^{t}-a^{2p+2}b^{t-2p-2}-a^{t-2p-2}b^{2p+2}+b^{t}\\&-\,a^{2p}b^{t-2p}-a^{t-2p}b^{2p}\\&+\,a^{2p}b^{t-2p}+a^{t-2p}b^{2p}\\= & {} (a-b)^{2}\beta _{t,2p}+a^{2p}b^{t-2p}+a^{t-2p}b^{2p}\\&-\,a^{2p+2}b^{t-2p-2}-a^{t-2p-2}b^{2p+2}\\= & {} (a-b)^{2}\beta _{t,2p}+\left( 1-a^{2}b^{-2}\right) a^{2p}b^{t-2p}\\&+\,a^{t-2p}b^{2p}(1-a^{-2}b^{2})\\= & {} (a-b)^{2}\beta _{t,2p}+\left( b^{2}-a^{2}\right) a^{2p+2}b^{t-2p}\\&+\left( a^{2}-b^{2}\right) a^{t-2p}b^{2p+2}\\ \beta _{t,2(p+1)}= & {} \beta _{t,2p}+\frac{k}{(a-b)}\left[ a^{t-2p}b^{2p+2}-a^{2p+2}b^{t-2p}\right] \\= & {} \beta _{t,2p}+ka^{2p+2}b^{2p+2}\left[ a^{t-4p-2}-b^{t-4p-2}\right] \\= & {} \beta _{t,2p}+k\frac{a^{t-4p-2}-b^{t-4p-2}}{a-b}\\= & {} \beta _{t,2p}+kF_{t-2(2p+1)} \end{aligned}$$

and as $k, F_{t-2(2p+1)} >0$, the proof is complete.    $\square$

On the other hand, if s is odd in $\beta _{t,s}$ then the sequence is decreasing, as the following lemma shows.

Lemma 3

The sequence $\left\{ \beta _{t,2p+1}\right\} _{t,p}$ satisfies $\beta _{t,2p+1} > \beta _{t,2p+3}$ for every $p\in \left\{ 0,2,...,\left\lfloor \frac{t}{4}\right\rfloor -1\right\}$ and all t.

Proof

$$\begin{aligned} \beta _{t,2p+1}= & {} \frac{\left( a^{2p+1}-b^{2p+1}\right) \left( a^{t-2p-1)}-b^{t-2p-1}\right) }{\left( a-b\right) ^{2}}\\= & {} \frac{a^{t}-a^{2p+1}b^{t-2p-1}-a^{t-2p-1}b^{2p+1}+b^{t}}{(a-b)^{2}} \end{aligned}$$

and

$$\begin{aligned} \beta _{t,2p+3}= & {} \frac{\left( a^{2p+3}-b^{2p+3}\right) \left( a^{t-2p-3)}-b^{t-2p-3}\right) }{\left( a-b\right) ^{2}}\\ (a-b)^{2}\beta _{t,2p+3}= & {} a^{t}-a^{2p+3}b^{t-2p-3}-a^{t-2p-3}b^{2p+3}+b^{t}\\&-\,a^{2p+1}b^{t-2p-1}-a^{t-2p-1}b^{2p+1}\\&+\,a^{2p+1}b^{t-2p-1}+a^{t-2p-1}b^{2p+1}\\ \end{aligned}$$

$$\begin{aligned}= & {} (a-b)^{2}\beta _{t,2p+1}+a^{2p+1}b^{t-2p-1}+a^{t-2p-1}b^{2p+1}\\&-\,a^{2p+3}b^{t-2p-3}-a^{t-2p-3}b^{2p+3}\\= & {} (a-b)^{2}\beta _{t,2p+1}+a^{2p+1}b^{t-2p-1}+a^{t-2p-1}b^{2p+1}\\&-\,a^{2p+1}b^{t-2p-1}a^{2}b^{-2}-a^{t-2p-1}b^{2p+1}a^{-2}b^{2}\\= & {} (a-b)^{2}\beta _{t,2p+1}+a^{2p+1}b^{t-2p-1}(1-a^{2}b^{-2})\\&+\,a^{t-2p-1}b^{2p+1}(1-a^{-2}b^{2}) \end{aligned}$$

Using the fact that $ab=-1$ then $a^{2}b^{2}=1$, and

$$\begin{aligned} \beta _{t,2p+3}= & {} \beta _{t,2p+1}+\frac{(a^{2}-b^{2})a^{t-2p-1}b^{2p+3}-(a^{2}-b^{2})a^{2p+3}b^{t-2p-1}}{(a-b)^{2}}\\= & {} \beta _{t,2p+1}+k\frac{a^{t-2p-1}b^{2p+3}-a^{2p+3}b^{t-2p-1}}{a-b}\\= & {} \beta _{t,2p+1}+k(ab)^{2p+3}\frac{a^{t-4(p+1)}-b^{t-a(p+1)}}{a-b}\\= & {} \beta _{t,2p+1}-kF_{k-t-4(p+1)}\\ \end{aligned}$$

and as $k, F_{k-t-4(p+1)} >0$, the proof is complete.    $\square$

The main Theorem of the section is the following:

Theorem 1

For any integers $t, s, k \ge 1$,

• 1. $\min _{s}\left\{ F_{s}F_{t-s}\right\} = F_{2}F_{t-2}=F_{t-2}$

• 2. $\max _{s}\left\{ F_{s}F_{t-s}\right\} = F_{1}F_{t-1}=F_{t-1}$

Proof

It is enough to proof that $\beta _{t,\left\lfloor \frac{t}{2}\right\rfloor } < \beta _{t,\left\lfloor \frac{t}{2}\right\rfloor -1}$ which can be easily done by an algebraic manipulation and the rest of the proof follows from above lemmas.    $\square$

4 Extremal Topologies on Polygonal Graphs

In this section, we show how the previous results about the product of Fibonacci numbers can be used for determining the structure of polygonal arrays G such that when adding a new polygon, maximize or minimize i(G).

Let h be a polygon with n sides. Let $P_i$ and $P_j$ be two different linear paths of sizes i and j, respectively, such that $i + j =k$ becomes a constant. Let G be the resulting graph formed by joining $P_i$ and $P_j$ to the end-nodes of any edge $e=\{x,y\} \in E(h)$, as it is illustrated in Fig. 2. Notice that e can be any edge of the polygon since in fact, the initial polygon is a cycle and all of its edges are indistinguishable.

We show that i(G) is maximum under the restriction $|P_i| + |P_j| = k$ when $i=2$ ($P_i$ has exactly two vertex and only one edge) and $j=k-2$ (a path of $k-2$ vertices).

Fig. 2.

A base graph

Lemma 4

Let h be a polygon of n sides and $e=\{x,y\}\in E(h)$. Let $P_{i}=\{x,x_1,\ldots , x_{i-1}\}$ and $P_{j}=\{y,y_1,\ldots , y_{j-1}\}$ be two disjointed paths such that $V(P_i)\cap V(h)=\{x\}$, $V(P_j)\cap V(h)=\{y\}$ and $i+j=k$. If $G=h\cup P_i\cup P_j$ then the maximum for i(G) is achieved when $i=2$ and $j=k-2$.

Proof

Applying the division edge rule on the edge $e=\{x,y\}$, we obtain that $i(G) = i(G-e) - i(G-(N[x] \cup N[y]))$. Notice that $(G-e)$ is a linear path of size $n+(i-1)+(j-1)= n+ k-2$; therefore, $i(G-e) = F_{n+k}$. Furthermore, $i(G-e)$ is invariant with respect to the selected position of the edge $e \in E(h)$.

On the other hand, $(G-(N[x] \cup N[y]))$ is formed by three disjointed paths: $P_{i-2}, P_{j-2}$ and the path that results from eliminating e and its two adjacent edges from h. Let us denote this last path as $P_{n-4}$. Then, $i(G-(N[x] \cup N[y]))) = F_{n-2} \cdot F_{i} \cdot F_{j}$. In fact, the result of this product does not depend on the initial position of e in h because the three resulting paths will have same sizes independently of the position of e in h.

Then, maximizing i(G) is equivalent to minimizing $F_{i} \cdot F_{j}$ since these are the unique sizes on i and j that can vary under the restriction $i + j =k$. According to Theorem 1, $F_{i} \cdot F_{j}$ has a minimum value when $F_{i}= F_2$ and $F_j=F_{k-2}$ which means that the resulting path $P_{i-2}$ after removing N[x] from G should be empty and the resulting path $P_{j-2}$ after removing N[y] from G should have $k-4$ vertices.    $\square$

Lemma 5

Let h be a polygon of n sides and $e=\{x,y\}\in E(h)$. Let $P_{i}=\{x,x_1,\ldots , x_{i-1}\}$ and $P_{j}=\{y,y_1,\ldots , y_{j-1}\}$ be two disjointed paths such that $V(P_i)\cap V(h)=\{x\}$, $V(P_j)\cap V(h)=\{y\}$ and $i+j=k$. If $G=h\cup P_i\cup P_j$ then the minimum for i(G) is achieved when $i=1$ and $j=k-1$.

Proof

Similar to Lemma 4.    $\square$

Furthermore, the maximum and minimum values for i(G) are achieved independently of the number of edges in the polygon h. Consequently, our results are fulfilled for any polygon joined with two disjointed paths in the end-nodes of one of its edges. We show in Fig. 3 the extremal topologies for i(G) for the class of graphs: $G=h\cup P_i\cup P_j$.

Fig. 3.

Extremal topologies for i(G), $G=h\cup P_i \cup P_j$.

Let $A_n: h_1, \ldots , h_n, n \ge 1$ be a polygonal array and p a new polygon of k edges. We denote as $e_i$ the common edge between the polygon $h_{i}$ and $h_{i+1}$. We want to extend $A_n$ to $A_{n+1}$ joining p to $A_n$ in such way that $i(A_{n+1})$ is either minimum or maximum into the set of possible edges $e \in E(h_n)$ to be selected for joining it with p.

Let us, enumerate the edges of $h_n$ as $b_0, b_1, \ldots , b_{k-1}$, where $b_0$ is the common edge between $h_n$ and $h_{n-1}$ and the numeration is according to the clockwise direction. We also consider that $h_n$ has more than 5 edges. We must select $e \in E(h_n)$ such that $i(A_n \cup p)$ is maximum into the set of possible selections of edges of $h_n$. For example, e can not be anyone from $b_0, b_1, b_{k-1}$ because if we join p to any one of those edges, then $A_n \cup p$ losses the structure of polygonal arrays.

Theorem 2

Let $A_n$ be a polygonal array whose last polygon $h_n$ has k edges and p be a polygon. Let $b_0, b_1, \ldots , b_{k-1}$ be the edges of $h_n$ such that $b_0$ is the common edge between $h_n$ and $h_{n-1}$ and the numeration is clockwise. If $A_{n+1}=A_{n}\cup p$ is a polygonal array then $\max \{i(A_{n+1})\}$ is achieved when p is joined to $A_n$ at $b_3$, that is a distance 2 from the common edge between $h_{n-1}$ and $h_n$.

Proof

Applying the division edge rule on $e=\{x,y\} \in E(h_n)$, we obtain

$$\begin{aligned} i(A_{n+1}) = i(A_{n+1} - e) - i(A_{n+1} -(N[x] \cup N[y])) \end{aligned}$$

(2)

The term $i(A_{n+1} - e)$ is invariant from e because its values does not depend on the selected position of e to join p to $A_n$.

$A_{n+1} -(N[x] \cup N[y])$ is a graph formed by two connected components: a linear path $P_{k-5}$ with $k-5$ edges and then $i(P_{k-5}) = F_{k-2}$ that is an invariant value independent to the position of $e \in E(h_n)$. And the other connected component, denoted by G, that is a polygonal array where one of the edges in the last polygon is joined to two disjointed paths $P_i$ and $P_j$. Then, $i(A_{n+1} -(N[x] \cup N[y])) = i(G) * F_{k-2}$, and that value is minimum if in G is preserved a maximum number of edges from $A_n$. It means that $(N[x] \cup N[y])$ contains a minimum number of edges from p and $h_n$. As $\delta (x) = \delta (y)=3$ then the minimum number of edges to be contained in $(N[x] \cup N[y])$ is 7, meaning that e has to be a distance 2 from the common edge $e_{n-1}$ between $h_{n-1}$ and $h_n$, and also $|P_i|=0$ and $|P_j|=k-6$, in order to maximize $i(A_{n+1})$.    $\square$

For the minimum Merrifield-Simmon index, it is not a sufficient condition to state that p is joined to $A_n$ to a distance one from the common edge between $h_{n-1}$ and $h_n$ since two cases have to be considered, Fig. 4 shows the two possible configurations in a octahedral polygonal array.

Fig. 4.

In the octahedral polygonal array on the left the shortest path for visiting $e_1,e_2,e_3$ is a path, while it is a tree in the octahedral polygonal array on the right

Fig. 5.

Application of the edge division rule to the graph Fig. 4a to compute the Merrifield-Simmon index

Applying the edge division rule to $e_3$, the decomposition to compute the Merrifield-Simmon index on the graphs Fig. 4a and b are shown in Figs. 5 and 6, respectively. The left graphs of Figs. 5a and 6a are invariant, similar to the right graphs (5c and 6c) of the same figures. By Lemma 5, the graph of Fig. 6b has minimum Merrifield-Simmon index than the graph of Fig. 5b hence the polygonal array has minimum Merrifield-Simmon index when the shortest path of $e_1,e_2$ and $e_3$ is a path.

Fig. 6.

Application of the edge division rule to the graph Fig. 3b to compute the Merrifield-Simmon index

Theorem 3

Let $A_n$ be a polygonal array whose last polygon $h_n$ has k edges and p be a polygon. Let $e_i$ be the edge joining $h_{i}$ to $h_{i+1}$. If $A_{n+1}=A_{n}\cup p$ is a polygonal array then $\min \{i(A_{n+1})\}$ is achieved when p is joined to $A_n$ at distance 1 from $e_n$ and $e_{n-1}, e_{n}, e_{p}$ forms a path.

Proof

Similar to the proof of Theorem 2.    $\square$

5 Conclusions

We have shown how properties of Fibonacci numbers can be used for the computation of Merrifield-Simmon index. We have shown that, as expected, when adding a new polygon at distance 2, the maximum number of independent sets is obtained among all the possible combinations. Dually, the minimal number of independent sets is obtained when the distance is 1 and a path is built from the joining edges. Our method does not require to compute explicitly, the number of independent sets of the involved graphs.