Zagreb indices
.
≈ 4 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
. 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.
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) 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 \geq 3 : M_1(P_n) = 4n - 6 M_2(P_n) = 4n - 8 For the cycle graph C_n with even n \geq 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 Ki_{n,n-1} (a complete graph K_{n-1} with one pendant edge): M_1(Ki_{n,n-1}) = n^3 - 5n^2 + 10n - 6 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. 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.
ZC_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: 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: ZC_1^*(G) = 2M_2(G) - M_1(G) VVM_1(G) = \sum_{u \in V(G)} d_{vv}(u)^2 This can also be expressed as: VVM_1(G) = \sum_{u \text{ vv-adj } w} d_{vv}(u) + d_{vv}(w) c_u = \Delta - d_u + 1 where \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: CM_1(G) = \sum_{uv \in E(G)} (c_u + c_v) CM_2(G) = \sum_{uv \in E(G)} c_u \cdot c_v Additionally, hyper reverse Zagreb indices are defined as: HCM_1(G) = \sum_{uv \in E(G)} (c_u + c_v)^2 HCM_2(G) = \sum_{uv \in E(G)} (c_u \cdot c_v)^2 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
Text derived from https://en.wikipedia.org/w/index.php?oldid=1328584059 under CC BY-SA 4.0; modifications have been made.