Zagreb indices

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

Definition

For a graph ${\displaystyle G}$ with vertex set ${\displaystyle V(G)}$ and edge set ${\displaystyle E(G)}$, the first Zagreb index ${\displaystyle M_{1}}$ and second Zagreb index ${\displaystyle M_{2}}$ are defined as:

${\displaystyle M_{1}(G)=\sum _{v\in V(G)}d_{v}^{2}}$

${\displaystyle M_{2}(G)=\sum _{uv\in E(G)}d_{u}d_{v}}$

where ${\displaystyle d_{v}}$ denotes the degree of vertex ${\displaystyle v}$.

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

${\displaystyle 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:^[3][4]

For the complete graph ${\displaystyle K_{n}}$:

${\displaystyle M_{1}(K_{n})=n(n-1)}$

${\displaystyle M_{2}(K_{n})={\frac {n(n-1)(n-2)}{2}}}$

For the path graph ${\displaystyle P_{n}}$ with ${\displaystyle n\geq 3}$:

${\displaystyle M_{1}(P_{n})=4n-6}$

${\displaystyle M_{2}(P_{n})=4n-8}$

For the cycle graph ${\displaystyle C_{n}}$ with even ${\displaystyle n\geq 4}$:

${\displaystyle M_{1}(C_{n})=4n}$

${\displaystyle M_{2}(C_{n})=4n}$

For the star graph ${\displaystyle S_{n}}$:

${\displaystyle M_{1}(S_{n})=(n-1)^{2}+(n-1)}$

${\displaystyle M_{2}(S_{n})=(n-1)^{2}}$

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

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

For the kite graph ${\displaystyle Ki_{n,n-1}}$ (a complete graph ${\displaystyle K_{n-1}}$ with one pendant edge):

${\displaystyle M_{1}(Ki_{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 ${\displaystyle G}$ with ${\displaystyle n}$ vertices and ${\displaystyle m}$ edges:

${\displaystyle M_{1}(G)\geq {\frac {4m^{2}}{n}}}$

with equality if and only if ${\displaystyle G}$ is a regular graph.^[4]

More refined bounds involving the maximum degree ${\displaystyle \Delta }$ and minimum degree ${\displaystyle \delta }$ have also been established.^[4]

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

${\displaystyle 2M_{2}(G)-\Delta ^{2}\delta \geq {\frac {(n-1)(M_{1}(G)-\Delta ^{2})^{2}}{(2m-\delta )(n-1)+(\Delta -\delta )[n(n-1)-2m]}}}$

with equality if and only if ${\displaystyle 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 ${\displaystyle \pi }$-electron energy on molecular structure.^[1] In their original paper, they showed that these graph invariants appear in an approximate formula for the total ${\displaystyle \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.^[2]

The Zagreb indices and their variants have been extensively studied, with the original papers cited over 1000 times.^[5] 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 ${\displaystyle \alpha }$:^[5]

${\displaystyle M_{1}^{(\alpha )}(G)=\sum _{v\in V(G)}d_{v}^{\alpha }}$

${\displaystyle M_{2}^{(\alpha )}(G)=\sum _{uv\in E(G)}[d_{u}d_{v}]^{\alpha }}$

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

Forgotten topological index

The forgotten topological index or F-index corresponds to ${\displaystyle M_{1}^{(3)}}$:^[5]

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

This index was introduced in the original 1972 paper^[1] 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 ${\displaystyle ZC_{1}^{*}}$, replaces vertex degrees with vertex connection numbers:^[2]

${\displaystyle ZC_{1}^{*}(G)=\sum _{v\in V(G)}d_{v}\tau _{v}}$

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

This index can be equivalently expressed as:

${\displaystyle ZC_{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:

${\displaystyle ZC_{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.^[6]

Two vertices ${\displaystyle 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 ${\displaystyle u}$, denoted ${\displaystyle d_{vv}(u)}$, is the number of vertices vv-adjacent to ${\displaystyle u}$. Note that ${\displaystyle d(u)\leq d_{vv}(u)}$ for every vertex, with equality if and only if every block of ${\displaystyle G}$ is complete.^[6]

The first vv-Zagreb index is defined as:

${\displaystyle VVM_{1}(G)=\sum _{u\in V(G)}d_{vv}(u)^{2}}$

This can also be expressed as:

${\displaystyle VVM_{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.^[7] The reverse degree of a vertex ${\displaystyle u\in V(G)}$ is defined as:

${\displaystyle c_{u}=\Delta -d_{u}+1}$

where ${\displaystyle \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:^[7]

${\displaystyle CM_{1}(G)=\sum _{uv\in E(G)}(c_{u}+c_{v})}$

${\displaystyle CM_{2}(G)=\sum _{uv\in E(G)}c_{u}\cdot c_{v}}$

Additionally, hyper reverse Zagreb indices are defined as:

${\displaystyle HCM_{1}(G)=\sum _{uv\in E(G)}(c_{u}+c_{v})^{2}}$

${\displaystyle HCM_{2}(G)=\sum _{uv\in E(G)}(c_{u}\cdot c_{v})^{2}}$

Other variants

Numerous other variants have been proposed, including:^[5]

• Hyper-Zagreb index: ${\displaystyle 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 ${\displaystyle d(u)-1}$ instead of ${\displaystyle d(u)}$
• Zagreb coindices: Summing over non-adjacent vertex pairs
• Zagreb root-indices: Using the roots of graph polynomials^[8]