# The Atom-Bond Connectivity Index of Catacondensed Polyomino Graphs

Authors: Jinsong Chen; Jianping Liu; Qiaoliang Li
Journal: Discrete Dynamics in Nature and Society
 (2013)

---

## Abstract

LetG=(V,E) be a graph. The atom-bond connectivity (ABC) index is defined as the sum of weights ((du+dv−2)/dudv)1/2 over all edges uv of G, where du denotes the degree of a vertex u of G. In this paper, we give the atom-bond connectivity index of the zigzag chain polyomino graphs. Meanwhile, we obtain the sharp upper bound on the atom-bond connectivity index of catacondensed polyomino graphs with h squares and determine the corresponding extremal graphs.


---

## Body

## 1. Introduction

One of the most active fields of research in contemporary chemical graph theory is the study of topological indices (graph topological invariants) that can be used for describing and predicting physicochemical and pharmacological properties of organic compounds. In chemistry and for chemical graphs, these invariant numbers are known as the topological indices. There are many publications on the topological indices, see [1–6].LetG=(V,E) be a simple graph of order n. A few years ago, Estrada et al. [7] introduced a further vertex-degree-based graph invariant, known as the atom-bond connectivity (ABC) index. It is defined as:
(1)ABC(G)=∑uv∈E(G)‍du+dv-2dudv.TheABC index keeps the spirit of the Randić index, and it provides a good model for the stability of linear and branched alkanes as well as the strain energy of cycloalkanes [7]. Recently, the study of the ABC index attracts some research attention [6, 8–12].Polyomino graphs [13], also called chessboards [14] or square-cell configurations [15] have attracted some mathematicians’ considerable attention because many interesting combinatorial subjects are yielded from them such as domination problem and modeling problems of surface chemistry. A polyomino graph [16] is a connected geometric graph obtained by arranging congruent regular squares of side length 1 (called a cell) in a plane such that two squares are either disjoint or have a common edge. The polyomino graph has received considerable attentions.Next, we introduce some graph definitions used in this paper.Definition 1 (see [4]).
LetG be a polyomino graph. If all vertices of G lie on its perimeter, then G is said to be catacondensed polyomino graph or tree-like polyomino graph. (see Figure 1).Figure 1
The zigzag chain polyomino graphZh.Definition 2 (see [16]).
LetG be a chain polyomino graph with h squares. If the subgraph obtained from G by deleting all the vertices of degree 2 and all the edges adjacent to the vertices is a path, then G is said to be the zigzag chain polyomino graph, denoted by Zh (see Figure 1).
In this paper, we give theABC indices of the zigzag chain polyomino graphs with h squares and obtain the sharp upper bound on the ABC indices of catacondensed polyomino graphs with h squares and determine the corresponding extremal graphs.


## 2. TheABC Indices of Catacondensed Polyomino Graphs

Let(2)S1={2+23,2+153-23,2},S2={2,322+64+153-2,43+156,23+153,2+153-23,2+64+156-23,2+64,2+62-156,22+64+23,22+64+156,22+62+23-156,22+64+153-23,22+62,322+64+152-83,322+264+156-2,322+64+4156-103,322+62+2156-83,322+364-2,322+364-153-23,322+364-156-43,322+6-152-23,322+6-2156-43,322+564-2153-23,322+62-43,322+364+156-83},S=S1⋃‍S2.
We call (du+dv-2)/dudv the weight of the edge uv, denoted by Wuv.Note that for any catacondensed polyomino graphH* with h squares, it can be obtained by gluing a new square s to some catacondensed polyomino graph H with h-1 squares. So, we have the following lemma.Lemma 3.
LetH* be a catacondensed polyomino graph with h squares which is obtained by gluing a new square s to some graph H, where H is a catacondensed polyomino graph with h-1 squares. One has (i)
If2≤h≤3, thenABC(H*)-ABC(H)∈S1,(ii)
ifh≥4, thenABC(H*)-ABC(H)∈S2.Proof. Consider the following:
(i)  if2≤h≤3, by directly calculating, we have ABC(H*)-ABC(H)∈S1,
(ii)  now, leth≥4. Without the loss of generality, let square s be adjacent to the edge AB in H (see Figure 2). In the following, if the weights of some edges of H have been changed when s is adjacent to the edge AB in H, then we marked these edges with thick lines in H*. Let Di=ABC(H*)-ABC(H)(i=1,2,…,35). Note that except the edge AB of s, the summation of the weights of the remaining three edges is always (3/2)2 in H*. There are exactly three types of formations (see Figure 2).
Case
1. In Type I, dA1=dB1=2 and dA2=dB2=3 (see Figure 3).
By the definition ofABC index, we have ABC(H*)-ABC(H) = (3/2)2 + (WuA2-WuA1) + (WA2B2-WA1B1) + (WvB2-WvB1) = Di (i=1,2,3).Ifdu=3anddv=3, then D1=2.Ifdu=3anddv=4 or du=4anddv=3, then D2=4/3+15/6.Ifdu=4anddv=4, then D3=2/3+15/3.Case2. In Type II, dA1=2, dB1=3,dA2=3, anddB2=4. (see Figure 4).
Letu adjacent to A and v, w adjacent to B (see Figure 4). Then du∈{2,3,4}, dv∈{3,4}, and dw∈{2,3,4}. If du=2, dv=3, and dw=2, which is in contradiction with h≥4; if du=3anddv=3, which is in contradiction with dB1=3; if du=4anddv=3, which is in contradiction with dA1=2 (A∈V(H)).
By the definition ofABC index, we have ABC(H*)-ABC(H) = (3/2)2 + (WuA2-WuA1) + (WA2B2-WA1B1) + (WvB2-WvB1) + (WwB2-WwB1) = Di (i=4,5,…,14).Ifdu=2,dv=3,anddw=3, then D4=2+15/2-4/3.Ifdu=2,dv=3,anddw=4, then D5=2+6/4+15/6-2/3.Ifdu=2,dv=4,anddw=2, then D6=2+6/4.Ifdu=2,dv=4,anddw=3, then D7=2+6/4+15/6-2/3.Ifdu=2,dv=4,anddw=4, then D8=2+6/2-15/6.Ifdu=3,dv=4,anddw=2, then D9=2/2+6/4+2/3.Ifdu=3,dv=4,anddw=3, then D10=2/2+6/4+5/12.Ifdu=3,dv=4,anddw=4, then D11=2/2+6/2+2/3-5/12.Ifdu=4,dv=4,anddw=2, then D12=2/2+6/4+5/12.Ifdu=4,dv=4,anddw=3, then D13=2/2+6/4+25/12-2/3.Ifdu=4,dv=4,anddw=4, then D14=2/2+6/2.
Case
3. In Type III, dA1=dB1=3 and dA2=dB2=4 (see Figure 5).
Letu, x adjacent to A and v, w adjacent to B (see Figure 5). Then, du∈{3,4}, dv∈{3,4}, dw∈{2,3,4}, and dx∈{2,3,4}. Since the case du=3,dv=4,dx=y1,anddw=y2 is the same as du=4,dv=3,dx=y2,anddw=y1, where y1,y2∈{2,3,4}. And note that if du=dv=3 or du=dv=4, the vertices x and w are symmetric.
By the definition ofABC index, we have ABC(H*)-ABC(H)=(3/2)2+(WxA2-WxA1)+(WuA2-WuA1)+(WA2B2-WA1B1)+(WvB2-WvB1)+(WwB2-WwB1)=Di (i=15,16,…,35).Ifdu=dv=3,dx=2,anddw=3, then D15=32/2+6/4+15/2-8/3.Ifdu=dv=3,dx=2,anddw=4, then D16=32/2+6/2+15/6-2.Ifdu=dv=3,dx=3,anddw=3, then D17=32/2+6/4+215/3-10/3.Ifdu=dv=3,dx=3,anddw=4, then D18=32/2+6/2+15/3-8/3.Ifdu=dv=3,dx=4,anddw=4, then D19=32/2+36/4-2.Ifdu=dv=4,dx=2,anddw=2, then D20=32/2+36/4-15/3-2/3.Ifdu=dv=4,dx=2,anddw=3, then D21=32/2+36/4-15/6-4/3.Ifdu=dv=4,dx=2,anddw=4, then D22=32/2+6-15/2-2/3.Ifdu=dv=4,dx=3,anddw=3, then D23=32/2+36/4-2.Ifdu=dv=4,dx=3,anddw=4, then D24=32/2+6-15/3-4/3.Ifdu=dv=4,dx=4,anddw=4, then D25=32/2+56/4-215/3-2/3.Ifdu=3,dv=4,dx=2,anddw=2, then D26=32/2+6/2-4/3.Ifdu=3,dv=4,dx=2,anddw=3, then D27=32/2+6/2+15/6-2.Ifdu=3,dv=4,dx=2,anddw=4, then D28=32/2+36/4-15/6-4/3.Ifdu=3,dv=4,dx=3,anddw=2, then D29=32/2+6/2+15/6-2.Ifdu=3,dv=4,dx=3,anddw=3, then D30=32/2+6/2+15/3-8/3.Ifdu=3,dv=4,dx=3,anddw=4, then D31=32/2+36/4-2.Ifdu=3,dv=4,dx=4,anddw=2, then D32=32/2+36/4-15/6-4/3.Ifdu=3,dv=4,dx=4,anddw=3, then D33=32/2+36/4-2.Ifdu=3,dv=4,dx=4,anddw=4, then D34=32/2+6-15/3-4/3.Ifdu=3,dv=3,dx=2,anddw=2, then D35=32/2+6/4+15/3-2.
By directly calculating, we haveD5=D7, D10=D12, D16=D27=D29, D18=D30, D19=D23=D31=D33, D21=D28=D32, D24=D34, and D6=max1≤i≤35Di, D14=min1≤i≤35Di. So ABC(H*)-ABC(H)∈S2, where h≥4.
Therefore,ABC(H*)-ABC(H)∈S.Figure 2Figure 3Figure 4Figure 5By Lemma3, we have the following theorem.Theorem 4.
LetG be a catacondensed polyomino graph with h(h≥2) squares, then
(3)ABC(G)=32+23+(2+153-23)a1+2a2+(43+156)a3+(23+153)a4+(2+152-43)a5+(2+64+156-23)a6+(2+64)a7+(2+62-156)a8+(22+64+23)a9+(22+64+156)a10+(22+62+23-156)a11+(22+64+153-23)a12+(22+62)a13+(322+64+152-83)a14+(322+62+156-2)a15+(322+64+2153-103)a16+(322+62+153-83)a17+(322+364-2)a18+(322+364-153-23)a19+(322+364-156-43)a20+(322+6-152-23)a21+(322+6-153-43)a22+(322+564-2153-23)a23+(322+62-43)a24+(322+64+153-2)a25,
where ai is a nonnegative integer for i=1,2,…,25 and h=2+∑i=125‍ai.Proof.
We prove Theorem4 by the induction on h. If h=2, by directly calculating, we have ABC(G)=32+2/3, where ai=0 (i=1,2,…,25). So, Theorem 4 holds for h=2.
Assume that Theorem4 holds for all catacondensed polyomino graphs with h-1 (h-1≥2) squares, that is,
(4)ABC(G)=32+23+(2+153-23)a1+2a2+(43+156)a3+(23+153)a4+(2+152-43)a5+(2+64+156-23)a6+(2+64)a7+(2+62-156)a8+(22+64+23)a9+(22+64+156)a10+(22+62+23-156)a11+(22+64+153-23)a12+(22+62)a13+(322+64+152-83)a14+(322+62+156-2)a15+(322+64+2153-103)a16+(322+62+153-83)a17+(322+364-2)a18+(322+364-153-23)a19+(322+364-156-43)a20+(322+6-152-23)a21+(322+6-153-43)a22+(322+564-2153-23)a23+(322+62-43)a24+(322+64+153-2)a25,
where ai is a nonnegative integer for i=1,2,…,25 and h-1=2+∑i=125‍ai.
We will prove that Theorem4 holds for h in the following. Let G* be a catacondensed polyomino graph with h squares. Without the loss of generality, G* can be obtained from some catacondensed polyomino graph G with h-1 squares by gluing a new square s to G. By Lemma 3, we have ABC(G*)-ABC(G)∈S. It means that ABC(G*)=ABC(G)+a, where a∈S. By the induction assumption and direct computation, we have
(5)ABC(G*)=32+23+(2+153-23)a1*+2a2*+(43+156)a3*+(23+153)a4*+(2+152-43)a5*+(2+64+156-23)a6*+(2+64)a7*+(2+62-156)a8*+(22+64+23)a9*+(22+64+156)a10*+(22+62+23-156)a11*+(22+64+153-23)a12*+(22+62)a13*+(322+64+152-83)a14*+(322+62+156-2)a15*+(322+64+2153-103)a16*+(322+62+153-83)a17*+(322+364-2)a18*+(322+364-153-23)a19*+(322+364-156-43)a20*+(322+6-152-23)a21*+(322+6-153-43)a22*+(322+564-2153-23)a23*+(322+62-43)a24*+(322+64+153-2)a25*.
There exists some l∈{1,2,…,25} such that al*=al+1 and aj*=aj for j≠l (j∈{1,2,…,25}). Obviously, ai* is a nonnegative integer for i=1,2,…,25 and 2+∑i=125‍ai*=2+1+∑i=125‍ai=h.Lemma 5.
LetH be a catacondensed polyomino graph with h squares. If h≤3, there are exactly four nonisomorphism catacondensed polyomino graphs (see Figure 6), where ABC(H1)=22, ABC(H2)=32+2/3, ABC(H3)=32+8/3, ABC(H4)=42+15/3.Figure 6
A catacondensed polyomino graph withh (h≤3) squares.Theorem 6.
LetZh be a zigzag chain polyomino graph with h squares, then
(6)ABC(Zh)={22,h=1,32+23,h=2,(h+1)2+(h-3)·64+153,h≥3.Proof.
Obviously,Zh can be obtained by gluing a new square sh to Zh-1. Let sh-1 be the square adjacent to sh (see Figure 1). We will prove Theorem 6 by the induction on h.
Ifh=1,2,3, then Theorem 6 holds (by Lemma 5). Assume that ABC(Zh-1)=(h-1+1)2+(h-1-3)·(6/4)+(15/3)=h2+(h-4)·(6/4)+(15/3) for h-1≥3. By the induction assumption and the D6 in Lemma 3, we have
(7)ABC(Zh)=ABC(Zh-1)+D6=h2+(h-4)·64+153+(2+64)=(h+1)2+(h-3)·64+153.
So, Theorem6 holds.Note thatD6=max1≤i≤35Di for h≥4 and by Lemma 5, we obtain the following Theorem 7.Theorem 7.
LetG be a catacondensed polyomino graph with h squares, then ABC(G)≤(h+1)2+(h-3)·(6/4)+(15/3), with the equality if and only if G≅Zh.



---

*Source: 598517-2013-03-17.xml*