Extremal properties of connected 4-cyclic graphs of a topological index related to chemical graphs

Abstract

Augmented Zagreb index (AZI) is an important vertex-degree-based topological index with many applications especially in chemistry. In this article, minimum value of $AZI(G)$ is obtained and the corresponding extremal graph is characterized in the class of connected 4-cyclic graphs with seven or more vertices. These results can be used to characterize numerous chemical properties of chemical compounds having 4-cyclic structures.

Introduction

In this article, simple, finite, and undirected graphs are considered. Order and size of a graph represent the number of vertices and the number of edges in the graph, respectively. In chemical compounds, atoms may be regarded as vertices and their covalent bonds can be visualized as edges of the graph. Number of edges incident to a vertex u is known as the degree of the vertex and is usually denoted by $d_u$ . If $d_u=1,$ then u is known as a pendent vertex. Minimum and maximum degree in the graph G is usually denoted by $\delta (G)$ and $\mathrm{\Delta }(G)$ , respectively. Consider a connected graph G of order s and size t. A connected graph of order s is called 4-cyclic (written as $G_s^4$ ), if the deletion of four appropriate edges produces an acyclic graph of order s. Similar definitions hold for unicyclic ( $G_s^1$ ), bicyclic ( $G_s^2$ ), and tricyclic ( $G_s^3$ ) graphs. A graph invariant I associates a real number with a graph G satisfying the condition $I(G)=I(G*)$ for every graph $G*$ isomorphic (structurally equivalent) to G. Topological indices are graph invariants having many applications in chemical graph theory (CGT). A comparative study on the practical uses of different topological indices has been presented by Sarkar et al. ¹ Augmented Zagreb Index (AZI) is one of the several well-known topological indices which have shown significant better results as compared to other vertex-degree-based topological indices especially studying the heat formation and predicting the boiling points of different chemical compounds. For this reason, AZI is preferred in designing the Quantitative Structure-Property Relationship (QSPR) of chemical compounds. AZI has been introduced by Furtula et al. ² and is defined as:

$$AZI(G)=\sum _{uv\in E}{\left({\displaystyle \frac{d_u{d}_v}{d_u+d_v-2}}\right)}^3$$

where E represents the edge set of G.

AZI is the modified form of Atom Bond Connectivity index (ABC). Bounds of AZI especially, the lower bound, plays a vital role to study the stability assessment and predictive modeling of different chemical compounds. Minimum value of $AZI(G)$ among all connected graphs of order s was calculated by Furtula et al. ² They characterized the extremal graph attaining this minimum value (which is the star graph of order $s$ ). For various classes of connected graphs, using different graph parameters, particular bounds on $AZI(G)$ were obtained by Huang et al. ³ and Wang et al. ⁴ For $G\in G_s^1$ and $G\in G_s^2$ , tight upper bounds of $AZI(G)$ were determined by Ali et al. ⁵ They also derived a Nordhaus-Gaddum-type result for AZI. Zhan et al. ⁶ determined the minimum and second minimum values of $AZI(G)$ for $G\in G_s^1$ and minimum value for $G\in G_s^2$ with the characterization of their extremal graphs. Ali et al. ⁷ presented a survey paper in which they discussed all extremal results and bounds of $AZI(G)$ . Further, Ali ⁸ obtained the minimum value of $AZI(G)$ for all connected graphs $G\in G_s^3$ with $s\ge 6$ and characterized the unique extremal graph attaining the minimum value. Some new bounds on triangle free graphs and molecular trees were obtained by Qingcue et al. ⁹ Lower bound of $AZI(G)$ for $k$ -apex trees was determined by Liu et al. ¹⁰ with $k\ge 4$ and $s\ge 3(k+1)$ .

Any graph $G\in G_s^4$ has a great importance in Chemical Graph Theory as many chemical compounds especially many drugs have 4-cyclic structure. Therefore, it is expected that by understanding different properties of 4-cyclic graphs with the help of topological indices, a reasonable discussion on the behavior of these chemical compounds may be generated. In view of the importance of connected 4-cyclic graphs and their relevance with many chemical compounds, minimum values of $AZI(G)$ for all connected graphs $G\in G_s^4$ with $s\ge 7$ is presented in this article. We also obtain the unique extremal graph attaining the minimum value.

Main result

In this article, we determine the minimum value of $AZI(G)$ for all $G\in G_s^4$ . We also find the unique extremal graph attaining the minimum value of $AZI(G)$ with $s\ge 7$ in this class. The main result is presented as follows.

Theorem 1

Let $G\in G_s^4$ and $s\ge 7$ , then

$$AZI(G)\ge (s-7){\left({\displaystyle \frac{s-2}{s-3}}\right)}^3+80$$

and the equality holds if and only if $G\cong G*$ (the extremal graph presented in Figure 1).

Figure 1.

The extremal 4-Cyclic graph having minimum AZI.

To prove the above theorem, few lemmas will be discussed that will be helpful in proving our main result.

Lemma 1

If $G\in G_s^4$ with the degree of each vertex at least 2 and $s\ge 7,$ then

$$AZI(G)\ge (s-7){\left({\displaystyle \frac{s-2}{s-3}}\right)}^3+80$$

The equality holds if and only if $G\cong G*$ (the extremal graph presented in Figure 1).

Proof

For s = 7, all 4-cyclic connected nonisomorphic graphs with approximate AZI is presented in Figure 2.

Figure 2.

AZI(G) of 4-Cyclic connected graphs with s = 7.

Now consider $s>7$ , since any graph G having size t with degree of each vertex at least 2 and not isomorphic to two vertex path must satisfy the inequality

$$AZI(G)\ge 8m$$

Thus we have,

$$AZI(G)\ge 8(s+3)$$

Since $s>7$ , so

$$(s-7)\left(8-{\left({\displaystyle \frac{s-2}{s-3}}\right)}^3\right)\ge 0$$

which leads to

$$8(s+3)\ge (s-7){\left({\displaystyle \frac{s-2}{s-3}}\right)}^3+80$$

Therefore,

$$AZI(G)>(s-7){\left({\displaystyle \frac{s-2}{s-3}}\right)}^3+80$$

Lemma 2

Suppose $G\in G_s^4$ having $\mathrm{\Delta }(G)=s-1$ and $s\ge 7,$ then

$$AZI(G)>(s-7){\left({\displaystyle \frac{s-2}{s-3}}\right)}^3+80$$

Proof

When $s\ge 7$ , all graphs which are satisfying the given constraints in the lemma, are depicted in Figure 3.

Figure 3.

All possible graphs satisfying the conditions of the Lemma 2.

Approximate AZI of all these graphs are as follows:

$$AZI(B_1)=(s-9){\left({\displaystyle \frac{s-1}{s-2}}\right)}^3+96(ifs\ge 9)$$

$$AZI(B_2)=(s-8){\left({\displaystyle \frac{s-1}{s-2}}\right)}^3+27{\left({\displaystyle \frac{s-1}{s}}\right)}^3+80(ifs\ge 8)$$

$$AZI(B_3)=(s-7){\left({\displaystyle \frac{s-1}{s-2}}\right)}^3+54{\left({\displaystyle \frac{s-1}{s}}\right)}^3+{\displaystyle \frac{4313}{64}}$$

$$AZI(B_4)=(s-6){\left({\displaystyle \frac{s-1}{s-2}}\right)}^3+81{\left({\displaystyle \frac{s-1}{s}}\right)}^3+{\displaystyle \frac{1752}{32}}$$

$$AZI(B_5)=(s-6){\left({\displaystyle \frac{s-1}{s-2}}\right)}^3+27{\left({\displaystyle \frac{s-1}{s}}\right)}^3+64{\left({\displaystyle \frac{s-1}{s+1}}\right)}^3+56$$

$$AZI(B_6)=(s-5){\left({\displaystyle \frac{s-1}{s-2}}\right)}^3+108{\left({\displaystyle \frac{s-1}{s}}\right)}^3+{\displaystyle \frac{729}{16}}$$

From the above computations, it can be verified that

$$AZI(B_i)>(s-7){\left({\displaystyle \frac{s-2}{s-3}}\right)}^3+80$$

for $i=1,2,\dots ,6$ . Hence the result holds.

Lemma 3

For $s\ge 7$ , let $G\in G_s^4$ having $\delta (G)=1$ and $\mathrm{\Delta }(G)\le s-2$ . If the considered graph G is not isomorphic to any graph from $H_1,\dots ,H_{24}$ (shown in Figure 4), then

$$AZI(G)\ge (s-7){\left({\displaystyle \frac{s-2}{s-3}}\right)}^3+80$$

and the equality holds if and only if $G\cong G*$ (the extremal graph presented in Figure 1).

Figure 4.

Graphs H₁ – H₂₄.

Proof

Graphs satisfying the conditions of the lemma of order 7 with their approximate AZI are depicted as in Figure 5.

Figure 5.

All possible graphs satisfying the conditions of the Lemma 3 with s = 7.

From Figure 5, it follows that the lemma is true for $s=7$ . Now consider $s\ge 8$ and choose a vertex v in $V(G)$ such that it has minimum adjacent pendent vertices. Suppose these adjacent vertices of v are $u_1,u_2,\dots ,u_p$ and nonpendent adjacent vertices of $v$ are $u_{p+1},u_{p+2},\dots ,u_r$ . It is obvious that $r\ge 2$ . We delete the vertices $u_1,u_2,\dots ,u_p$ from the graph G to obtain a deduced graph $G^{\mathrm{\prime }}$ . Deduced graph $G^{\mathrm{\prime }}$ has order $s-p$ and size $s-p+3$ . If $s-p=5,$ then $G^{\mathrm{\prime }}$ is isomorphic to the following two graphs (Figure 6) which is a contradiction to the statement of the lemma (isomorphic to $H_1$ , $H_2$ ).

Figure 6.

Deduced graphs G′ with s – p = 5.

If $s-p=6$ then $G^{\mathrm{\prime }}$ is isomorphic to the following graphs (Figure 7) which is again a contradiction to the statement of this lemma (isomorphic to one of the graphs $H_4$ , $H_{24}$ ).

Figure 7.

Deduced graphs G′ with s – p = 6.

Thus $s-p\ge 7,$ so from lemma 1 and the hypothesis, we have

$$AZI(G^{\mathrm{\prime }})\ge (s-p-7){\left({\displaystyle \frac{s-p-2}{s-p-3}}\right)}^3+80$$

(1)

and the equality holds in equation (1) if and only if $G\cong G_{s-p}$ .

Suppose a vertex $u_i\in G$ having degree $d_u$ for $i=p+1,\dots ,r,$ then it holds that

$$AZI(G)=\sum _{i=p+1}^r\left[{\left({\displaystyle \frac{r{d}_{u_i}}{r+d_{u_i}-2}}\right)}^3-{\left({\displaystyle \frac{(r-p)d_{u_i}}{r+d_{u_i}-p-2}}\right)}^3\right]+p{\left({\displaystyle \frac{r}{r-1}}\right)}^3+AZI(G^{\mathrm{\prime }})$$

If the term written in the summation is considered as a function of s and $d_{u_i}$ , then the function will be increasing in $d_{u_i}$ in the interval $[2,\mathrm{\infty }]$ . So using this fact and from equation (1), we get the following inequality

$$AZI(G)\ge p{\left({\displaystyle \frac{r}{r-1}}\right)}^3+(s-p-7){\left({\displaystyle \frac{s-p-2}{s-p-3}}\right)}^3+80$$

(2)

and the equality holds if and only if $G^{\mathrm{\prime }}$ is isomorphic to $G{*}_{s-p}$ and $d_{u_i}=2$ for every $i\in \{p+1,p+2,\dots ,r\}.$

Now consider the function $f(z)={\left(\frac{z}{z-1}\right)}^3$ with $z\ge 2$ which is strictly decreasing in the interval $(2,\mathrm{\infty })$ . Thus the inequality $r\le s-2$ implies that

$$p{\left({\displaystyle \frac{r}{r-1}}\right)}^3\ge p{\left({\displaystyle \frac{s-2}{s-3}}\right)}^3$$

(3)

And the equality holds in equation (3) if and only if $r=s-2.$

We also have

$$p{\left({\displaystyle \frac{s-2}{s-3}}\right)}^3+(s-p-7){\left({\displaystyle \frac{s-p-2}{s-p-3}}\right)}^3+80=AZI(G*)+(s-p-7)\left[{\left({\displaystyle \frac{s-p-2}{s-p-3}}\right)}^3-{\left({\displaystyle \frac{s-2}{s-3}}\right)}^3\right]$$

(4)

As $s-p\ge 7,$ so we have

$$(s-p-7)\left[{\left({\displaystyle \frac{s-p-2}{s-p-3}}\right)}^3-{\left({\displaystyle \frac{s-2}{s-3}}\right)}^3\right]\ge 0$$

(5)

and the equality holds if and only if $s-p=7$ . Hence from equations (2)–(5), we have $AZI(G)\ge AZI(G*)$ and the equality holds if and only if $G\cong G*$ .

Lemma 4

If G is isomorphic to one of the graphs $H_1,\dots ,H_{24}$ shown in Figure 4, then

$$AZI(G)>(s-7){\left({\displaystyle \frac{s-2}{s-3}}\right)}^3+80$$

Proof

We calculate AZI of all graphs depicted in Figure 4 as follows:

$$AZI(H_1)\ge (s-5){\left({\displaystyle \frac{s-2}{s-3}}\right)}^3+54{\left({\displaystyle \frac{s-2}{s-1}}\right)}^3+64{\left({\displaystyle \frac{s-2}{s}}\right)}^3+{\displaystyle \frac{5184}{125}+{\displaystyle \frac{1458}{64}}}$$

$$AZI(H_2)\ge (s-5){\left({\displaystyle \frac{s-3}{s-4}}\right)}^3+128{\left({\displaystyle \frac{s-3}{s-1}}\right)}^3+{\displaystyle \frac{6912}{125}+{\displaystyle \frac{4096}{216}+{\displaystyle \frac{729}{64}}}}$$

$$AZI(H_3)\ge (s-5){\left({\displaystyle \frac{s-2}{s-3}}\right)}^3+27{\left({\displaystyle \frac{s-2}{s-1}}\right)}^3+128{\left({\displaystyle \frac{s-2}{s}}\right)}^3+{\displaystyle \frac{4096}{216}+{\displaystyle \frac{3456}{125}+16}}$$

$$AZI(H_4)\ge (s-6){\left({\displaystyle \frac{s-4}{s-5}}\right)}^3+250{\left({\displaystyle \frac{s-4}{s-1}}\right)}^3+{\displaystyle \frac{15625}{512}+48}$$

$$AZI(H_5)\ge (s-6){\left({\displaystyle \frac{s-3}{s-4}}\right)}^3+125{\left({\displaystyle \frac{s-3}{s}}\right)}^3+54{\left({\displaystyle \frac{s-3}{s-1}}\right)}^3+{\displaystyle \frac{3375}{108}+32}$$

$$AZI(H_6)\ge (s-6){\left({\displaystyle \frac{s-4}{s-5}}\right)}^3+125{\left({\displaystyle \frac{s-4}{s-1}}\right)}^3+27{\left({\displaystyle \frac{s-4}{s-3}}\right)}^3+{\displaystyle \frac{3375}{72}+{\displaystyle \frac{729}{32}+16}}$$

$$AZI(H_7)\ge (s-6){\left({\displaystyle \frac{s-3}{s-4}}\right)}^3+125{\left({\displaystyle \frac{s-3}{s}}\right)}^3+27{\left({\displaystyle \frac{s-3}{s-2}}\right)}^3+{\displaystyle \frac{3375}{108}+{\displaystyle \frac{729}{64}+32}}$$

$$AZI(H_8)\ge (s-6){\left({\displaystyle \frac{s-4}{s-5}}\right)}^3+125{\left({\displaystyle \frac{s-4}{s-1}}\right)}^3+64{\left({\displaystyle \frac{s-4}{s-2}}\right)}^3+{\displaystyle \frac{8000}{343}+{\displaystyle \frac{3375}{216}+{\displaystyle \frac{1728}{125}+32}}}$$

$$AZI(H_9)\ge (s-6){\left({\displaystyle \frac{s-2}{s-3}}\right)}^3+125{\left({\displaystyle \frac{s-2}{s+1}}\right)}^3+27{\left({\displaystyle \frac{s-2}{s-1}}\right)}^3+{\displaystyle \frac{3375}{216}+48}$$

$$AZI(H_{10})\ge (s-6){\left({\displaystyle \frac{s-3}{s-4}}\right)}^3+125{\left({\displaystyle \frac{s-3}{s}}\right)}^3+64{\left({\displaystyle \frac{s-3}{s-1}}\right)}^3+{\displaystyle \frac{8000}{343}+32}$$

$$AZI(H_{11})\ge (s-6){\left({\displaystyle \frac{s-4}{s-5}}\right)}^3+125{\left({\displaystyle \frac{s-4}{s-1}}\right)}^3+27{\left({\displaystyle \frac{s-4}{s-3}}\right)}^3+{\displaystyle \frac{8000}{343}+{\displaystyle \frac{3375}{216}+{\displaystyle \frac{1728}{125}+16}}}$$

$$AZI(H_{12})\ge (s-6){\left({\displaystyle \frac{s-2}{s-3}}\right)}^3+54{\left({\displaystyle \frac{s-2}{s-1}}\right)}^3+64{\left({\displaystyle \frac{s-2}{s}}\right)}^3+{\displaystyle \frac{1728}{125}+{\displaystyle \frac{729}{64}+32}}$$

$$AZI(H_{13})\ge (s-6){\left({\displaystyle \frac{s-4}{s-5}}\right)}^3+128{\left({\displaystyle \frac{s-4}{s-2}}\right)}^3+{\displaystyle \frac{5184}{125}+{\displaystyle \frac{4096}{216}+{\displaystyle \frac{729}{64}+16}}}$$

$$AZI(H_{14})\ge (s-6){\left({\displaystyle \frac{s-4}{s-5}}\right)}^3+64{\left({\displaystyle \frac{s-4}{s-2}}\right)}^3+27{\left({\displaystyle \frac{s-4}{s-3}}\right)}^3+{\displaystyle \frac{5184}{125}+{\displaystyle \frac{4096}{216}+{\displaystyle \frac{729}{64}+16}}}$$

$$AZI(H_{15})\ge (s-6){\left({\displaystyle \frac{s-3}{s-4}}\right)}^3+128{\left({\displaystyle \frac{s-3}{s-1}}\right)}^3+27{\left({\displaystyle \frac{s-3}{s-2}}\right)}^3+{\displaystyle \frac{4096}{216}+{\displaystyle \frac{1728}{125}+32}}$$

$$AZI(H_{16})\ge (s-6){\left({\displaystyle \frac{s-3}{s-4}}\right)}^3+64{\left({\displaystyle \frac{s-3}{s-1}}\right)}^3+27{\left({\displaystyle \frac{s-3}{s-2}}\right)}^3+{\displaystyle \frac{4096}{216}+{\displaystyle \frac{3456}{-125}+32}}$$

$$AZI(H_{17})\ge (s-6){\left({\displaystyle \frac{s-3}{s-4}}\right)}^3+81{\left({\displaystyle \frac{s-3}{s-2}}\right)}^3+{\displaystyle \frac{2187}{32}}$$

$$AZI(H_{18})\ge (s-6){\left({\displaystyle \frac{s-4}{s-5}}\right)}^3+64{\left({\displaystyle \frac{s-4}{s-2}}\right)}^3+27{\left({\displaystyle \frac{s-4}{s-3}}\right)}^3+{\displaystyle \frac{6912}{125}+{\displaystyle \frac{4096}{216}+16}}$$

$$AZI(H_{19})\ge (s-6){\left({\displaystyle \frac{s-3}{s-4}}\right)}^3+128{\left({\displaystyle \frac{s-3}{s-1}}\right)}^3+{\displaystyle \frac{4096}{216}+{\displaystyle \frac{3456}{125}+32}}$$

$$AZI(H_{20})\ge (s-6){\left({\displaystyle \frac{s-2}{s-3}}\right)}^3+64{\left({\displaystyle \frac{s-2}{s}}\right)}^3+54{\left({\displaystyle \frac{s-2}{s-1}}\right)}^3+{\displaystyle \frac{3456}{125}+32}$$

$$AZI(H_{21})\ge (s-6){\left({\displaystyle \frac{s-4}{s-5}}\right)}^3+54{\left({\displaystyle \frac{s-4}{s-3}}\right)}^3+{\displaystyle \frac{6912}{125}+{\displaystyle \frac{2187}{64}+32}}$$

$$AZI(H_{22})\ge (s-6){\left({\displaystyle \frac{s-2}{s-3}}\right)}^3+108{\left({\displaystyle \frac{s-2}{s-1}}\right)}^3+{\displaystyle \frac{2187}{64}+16}$$

$$AZI(H_{23})\ge (s-6){\left({\displaystyle \frac{s-3}{s-4}}\right)}^3+64{\left({\displaystyle \frac{s-3}{s-1}}\right)}^3+27{\left({\displaystyle \frac{s-3}{s-2}}\right)}^3+{\displaystyle \frac{5184}{125}+{\displaystyle \frac{1458}{64}+16}}$$

$$AZI(H_{24})\ge (s-6){\left({\displaystyle \frac{s-3}{s-4}}\right)}^3+64{\left({\displaystyle \frac{s-3}{s-1}}\right)}^3+54{\left({\displaystyle \frac{s-3}{s-2}}\right)}^3+{\displaystyle \frac{5184}{125}+{\displaystyle \frac{729}{64}+16}}$$

Therefore, we conclude that

$$AZI(H_i)>(s-7){\left({\displaystyle \frac{s-2}{s-3}}\right)}^3+80$$

$$\mathrm{for}i=1,\dots ,24$$

Proof of theorem 1

Using Lemmas 1–4 our main result follows.

Conclusion

In this article, we have determined the minimum value of $AZI(G)$ in the class of connected 4-cyclic graphs. Also, the unique extremal graph attaining this minimum value of $AZI(G)$ has been characterized. The authors feel that it would be interesting to find the same characterization of $AZI(G)$ in the class of k-cyclic with $k\ge 5$ graphs. Another possible extension would be to find a possible ordering of graphs on the basis of minimum values of $AZI(G)$ .