Chemistry:Zagreb indices

Short description: Topological indices in chemical graph theory

Vertices are labeled by their degree. The edges in the first graph are labeled by the sum of the degrees of vertices incident to it, and likewise for the second, but with the product rather than sum of vertices. The first and second Zagreb indices respectively are the sums of these edge labels.

The Zagreb indices are among the oldest topological indices in chemical graph theory, introduced in 1972 by Ivan Gutman and Nenad Trinajstić. These graph invariants were originally developed to study the structure-dependency of total $\pi$-electron energy in conjugated molecules and have since become widely used in QSAR/QSPR studies.

Definition

For a graph $G$ with vertex set $V(G)$ and edge set $E(G)$, the first Zagreb index $M_1$ and second Zagreb index $M_2$ are defined as:

$M_1(G)=\sum _{v\in V(G)}{d}_v^2$

$M_2(G)=\sum _{uv\in E(G)}{d}_u{d}_v$

where $d_v$ denotes the degree of vertex $v$.

The first Zagreb index can also be expressed in an equivalent edge-based form:

$M_1(G)=\sum _{uv\in E(G)}(d_u+d_v)$

Values for specific graph families

Explicit formulas for the Zagreb indices have been computed for various graph families:

For the complete graph $K_n$:

$M_1(K_n)=n(n-1)$

$M_2(K_n)=\frac{n(n-1)(n-2)}{2}$

For the path graph $P_n$ with $n\ge 3$:

$M_1(P_n)=4n-6$

$M_2(P_n)=4n-8$

For the cycle graph $C_n$ with even $n\ge 4$:

$M_1(C_n)=4n$

$M_2(C_n)=4n$

For the star graph $S_n$:

$M_1(S_n)=(n-1{)}^2+(n-1)$

$M_2(S_n)=(n-1{)}^2$

For the graph $K_{2,n-2}^{*}$ (the complete bipartite graph $K_{2,n-2}$ but with an edge added between the two vertices of degree $n-2$):

$M_1(K_{2,n-2}^{*})=2(n-1{)}^2+4(n-2)$

For the kite graph $K{i}_{n,n-1}$ (a complete graph $K_{n-1}$ with one pendant edge):

$M_1(K{i}_{n,n-1})=n^3-5n^2+10n-6$

Bounds

Sharp bounds have been established for the Zagreb indices in terms of basic graph parameters.

For a graph $G$ with $n$ vertices and $m$ edges:

$M_1(G)\ge \frac{4m^2}{n}$

with equality if and only if $G$ is a regular graph.

More refined bounds involving the maximum degree $\mathrm{\Delta }$ and minimum degree $\delta$ have also been established.

Das, Xu, and Nam established a fundamental relationship between the first and second Zagreb indices:

$2M_2(G)-{\mathrm{\Delta }}^2\delta \ge \frac{(n-1)(M_1(G)-{\mathrm{\Delta }}^2{)}^2}{(2m-\delta )(n-1)+(\mathrm{\Delta }-\delta )[n(n-1)-2m]}$

with equality if and only if $G$ is regular. This inequality provides a way to bound one Zagreb index in terms of the other.

History and motivation

The Zagreb indices were introduced by Gutman and Trinajstić in 1972 while investigating the dependence of total $\pi$-electron energy on molecular structure. In their original paper, they showed that these graph invariants appear in an approximate formula for the total $\pi$-electron energy of alternant hydrocarbons. The indices were named after the city of Zagreb, Croatia, where much of the early work on these invariants was conducted.

In the same 1972 paper, Gutman and Trinajstić also introduced a related invariant involving vertex connection numbers (the number of vertices at distance 2 from a given vertex), though this particular modification received less attention in subsequent research.

The Zagreb indices and their variants have been extensively studied, with the original papers cited over 1000 times. They are used in chemical graph theory for modeling physicochemical properties of chemical compounds, QSAR (quantitative structure-activity relationship) and QSPR (quantitative structure-property relationship) studies, and predicting various molecular properties.

Related indices

General Zagreb indices

The Zagreb indices can be generalized by introducing a parameter $\alpha$:

$M_1^{(\alpha )}(G)=\sum _{v\in V(G)}{d}_v^{\alpha }$

$M_2^{(\alpha )}(G)=\sum _{uv\in E(G)}[d_u{d}_v{]}^{\alpha }$

where $\alpha$ is a real number. For $\alpha =2$ and $\alpha =1$ respectively, these reduce to the classical Zagreb indices. Special cases of the general Zagreb indices include the Randić index (for $\alpha =-1/2$ in $M_2^{(\alpha )}$) and the forgotten topological index.

Forgotten topological index

The forgotten topological index or F-index corresponds to $M_1^{(3)}$:

$F(G)=\sum _{v\in V(G)}{d}_v^3$

This index was introduced in the original 1972 paper but remained largely unstudied until 2015 when its applications in QSPR were recognized.

Modified first Zagreb connection index

A modification of the first Zagreb index, called the modified first Zagreb connection index and denoted $Z{C}_1^{*}$, replaces vertex degrees with vertex connection numbers:

$Z{C}_1^{*}(G)=\sum _{v\in V(G)}{d}_v{\tau }_v$

where ${\tau }_v$ is the connection number of vertex $v$ (the number of vertices at distance 2 from $v$). This invariant also appeared in the original 1972 paper by Gutman and Trinajstić as influencing total $\pi$-electron energy, though it was not extensively studied until more recently.

This index can be equivalently expressed as:

$Z{C}_1^{*}(G)=\sum _{uv\in E(G)}({\tau }_u+{\tau }_v)$

For triangle-free and quadrangle-free graphs, there is a simple relationship between this index and the Zagreb indices:

$Z{C}_1^{*}(G)=2M_2(G)-M_1(G)$

vv-Zagreb index

The concept of vv-degree (vertex-vertex degree) provides another way to generalize Zagreb indices by considering block structures in graphs.

Two vertices $u,w\in V(G)$ are said to be vv-adjacent if they are incident on the same block. The vv-degree of a vertex $u$, denoted $d_{vv}(u)$, is the number of vertices vv-adjacent to $u$. Note that $d(u)\le d_{vv}(u)$ for every vertex, with equality if and only if every block of $G$ is complete.

The first vv-Zagreb index is defined as:

$VV{M}_1(G)=\sum _{u\in V(G)}{d}_{vv}(u{)}^2$

This can also be expressed as:

$VV{M}_1(G)=\sum _{u\text{ vv-adj }w}{d}_{vv}(u)+d_{vv}(w)$

Reverse Zagreb indices

The reverse Zagreb indices were introduced by Kulli in 2018 and are based on the reverse degree of vertices. The reverse degree of a vertex $u\in V(G)$ is defined as:

$c_u=\mathrm{\Delta }-d_u+1$

where $\mathrm{\Delta }=\max d_u:u\in V(G)$ is the maximum degree in the graph.

The first reverse Zagreb index and second reverse Zagreb index are defined as:

$C{M}_1(G)=\sum _{uv\in E(G)}(c_u+c_v)$

$C{M}_2(G)=\sum _{uv\in E(G)}{c}_u\cdot c_v$

Additionally, hyper reverse Zagreb indices are defined as:

$HC{M}_1(G)=\sum _{uv\in E(G)}(c_u+c_v{)}^2$

$HC{M}_2(G)=\sum _{uv\in E(G)}(c_u\cdot c_v{)}^2$

Other variants

Numerous other variants have been proposed, including:

• Hyper-Zagreb index: $HM(G)=\sum _{uv\in E(G)}[d_u+d_v{]}^2$
• Reformulated Zagreb indices: Defined using edge degrees instead of vertex degrees
• Reduced Zagreb indices: Using $d(u)-1$ instead of $d(u)$
• Zagreb coindices: Summing over non-adjacent vertex pairs
• Zagreb root-indices: Using the roots of graph polynomials