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 $A Z I (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.

Keywords

4-Cyclic graphs extremal properties AZI chemical graph

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 $δ (G)$ and $Δ (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:

A Z I (G) = \sum_{u v \in E} {(\frac{d_{u} d_{v}}{d_{u} + d_{v} - 2})}^{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 $A Z I (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 $A Z I (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 $A Z I (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 $A Z I (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 $A Z I (G)$ . Further, Ali⁸ obtained the minimum value of $A Z I (G)$ for all connected graphs $G \in G_{s}^{3}$ with $s \geq 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 $A Z I (G)$ for $k$ -apex trees was determined by Liu et al.¹⁰ with $k \geq 4$ and $s \geq 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 $A Z I (G)$ for all connected graphs $G \in G_{s}^{4}$ with $s \geq 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 $A Z I (G)$ for all $G \in G_{s}^{4}$ . We also find the unique extremal graph attaining the minimum value of $A Z I (G)$ with $s \geq 7$ in this class. The main result is presented as follows.

Theorem 1

Let $G \in G_{s}^{4}$ and $s \geq 7$ , then

A Z I (G) \geq (s - 7) {(\frac{s - 2}{s - 3})}^{3} + 80

and the equality holds if and only if

G ≅ 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 \geq 7,$ then

A Z I (G) \geq (s - 7) {(\frac{s - 2}{s - 3})}^{3} + 80

The equality holds if and only if

G ≅ 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

A Z I (G) \geq 8 m

Thus we have,

A Z I (G) \geq 8 (s + 3)

Since

s > 7

, so

(s - 7) (8 - {(\frac{s - 2}{s - 3})}^{3}) \geq 0

which leads to

8 (s + 3) \geq (s - 7) {(\frac{s - 2}{s - 3})}^{3} + 80

Therefore,

A Z I (G) > (s - 7) {(\frac{s - 2}{s - 3})}^{3} + 80

Lemma 2

Suppose $G \in G_{s}^{4}$ having $Δ (G) = s - 1$ and $s \geq 7,$ then

A Z I (G) > (s - 7) {(\frac{s - 2}{s - 3})}^{3} + 80

Proof

When $s \geq 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:

A Z I (B_{1}) = (s - 9) {(\frac{s - 1}{s - 2})}^{3} + 96 (i f s \geq 9)

A Z I (B_{2}) = (s - 8) {(\frac{s - 1}{s - 2})}^{3} + 27 {(\frac{s - 1}{s})}^{3} + 80 (i f s \geq 8)

A Z I (B_{3}) = (s - 7) {(\frac{s - 1}{s - 2})}^{3} + 54 {(\frac{s - 1}{s})}^{3} + \frac{4313}{64}

A Z I (B_{4}) = (s - 6) {(\frac{s - 1}{s - 2})}^{3} + 81 {(\frac{s - 1}{s})}^{3} + \frac{1752}{32}

A Z I (B_{5}) = (s - 6) {(\frac{s - 1}{s - 2})}^{3} + 27 {(\frac{s - 1}{s})}^{3} + 64 {(\frac{s - 1}{s + 1})}^{3} + 56

A Z I (B_{6}) = (s - 5) {(\frac{s - 1}{s - 2})}^{3} + 108 {(\frac{s - 1}{s})}^{3} + \frac{729}{16}

From the above computations, it can be verified that

A Z I (B_{i}) > (s - 7) {(\frac{s - 2}{s - 3})}^{3} + 80

for

i = 1, 2, \dots, 6

. Hence the result holds.

Lemma 3

For $s \geq 7$ , let $G \in G_{s}^{4}$ having $δ (G) = 1$ and $Δ (G) \leq s - 2$ . If the considered graph G is not isomorphic to any graph from $H_{1}, \dots, H_{24}$ (shown in Figure 4), then

A Z I (G) \geq (s - 7) {(\frac{s - 2}{s - 3})}^{3} + 80

and the equality holds if and only if

G ≅ 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 \geq 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 \geq 2$ . We delete the vertices $u_{1}, u_{2}, \dots, u_{p}$ from the graph G to obtain a deduced graph $G^{'}$ . Deduced graph $G^{'}$ has order $s - p$ and size $s - p + 3$ . If $s - p = 5,$ then $G^{'}$ 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^{'}$ 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 \geq 7,$ so from lemma 1 and the hypothesis, we have

A Z I (G^{'}) \geq (s - p - 7) {(\frac{s - p - 2}{s - p - 3})}^{3} + 80

(1)

and the equality holds in equation (1) if and only if

G ≅ G_{s - p}

Suppose a vertex $u_{i} \in G$ having degree $d_{u}$ for $i = p + 1, \dots, r,$ then it holds that

A Z I (G) = \sum_{i = p + 1}^{r} [{(\frac{r d_{u_{i}}}{r + d_{u_{i}} - 2})}^{3} - {(\frac{(r - p) d_{u_{i}}}{r + d_{u_{i}} - p - 2})}^{3}] + p {(\frac{r}{r - 1})}^{3} + A Z I (G^{'})

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, \infty]

. So using this fact and from equation (1), we get the following inequality

A Z I (G) \geq p {(\frac{r}{r - 1})}^{3} + (s - p - 7) {(\frac{s - p - 2}{s - p - 3})}^{3} + 80

(2)

and the equality holds if and only if

G^{'}

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) = {(\frac{z}{z - 1})}^{3}$ with $z \geq 2$ which is strictly decreasing in the interval $(2, \infty)$ . Thus the inequality $r \leq s - 2$ implies that

p {(\frac{r}{r - 1})}^{3} \geq p {(\frac{s - 2}{s - 3})}^{3}

(3)

And the equality holds in equation (3) if and only if

r = s - 2.

We also have

p {(\frac{s - 2}{s - 3})}^{3} + (s - p - 7) {(\frac{s - p - 2}{s - p - 3})}^{3} + 80 = A Z I (G *) + (s - p - 7) [{(\frac{s - p - 2}{s - p - 3})}^{3} - {(\frac{s - 2}{s - 3})}^{3}]

(4)

s - p \geq 7,

so we have

(s - p - 7) [{(\frac{s - p - 2}{s - p - 3})}^{3} - {(\frac{s - 2}{s - 3})}^{3}] \geq 0

(5)

and the equality holds if and only if

s - p = 7

. Hence from equations (2)–(5), we have

A Z I (G) \geq A Z I (G *)

and the equality holds if and only if

G ≅ G *

Lemma 4

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

A Z I (G) > (s - 7) {(\frac{s - 2}{s - 3})}^{3} + 80

Proof

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

A Z I (H_{1}) \geq (s - 5) {(\frac{s - 2}{s - 3})}^{3} + 54 {(\frac{s - 2}{s - 1})}^{3} + 64 {(\frac{s - 2}{s})}^{3} + \frac{5184}{125} + \frac{1458}{64}

A Z I (H_{2}) \geq (s - 5) {(\frac{s - 3}{s - 4})}^{3} + 128 {(\frac{s - 3}{s - 1})}^{3} + \frac{6912}{125} + \frac{4096}{216} + \frac{729}{64}

A Z I (H_{3}) \geq (s - 5) {(\frac{s - 2}{s - 3})}^{3} + 27 {(\frac{s - 2}{s - 1})}^{3} + 128 {(\frac{s - 2}{s})}^{3} + \frac{4096}{216} + \frac{3456}{125} + 16

A Z I (H_{4}) \geq (s - 6) {(\frac{s - 4}{s - 5})}^{3} + 250 {(\frac{s - 4}{s - 1})}^{3} + \frac{15625}{512} + 48

A Z I (H_{5}) \geq (s - 6) {(\frac{s - 3}{s - 4})}^{3} + 125 {(\frac{s - 3}{s})}^{3} + 54 {(\frac{s - 3}{s - 1})}^{3} + \frac{3375}{108} + 32

A Z I (H_{6}) \geq (s - 6) {(\frac{s - 4}{s - 5})}^{3} + 125 {(\frac{s - 4}{s - 1})}^{3} + 27 {(\frac{s - 4}{s - 3})}^{3} + \frac{3375}{72} + \frac{729}{32} + 16

A Z I (H_{7}) \geq (s - 6) {(\frac{s - 3}{s - 4})}^{3} + 125 {(\frac{s - 3}{s})}^{3} + 27 {(\frac{s - 3}{s - 2})}^{3} + \frac{3375}{108} + \frac{729}{64} + 32

A Z I (H_{8}) \geq (s - 6) {(\frac{s - 4}{s - 5})}^{3} + 125 {(\frac{s - 4}{s - 1})}^{3} + 64 {(\frac{s - 4}{s - 2})}^{3} + \frac{8000}{343} + \frac{3375}{216} + \frac{1728}{125} + 32

A Z I (H_{9}) \geq (s - 6) {(\frac{s - 2}{s - 3})}^{3} + 125 {(\frac{s - 2}{s + 1})}^{3} + 27 {(\frac{s - 2}{s - 1})}^{3} + \frac{3375}{216} + 48

A Z I (H_{10}) \geq (s - 6) {(\frac{s - 3}{s - 4})}^{3} + 125 {(\frac{s - 3}{s})}^{3} + 64 {(\frac{s - 3}{s - 1})}^{3} + \frac{8000}{343} + 32

A Z I (H_{11}) \geq (s - 6) {(\frac{s - 4}{s - 5})}^{3} + 125 {(\frac{s - 4}{s - 1})}^{3} + 27 {(\frac{s - 4}{s - 3})}^{3} + \frac{8000}{343} + \frac{3375}{216} + \frac{1728}{125} + 16

A Z I (H_{12}) \geq (s - 6) {(\frac{s - 2}{s - 3})}^{3} + 54 {(\frac{s - 2}{s - 1})}^{3} + 64 {(\frac{s - 2}{s})}^{3} + \frac{1728}{125} + \frac{729}{64} + 32

A Z I (H_{13}) \geq (s - 6) {(\frac{s - 4}{s - 5})}^{3} + 128 {(\frac{s - 4}{s - 2})}^{3} + \frac{5184}{125} + \frac{4096}{216} + \frac{729}{64} + 16

A Z I (H_{14}) \geq (s - 6) {(\frac{s - 4}{s - 5})}^{3} + 64 {(\frac{s - 4}{s - 2})}^{3} + 27 {(\frac{s - 4}{s - 3})}^{3} + \frac{5184}{125} + \frac{4096}{216} + \frac{729}{64} + 16

A Z I (H_{15}) \geq (s - 6) {(\frac{s - 3}{s - 4})}^{3} + 128 {(\frac{s - 3}{s - 1})}^{3} + 27 {(\frac{s - 3}{s - 2})}^{3} + \frac{4096}{216} + \frac{1728}{125} + 32

A Z I (H_{16}) \geq (s - 6) {(\frac{s - 3}{s - 4})}^{3} + 64 {(\frac{s - 3}{s - 1})}^{3} + 27 {(\frac{s - 3}{s - 2})}^{3} + \frac{4096}{216} + \frac{3456}{- 125} + 32

A Z I (H_{17}) \geq (s - 6) {(\frac{s - 3}{s - 4})}^{3} + 81 {(\frac{s - 3}{s - 2})}^{3} + \frac{2187}{32}

A Z I (H_{18}) \geq (s - 6) {(\frac{s - 4}{s - 5})}^{3} + 64 {(\frac{s - 4}{s - 2})}^{3} + 27 {(\frac{s - 4}{s - 3})}^{3} + \frac{6912}{125} + \frac{4096}{216} + 16

A Z I (H_{19}) \geq (s - 6) {(\frac{s - 3}{s - 4})}^{3} + 128 {(\frac{s - 3}{s - 1})}^{3} + \frac{4096}{216} + \frac{3456}{125} + 32

A Z I (H_{20}) \geq (s - 6) {(\frac{s - 2}{s - 3})}^{3} + 64 {(\frac{s - 2}{s})}^{3} + 54 {(\frac{s - 2}{s - 1})}^{3} + \frac{3456}{125} + 32

A Z I (H_{21}) \geq (s - 6) {(\frac{s - 4}{s - 5})}^{3} + 54 {(\frac{s - 4}{s - 3})}^{3} + \frac{6912}{125} + \frac{2187}{64} + 32

A Z I (H_{22}) \geq (s - 6) {(\frac{s - 2}{s - 3})}^{3} + 108 {(\frac{s - 2}{s - 1})}^{3} + \frac{2187}{64} + 16

A Z I (H_{23}) \geq (s - 6) {(\frac{s - 3}{s - 4})}^{3} + 64 {(\frac{s - 3}{s - 1})}^{3} + 27 {(\frac{s - 3}{s - 2})}^{3} + \frac{5184}{125} + \frac{1458}{64} + 16

A Z I (H_{24}) \geq (s - 6) {(\frac{s - 3}{s - 4})}^{3} + 64 {(\frac{s - 3}{s - 1})}^{3} + 54 {(\frac{s - 3}{s - 2})}^{3} + \frac{5184}{125} + \frac{729}{64} + 16

Therefore, we conclude that

A Z I (H_{i}) > (s - 7) {(\frac{s - 2}{s - 3})}^{3} + 80

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 $A Z I (G)$ in the class of connected 4-cyclic graphs. Also, the unique extremal graph attaining this minimum value of $A Z I (G)$ has been characterized. The authors feel that it would be interesting to find the same characterization of $A Z I (G)$ in the class of k-cyclic with $k \geq 5$ graphs. Another possible extension would be to find a possible ordering of graphs on the basis of minimum values of $A Z I (G)$ .

Footnotes

Acknowledgement

The authors are highly indebted to the anonymous referees whose valuable comments greatly helped in improving the earlier version of the research paper.

Authors’ contributions

All authors contributed equally to the paper from problem formulation, research work, and paper write up.

Declaration of conflicting interests

The authors declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The authors received no financial support for the research, authorship, and/or publication of this article.

ORCID iD

M. Tariq Rahim

References

Sarkar

Pal

. On some topological indices and their importance in chemical sciences: a comparative study. Eur Phys J Plus 2022; 137. doi:https://doi.org/10.1140/epjp/s13360-022-02431-1

Furtula

Graovac

Vukičević

. Augmented Zagreb index. J Math Chem 2010; 48: 370–380.

Huang

Liu

Gan

. Augmented Zagreb index of connected graphs. MATCH Commun Math Comput Chem 2012; 67: 483–494.

Wang

Huang

Liu

. Bounds on augmented Zagreb index. MATCH Commun Math Comput Chem 2012; 68: 209–216.

Ali

Raza

Bhatti

. On the augmented Zagreb index. arXiv preprint. 2014;1402.3078. doi:https://doi.org/10.48550/arXiv.1402.3078

Zhan

Qiao

Cai

. Unicyclic and bicyclic graphs with minimal augmented Zagreb index. J Inequal Appl 2015; 2015: 1–12.

Ali

Furtula

Gutman

, et al. Augmented Zagreb index: extremal results and bounds. MATCH Commun Math Comput Chem 2021; 67: 483–494.

Ali

. A note on minimal augmented Zagreb index of tricyclic graphs of fixed order. MATCH Commun Math Comput Chem 2021; 85: 247–256.

Qingcu

Wen

Renqian

, et al. Bounds for the augmented Zagreb index. Theory Appl Graphs 2023; 10: 1–10.

10.

Liu

Pang

Belardo

, et al. The k-apex trees with minimum augmented Zagreb index. Discrete Math 2023; 346. doi:https://doi.org/10.1016/j.disc.2023.113390