ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 7 (2014) 1-12
Compression ratio of Wiener index in 2-d rectangular and polygonal lattices
Jelena Sedlar *
Faculty of civil engeneering, architecture and geodesy Matice hrvatske 15, HR-21000 Split, Croatia

Damir Vukicevic
Faculty of Science, University of Split, Nikole Tesle 12, HR-21000 Split, Croatia
Franco Cataldo , Ottorino Ori
Actinium Chemical Research, Via Casilina 1626/A, 00133 Rome, Italy
Ante Graovac
Faculty of Science, University of Split, Nikole Tesle 12, HR-21000 Split, Croatia IMC, University of Dubrovnik, Branitelja Dubrovnika 29, HR-20000 Dubrovnik, Croatia
Received 20 October 2011, accepted 31 October 2012, published online 7 January 2013
In this paper, we establish leading coefficient of Wiener index for open and closed 2-dimensional rectangular lattices, for various open and closed polygonal lattices, and for open and closed multidimensional cubes. These results enable us to establish compression ratio of Wiener index when number of rows and columns in the lattice tends to infinity.
Keywords: Graph theory, 2D rectangular and polygonal lattices, Wiener index, Compression ratio. Math. Subj. Class.: 05C12, 92E10
* corresponding author
E-mail addresses: jsedlar@gradst.hr (Jelena Sedlar), vukicevi@pmfst.hr (Damir Vukicevic), franco.cataldo@fastwebnet.it (Franco Cataldo), ottorino.ori@alice.it (Ottorino Ori), graovac@irb.hr (Ante Graovac)
Abstract
©® This work is licensed under http://creativecommons.Org/licenses/by/3.0/
2
Ars Math. Contemp. 7 (2014) 41-54
1	Introduction
Topological indices are very important in chemistry, since they can be used for modeling and prediction of many chemical properties. One of the most famous and the most researched indices is Wiener index. Topological indices are invariants defined on graphs representing various chemical compounds. For example, one such compound is graphene which is represented with hexagonal lattice graph. Also, nanotubes and nanotori received much attention recently, and they are represented with a graph which is rectangle shaped lattice with opposite sides identified.
Recent theoretical investigations point out that the minimization of distance-based graph invariants, namely the Wiener index W [7] and the topological efficiency index p recently introduced [3], provides the fast determination of the subsets of isomers with relative structural stability of a given chemical structure. This method has been applied to important classes of carbon hexagonal systems like fullerenes, graphene with nanocones and graphene. This elegant computational topological approach quickly sieves the most stable C66 cages among 4478 distinct isomers as reported in [8]. Moreover, the same method gives the correct numbers of NMR resonance peaks and relative intensities. The Wiener index has been computed for monodimensional infinite lattices to describe conductibilty features of conjugated polymers [1]. Present article reports about a relevant property - the compression factor [3] - of the topological invariants computed on infinite lattices. For different topological indices, there is quite much recent interest [4-6] in the ratio of the value of the index on open and closed lattices (i.e. nanotubes and nanotori). In this article, we investigate compression ratio of 2-dimensional and multidimensional rectangular lattices, and various 2-dimensional polygonal lattices.
The present paper is organized as follows. In the second section named 'Preliminaries', we introduce some basic notions and notation that will be used throughout the paper. In the third section, we establish the leading coefficient in Wiener index for open and closed 2-dimensional rectangular lattices, which leads us to compression ratio in asymptotic case. In the fourth section, we use the results from the second section to derive the same kind of result for hexagonal and similar lattices. In the fifth section, we establish the limit of compression ratio for d-dimensional rectangular cube. Finally, in the last section named 'Conclusion', we summarize the main results of this paper.
2	Preliminaries
In this paper, we consider only simple connected graphs. We will use the following notation: G for graph, V(G) or just V for its set of vertices, E(G) or just E for its set of edges. With N we will denote number of vertices in a graph. For two vertices u,v e V, we define distance d(u, v) of u and v as the length of shortest path connecting u and v. Given the notion of distance, Wiener index of a graph G is defined [9] as
W(G) = ^ d(u, v).
Here, the pair of vertices u, v is unordered. In some literature, the summation goes over all ordered pairs (u, v) of vertices and then the sum needs to be multiplied by a half. Now, let us introduce some special kinds of graphs that will be of interest to us in this paper, namely
J. Sedlar et al.: Compression ratio of Wiener index in 2-d rectangular and polygonal lattices 3
open and closed lattice graphs. First, let Rn,k be rectangular lattice containing 2n rows and 2kn columns of squares. Lattices R3^ and R3,2 are shown in Figure 1.
Figure 1: Lattices R3,i and R3,2.
Let us denote vertices of Rn,k with integer coordinates (i, j) for i = 0,..., 2nk and j = 0,..., 2n as if the lattice was placed in first quadrant of Cartesian coordinate system. Therefore
V(Rn,k) = {vi,j : i = 0,..., 2nk and j = 0,..., 2n} .
Open lattice is a graph ORn,k obtained from Rn,k by deleting vertices v0,j and vi,0. Closed lattice is a graph CRn,k obtained from Rn,k by identifying vertices v0,j and v2nk,j, and also vertices vi 0 and vi 2n. Therefore, open and closed lattice graphs have the same number of vertices which is
|V (O Rn,k)| = |v (C Rn,k)| =4n2k.
Further, for a fixed integer k let us consider polygons Pk with 4k + 2 vertices. Let Ln,k be rectangle shaped lattice consisting of 2n rows of polygons Pk, with rows containing n and n - 1 polygons alternatively, such that two neighboring polygons from one row share exactly two vertices, while two neighboring polygons from different rows share exactly k + 1 vertices. For k =1, lattice Ln,k is actually hexagonal lattice with 2n rows and n columns of hexagons. Note that lattice Ln,k can be considered as subgraph of rectangular lattice Rn,k assigning to polygons the size of 2k square cells. Therefore, we can use the same vertex notation in Ln,k as in Rn,k. Lattices L3,i and L3,2 for k = 1 and k = 2 are shown in Figure 2. Again, open and closed lattices OLn,k and CLn,k can be obtained as for rectangular lattice. Finally, a d-dimensional rectangular cube Rn is defined in a following manner: set of vertices V(Rn) is defined with
V (Rn) = {(xi,...,xd) : Xi G{0,1,..., n}} ,
and two vertices (x1,..., xd) and (y1,..., yd) are connected with an edge if and only if there is a coordinate j such that xi = yi for every i G {1,..., d} \ {j} , and for j-th coordinate holds |y - Xj | = 1. Open lattice O Rn is a graph obtained from Rn by deleting all vertices that have at least one zero coordinate. Closed lattice C Rn is a graph obtained from Rn by identifying every pair of vertices (x1,..., xd) and (y1,..., yd) such that xi = yi for every i G {1,..., d} \ {j} and for j-th coordinate holds Xj = 0 and yj = n. Obviously, the number of vertices in O Rn and C Rn is the same and it equals nd.
Now, if OG is an open lattice graph and CG its closed version, compression ratio of G is defined [3] as
W (C G)
cr(G)
W(OG) '
4
Ars Math. Contemp. 7 (2014) 41-54
Figure 2: Lattices L3,1 and ¿3,2.
Obviously, Wiener index depends on the size of the lattice i.e. on n and k, and therefore compression ratio depends on them too. Our goal is to establish the limit of compression ratio for Rn,k, Ln<k and Rn when n tends to infinity for a fixed k.
3 Compression ratio of Rn,k
For k = 1 (i.e. for square shaped rectangular lattices), the result cr(Rn,k) = 3 was already obtained in reference [4]. The result f for bidimensional square is the same as the result for monodimensional lattices (polymer chains) obtained in [3]. We will here derive the same result for k > 1, i.e. for some rectangle shaped lattices. Let k be fixed integer. We have following theorems.
Theorem 3.1. For the lattice graph ORn,k, Wiener index W(ORn,k) is a polynomial in n of degree 5 whose leading coefficient equals
16k2 (1 + k). Proof. For vertices vitj and vpq of ORn,k holds
d (vi,j ,vp,q) = \p - i\ + \q - j\ .
Obviously,
2kn 2n 2kn 2n	2kn 2n 2n
W (O Rn,k ) = EEEE d(vi,j , vp,q ) - EEE d(vij ,vi,q ).
i=1 j = 1 p=i q=l	i=1 j = 1 q=j
The second (subtracted) sum does not influence leading term in n, therefore we can neglect it. To avoid absolute value, we can rewrite the first sum as
2kn 2n 2kn 2n	2kn 2n 2kn
W(ORn,k) « 2 EEEE d(vi,j, vp,q) - E E E d(vi,j, vp,j).
i=1 j=1 p=i q=j	i=1 j=1 p=i
Again, the second (subtracted) sum does not influence leading term in n, therefore we can neglect it. Now we have
2kn 2n 2kn 2n
w (O Rn,k)«2 EEEE (p - i + q - j)
i=1 j=1 p=i q=j
and the result then follows by easy calculation.
□
J. Sedlar et al.: Compression ratio of Wiener index in 2-d rectangular and polygonal lattices 5
Theorem 3.2. For the lattice graph CRn,k, Wiener index W(CRn,k) is a polynomial in n of degree 5 whose leading coefficient equals
4k2 (1 + k).
Proof. Obviously, all vertices in C Rn,k have the same sums of distances to all other vertices. Therefore, to obtain W(CRn,k) it is enough to calculate distances from one vertex (vi,i is easiest for calculation) to all other vertices. Since CRn,k is a torus, to do that we will calculate the sum of distances from v1,1 to vpq where 1 < p < kn and 1 < q < n and multiply it by 4. Now, the obtained number should be multiplied by number 2n • 2kn of vertices in the lattice, and then divided by 2 since each distance was counted twice. Therefore we have
kn n
W(CRn,k) « 2 • 2n • 2kn • 4 • ^^ (p - 1 + q - 1),
p=1 q=1
and the result now follows by direct calculation.
□
Corollary 3.3. Holds
3
lim cr(Rn,k) = t.
n—^^o	4
4 Compression ratio of Ln,k
This section is devoted to the exact determination of the compression factors for the 2-dimensional polygonal lattice Ln,k. We start from a numerical example devoted to the case of the graphene lattice. Figure 3 shows the rectangular L3,i portion of this hexagonal system.
Figure 3: View of L3}1 hexagonal lattice with bold vertices common to neighboring polygons along one row, whereas the dotted ones are shared by two neighboring polygons from two different rows.
The numerical determination of invariants W (O G) and W (C G) for this infinite graph is based on the results summarized in Table 1 where, for an increasing number of vertices N, values of both descriptors are listed. The exact polynomial forms are given in Table 1
5	5
for O W and C W with leading terms O W « 2N52 and C W « T^2 respectively, producing
6
Ars Math. Contemp. 7 (2014) 41-54
N	OW = i5 (6N5 - 5N3 - N2 )	C W = 24 (7N 2 - 4N i)
36	3 038	2 232
100	39 666	29 000
196	214 214	156 408
324	753 882	550 152
484	2 057 902	1 501 368
676	4 746 690	3 462 472
900	9 710 998	7 083 000
Table 1: Exact polynomial forms for the Wiener index of the open (O W) and closed (C W) rectangular graphene lattices L„ i with N vertices.
the value cr(Ln<1) = f§ for the compression factor of rectangular graphene. More details about the numerical determination of various topological descriptors of the graphene rectangular lattices are given in [2].
Now, we want to establish the compression ratio of Ln<k. We will use the fact that Ln<k can be considered as the subgraph of Rn,k. Therefore, distances between vertices in Ln<k for some pairs of vertices are equal as in Rn^k, while for some other pairs of vertices are greater than in Rn,k. We will establish for which pairs of vertices the distance is greater in Lnk than in Rni<k, and how much greater. We will not establish the exact value of Wiener index for OLn,k or CLn,k as that would be tedious for all the possible cases, but we will neglect some quantities which do not influence the leading coefficient.
Theorem 4.1. For the lattice graph OLn,k, Wiener index W(OLn,k) is a polynomial in n of degree 5 whose leading coefficient equals
15k2 (7k + 5).
Proof. Since Ln<k is a subgraph of Rn,k that means distances in Ln<k are equal or greater than in Rn k. Therefore
W(OLn,k )= W(ORn,k )+A.
If we establish leading coefficient in A, then by combining that result with Theorem 3.1 we obtain desired result. Therefore, we are interesting in establishing A, i.e. for which pairs of vertices the distance in Ln^k is greater than in Rn^k and how much greater. For a vertex vij lattice Lnkk can be divided into four areas as illustrated with Figure 4. Vertices in areas left and right to vitj have the same distance to vitj in Ln<k as in Rni<k, while the vertices in areas up and down to vij have the greater distance to vij in Ln<k than in Rn,k. For easier calculation, we will approximate zig-zag lines that divide Ln<k into areas with lines
q = qi(p) = j - 1(p - i),
q = q2(p) = j + 1(p - i).
as also illustrated in Figure 4, and we denote upper and lower areas with L^ k and left and right areas with LB k. With such an approximation, we make an error in some vertices near
J. Sedlar et al.: Compression ratio of Wiener index in 2-d rectangular and polygonal lattices 7
Figure 4: Division of lattice Ln,k into areas for a vertex v^-.
the lines, but since number of such vertices is linear in n, that error does not influence the leading term of A and we can neglect it. Now that we established the pairs of vertices for which the distance is greater, we want to establish how much greater. Obviously, the trouble is if we have to go vertically, since some vertical edges are missing now. Therefore, we go vertically as little as we can (the shortest path is illustrated in Figure 4), and for each vertical step the path is k edges longer in Ln,k than in Rn,k. Now, to calculate all these exactly, we have to divide into cases, regarding the position of vi j (since then lines q1 (p) and q2 (p) intersect boundaries in different sides, which influences calculation). The division into cases is illustrated with Figure 5. There are four areas, but upper and lower
Figure 5: Division into cases with respect to the position of vi j in the lattice.
are equal up to symmetry, and also left and right. Again, we will approximate division with lines
j = ji(i) = n - k-(i - kn), j = j2(i) = n + k"(i - kn)
and denote upper and lower areas with L^k and left and right areas with L^k. This approximation again produces an error in calculating W(Ln,k) but not great enough to influence the leading term, therefore we can again neglect it. Before we proceed note that lines we
8
Ars Math. Contemp. 7 (2014) 41-54
introduced can also be expressed as i = n(j), i = i2(j), p = pi(q) andp = p2(q). Now we distinguish two cases.
CASE I: Let vi,j G L^l. For an arbitrary vertex vp, q, we are interested in establishing the difference in d(vi,j, vp,q) between Ln,k and Rnk. The difference is greater than zero only if vp q G LAk. To calculate the difference A, that occurs for pairs of vertices in this case, we have to divide LA k into 4 subareas A1, A2, A3, A4 as illustrated in Figure 6. Now
Figure 6: The division of the area LA k into subareas in the case vi, j G L^l
we have
2n i 2 (j) i q2(p)
A(Ai) = 2 E E EE (q2(p) - q) ■ k,
j=n i=ii (j) p=1 q=1 2n i2(j) 2lnqi(p)
A(A2) = 2 E £ EE (qi(p) - q) ■ k,
j=n i=ii (j) p=i q=1 2n i2(j)	i	2n
A(A3) = 2 £ E E E (q - q1(p)) ■ k,
j=n i=ii (j) p=pi (2n) q=qi (p) 2n i2(j) p2 (2n) 2n
A(A4) = 2£ E E E (q - q2(p)) ■ k.
j=n i=ii (j) p=i q=q2(p)
Therefore A1 = A(A1) + A(A2) + A(As) + A(A4) and by direct calculation we establish that A1 is a polynomial in n of degree 5 with leading coefficient being 14 k3.
CASE II: Let vi,j G L^l. Again, the difference d(vi,j ,vp q) is greater than zero only if vp,q G L^. Again, we divide L^ into four areas A1,..., A4 as shown in Figure 7. Now, we calculate
J. Sedlar et al.: Compression ratio of Wiener index in 2-d rectangular and polygonal lattices 9
Figure 7: The division of the area La k into subareas in the case vi}j e L(n'k.
kn ji(i) i q2 (p)
A(Ai) = 2 £ £ ££ (q2(p) - q) ■ k,
i=l j=j2(i) p= 1 q=l kn ji(i) Pi(1) qi(p)
A(A2) = 2 £ £ £ £ (qi(p) - q) ■ k,
i=1 j=j2(i) p=i q=1
kn ji(i) i 2n
A(A3) = 2 £ £ £ £ (q - qi(p)) ■ k, i=1 j=j2(i) P=1 q=qi(p)
kn ji(i) P2 (2n) 2n
A(A4) = 2 £ £ £ £ (q - q2(p)) ■ k.
i=1 j=j2(i) p=i q=q2(p)
Now A2 = A(A1) + A(A2) + A(As) + A(A) and by direct calculation we establish that A2 is a polynomial in n of degree 5 with leading coefficient being 25 k3. Therefore, we conclude that A is a polynomial in n of degree 5 with leading coefficient being equal to
1	( 14 k3 + 22 = 32 k3.
2	V 5 15 ) 15 Now the result follows from this and Theorem 3.1.
Theorem 4.2. For the lattice graph CLn,k, Wiener index W(CLn,k ) is a polynomial in n of degree 5 whose leading coefficient equals
4k2 (4k + 3).
Proof. Let us introduce the same vertex notation in CLn,k as in CRn,k (we can do that as CLnk is a subgraph of CRni<k). Since, CLn<k is a subgraph of CRni<k we have
W (CLn,k) = W (CRn,k ) + A.
Therefore, if we establish A, the result will follow from Theorem 3.2. Since all vertices in CLnk are equivalent in the sense that they have the same distances to all other vertices, it
10
Ars Math. Contemp. 7 (2014) 41-54
is enough to calculate difference in distances for one vertex, and then multiply it by number of vertices, and divide by two since each difference is thus calculated twice. It is easiest if we calculate for v1;1. Since CLn,k is a torus, we will calculate the difference in distance from v1;1 to vp,q where 1 < p < kn and 1 < q < n and multiply it by 4. In that area difference in distances is greater than 0 only if 1 < p < kn and q1 (p) < q < n where
qi(p) = 1 • p.
Therefore,
1	kn n
A « - • 2kn • 2n • 4 • ^ ^ (q - qi(p)) . p=1 q=qi(p)
By direct calculation, we obtain that A is a polynomial in n of degree 5 with leading coefficient being
4
-k3. 3
Now the result follows from Theorem 3.2.
□
Corollary 4.3. Holds
5 (4k + 3)
lim cr(Ln,k) =
4 (7k + 5)'
Now, we can derive from this result compression ratio for some specific lattices. For example, lattice Ln1 is hexagonal lattice with 2n rows and n columns of hexagons. Therefore, from Corollary 4.3 follows that compression factor for such lattice equals
lim cr(Ln i) = 5(4 + 3) = 35 = 0.729 17
n^^ v n'u 4(7 + 5) 48
confirming the result numerically derived in [2]. For k = 2, lattice Ln k is a lattice consisting of 10-gons, with 2n rows and n columns of rectangular unit cells with size 2k = 4 squares as in Figure 2. From Corollary 4.3 follows that compression factor for such lattice equals
lim cr(Ln 2) = 5(4 ^ 2 + 3) = 55 = 0.723 68. v n'2; 4(7 • 2 + 5) 76
Corollary 4.4. Holds
k
lim cr(Ln,k) = lim cr(Rn,k) -
n,k	n,k -
n^TO	n^TO	4(7k + 5)
Invariant limn^TO cr(Ln,k) reaches its maximum value limn^TO cr(Ln,1) = ||, whereas for large k the limit limn^TO cr(Ln,k) constantly decreases toward its lower limit 5.
J. Sedlar et al.: Compression ratio of Wiener index in 2-d rectangular and polygonal lattices 11
5 Compression ratio of R
In this section, we will establish the limit of compression ratio of d-dimensional rectangular cube Rd when n tends to infinity, and we will show that it does not depend on dimension d.
Theorem 5.1. Holds
3
lim cr (Rd) = -.
n^TO V n' 4
Proof. Let us denote [n] = {1,2,..., n} . Note that
lim W L+T^ = lim ~2i+T I E E E lyi - Xil
\(xi,...xd)e[n]d (y1,...yd)e[n]d 1<i<d
= JjS. n^T fd • n2d-2 E (j - •)
\	1<i<j<n
= iim -1 Id • E (j -
n^oo n3 I	—
\ 1<i<j<n
_ d = 6.
On the other hand
üm ^^ = nm (1 ■ ■2d ■ E E (Xi- D
(xi,...,xd)e[n/2]d l<i<d
-, nd+r |2d-'d( n r E (i - i>
Therefore
lim ^ Id ■ E (« - !)
n—^oo n2 I	^^
\ r<i<n
d 8 '
W (C Rd \	W ( R") d 3
lim cr(Rd) = lim W 1 = lim "2d+1 = -8 = -n-O Cr(Rn) n—>oo W (Rn ) n—O W(Rj) d 4 '
n2 d+1 6
□
6 Conclusion
In this paper, we studied compression ratio for open and closed 2-dimensional rectangular lattices Rn,k and 2-dimensional polygonal lattices Ln,k. For that purpose, we established that leading coefficient in W(ORn,k) equals 46k2 (1 + k) (Theorem 3.1), while
12
Ars Math. Contemp. 7 (2014) 41-54
in W(CRn,k) equals 4k2 (1 + k) (Theorem 3.2), which yields	cr(Rni<k) = 4
(Corollary 3.3). Also, we established that leading coefficient in W(OLn,k) equals ifk (7k + 5) (Theorem 4.1), while leading coefficient in W(CLn,k) equals |k2 (4k + 3) (Theorem 4.2), which yields lim„^TO cr(Ln,k) =	(Corollary 4.3). Lattice L„,i is hexagonal lattice with 2n rows and n columns of hexagons, for which therefore holds cr(Ln,i) = H. Lattice L„,2 is 10-gonal lattice with 2n rows and n columns, for which therefore limn^TO cr(Ln,2) = 45(-184+35)) = 75. Finally, we established that for d-dimensional rectangular cube holds limn^TO cr (Rn) = 3 (Theorem 5.1).
7 Acknowledgements
Partial support by the Ministry of Science, Education and Sports of the Republic of Croatia (Grant Nos. 098-0982929-2940, 083-0831510-1511, 177-0000000-0884, 037-00000002779) and project GReGAS within EuroGIGA Collaborative Research Project is gratefully acknowledged.
References
[1]	D. Bonchev and O. Mekenyan, A Topologycal Approach to the Calculation of the n-Electron Energy and Energy Gap of Infinite Conjugated Polymers, Z. Naturforsch. 35a (1980), 739-747.
[2]	F. Cataldo, O. Ori and A. Graovac, Graphene Topological Modifications, Int. J. Chem. Mod. 3(1-2) (2011), 45-63.
[3]	F. Cataldo, O. Ori and S. Iglesias-Groth, Topological lattice descriptors of graphene sheets with fullerene-like nanostructures, Molecular Simulation 36(5) (2010), 341-353.
[4]	T. Doslic, A. Graovac, F. Cataldo and O. Ori, Notes on some Distance-Based Invariants for 2-Dimensional Square and Comb Lattices, Iranian Journal of Mathematical Sciences and Informatics 5 (2010), 61-68.
[5]	T. Doslic, A. Graovac and O. Ori, Eccentric connectivity index of hexagonal belts and chains, MATCH Commun. Math. Comput. Chem. 65 (2011), 745-752.
[6]	T. Doslic, A. Graovac, D. Vukicevic, F. Cataldo, O. Ori, A. Iranmanesh, A. R. Ashrafi and F. Koorepazan-Moftakhar, Topological Compression Factors of 2-Dimensional TUC4C8(R) Lattices and Tori, Iranian Journal ofMathematical Sciences and Informatics 1 (2010), 73-80.
[7]	A. Iranmanesh, A. R. Ashrafi, A. Graovac, F. Cataldo and O. Ori, Wiener Index Role in Topological Modeling of Hexagonal Systems - From Fullerenes to Graphene, in: I. Gutman, B. Fortula (eds.), Distance in Molecular Graphs, Mathematical Chemistry Monographs series N.12 to be published 2012; info on MCM book series can be found at www.pmf.kg.ac.rs/match
[8]	D. Vukicevic, F. Cataldo, O. Ori and A. Graovac, Topological efficiency of C66 fullerene, Chem. Phys. Lett. 501 (2011), 442-445.
[9]	H. Wiener, Structural determination of paraffin boiling points, J. Am. Chem. Soc. 69(1) (1947), 17-20.