Harmonic index

Vertices are labeled by their degree. The edges in the graph are labeled 2 divided by the sum of the degrees of vertices incident to it. The Harmonic index is the sum of these edge labels.

The harmonic index is a topological index based on the degrees of vertices in a graph. Introduced by Fajtlowicz in 1987, ^[1] it has become an important descriptor in chemical graph theory and has been extensively studied for its mathematical properties and applications.

Definition

For a simple connected graph ${\displaystyle G=(V,E)}$ with vertex set ${\displaystyle V}$ and edge set ${\displaystyle E}$, the harmonic index ${\displaystyle H(G)}$ is defined as:

${\displaystyle \displaystyle H(G)=\sum _{uv\in E(G)}{\frac {2}{d(u)+d(v)}}}$

where ${\displaystyle d(u)}$ and ${\displaystyle d(v)}$ denote the degrees of vertices ${\displaystyle u}$ and ${\displaystyle v}$ respectively, and the sum is taken over all edges ${\displaystyle uv}$ in ${\displaystyle G}$. ^[2]

Relationship to other indices

The harmonic index is closely related to the Randić index and can be considered as one of its variants. While the Randić index uses ${\displaystyle (d(u)\cdot d(v))^{-1/2}}$ as the edge weight, the harmonic index uses the harmonic mean of the endpoint degrees. ^[2]

The harmonic index is also related to the inverse degree of a graph:

${\displaystyle \displaystyle ID(G)=\sum _{u\in V(G)}{\frac {1}{d(u)}}}$

Properties

Bounds

For a connected graph ${\displaystyle G}$ with ${\displaystyle n}$ vertices, ${\displaystyle m}$ edges, maximum degree ${\displaystyle \Delta }$, minimum degree ${\displaystyle \delta }$, and ${\displaystyle p}$ pendant edges:

Lower bound: ^[2]

${\displaystyle \displaystyle H(G)\geq {\frac {2p}{\Delta +1}}+{\frac {m-p}{\Delta }}}$

Equality holds if and only if ${\displaystyle G}$ is the star graph ${\displaystyle K_{1,n-1}}$, a regular graph, or a ${\displaystyle (\Delta ,1)}$-semiregular graph.

Upper bounds: Various upper bounds have been established for specific graph classes. For example, for trees: ^[3]

• For any tree ${\displaystyle T}$ of order ${\displaystyle n\geq 3}$: ${\displaystyle H(T)\leq H(P_{n})={\frac {n-3}{4}}+{\frac {4}{3}}}$, with equality if and only if ${\displaystyle T}$ is the path graph ${\displaystyle P_{n}}$
• For any tree ${\displaystyle T}$ of order ${\displaystyle n\geq 3}$: ${\displaystyle H(T)\geq H(S_{n})={\frac {2(n-1)}{n}}}$, with equality if and only if ${\displaystyle T}$ is the star graph ${\displaystyle S_{n}}$

Extremal graphs

Among all connected graphs with ${\displaystyle n}$ vertices: ^[3]

• The complete graph ${\displaystyle K_{n}}$ maximizes the harmonic index
• The path graph ${\displaystyle P_{n}}$ maximizes the harmonic index among trees
• The star graph ${\displaystyle S_{n}}$ has the minimum harmonic index among trees

For unicyclic graphs of order ${\displaystyle n}$: ^[4]

• The cycle ${\displaystyle C_{n}}$ achieves the maximum value: ${\displaystyle H(C_{n})=n/2}$
• The graph ${\displaystyle S(n-2,1,1)}$ achieves the minimum value

Harmonic polynomial

The harmonic polynomial of a graph ${\displaystyle G}$ is defined as: ^[5]

${\displaystyle \displaystyle H(G,x)=\sum _{uv\in E(G)}x^{d(u)+d(v)-1}}$

This polynomial is named for its relationship to the harmonic index:

${\displaystyle \displaystyle H(G)=2\int _{0}^{1}H(G,x)\,dx}$

The harmonic polynomial is also related to the first Zagreb polynomial

${\displaystyle M_{1}(G,x)=\sum _{uv\in E}x^{d(u)+d(v)}}$

by the equality:

${\displaystyle M_{1}(G,x)=x\cdot H(G,x)}$. ^[6]

Values for specific graphs

For several common graph families, the harmonic index has closed-form expressions: ^{[2] [6]}

• Complete graph ${\displaystyle K_{n}}$: ${\displaystyle H(K_{n})={\frac {n}{2}}}$
• Cycle graph ${\displaystyle C_{n}}$: ${\displaystyle H(C_{n})={\frac {n}{2}}}$
• Path graph ${\displaystyle P_{n}}$: ${\displaystyle H(P_{n})={\frac {n-3}{4}}+{\frac {4}{3}}}$ for ${\displaystyle n\geq 3}$
• Star graph ${\displaystyle S_{n}}$: ${\displaystyle H(S_{n})={\frac {2(n-1)}{n}}}$
• Complete bipartite graph ${\displaystyle K_{n_{1},n_{2}}}$: ${\displaystyle H(K_{n_{1},n_{2}})={\frac {2n_{1}n_{2}}{n_{1}+n_{2}}}}$
• Hypercube graph ${\displaystyle Q_{n}}$: ${\displaystyle H(Q_{n})=2^{n-1}}$

Hamiltonian properties

Recent work has established connections between the harmonic index and Hamiltonian properties of graphs: ^[7]

Theorem (Li, 2024): Let ${\displaystyle G}$ be a ${\displaystyle k}$-connected graph with ${\displaystyle n}$ vertices and ${\displaystyle e}$ edges, where ${\displaystyle k\geq 2}$ and ${\displaystyle n\geq 3}$. If

${\displaystyle \displaystyle H(G)\geq {\frac {(\delta +\Delta )^{2}}{2M\delta \Delta }}\cdot e^{2}}$

where ${\displaystyle M=(k+1)\delta ^{2}+{\frac {e^{2}}{n-(k+1)}}}$, then ${\displaystyle G}$ is Hamiltonian.

A similar result holds for traceable graphs with ${\displaystyle k\geq 1}$ and ${\displaystyle n\geq 9}$. ^[7]

Operations on graphs

The harmonic index has been studied extensively for various graph operations: ^[6]

Cartesian product

For graphs ${\displaystyle G_{1}}$ and ${\displaystyle G_{2}}$, the harmonic index of their Cartesian product satisfies:

${\displaystyle \displaystyle H(G_{1}\times G_{2})\geq {\frac {1}{2}}H(G_{1})ID(G_{2})+{\frac {1}{2}}H(G_{2})ID(G_{1})}$

Other products

Similar results have been established for:

• Corona product
• Join of graphs
• Cartesian sum
• Lexicographic product

Graph perturbations

The harmonic index exhibits predictable behavior under certain graph operations: ^[2]

• Edge separation: If ${\displaystyle e=uv}$ is a cut edge with both components having at least two vertices, contracting ${\displaystyle e}$ and adding a pendant edge decreases the harmonic index.
• Edge grafting: Moving pendant paths to concentrate at a single vertex generally increases the harmonic index.
• Vertex deletion: Removing a pendant vertex strictly decreases the harmonic index: ${\displaystyle H(G)>H(G-v)}$ for any pendant vertex ${\displaystyle v}$.

Applications

The harmonic index has found applications in chemical graph theory, where it serves as a molecular descriptor for predicting physicochemical properties of chemical compounds. In QSAR/QSPR studies (quantitative structure-activity and structure-property relationships), the harmonic index has proven useful for correlating molecular structure with biological activity and physical properties. ^[2]

The harmonic index has also been applied to network analysis, where it helps measure connectivity and structural properties of various types of networks. Its mathematical properties, particularly its relationship to vertex degrees and its behavior under graph operations, make it a useful tool for understanding graph structure in both theoretical and applied contexts. ^[6]

Computational complexity

The harmonic index can be computed in ${\displaystyle O(m)}$ time for a graph with ${\displaystyle m}$ edges, since it requires only a single pass through all edges. An ${\displaystyle O(n^{2})}$ algorithm for computing the harmonic polynomial has been developed. ^[6]

See also

• Randić index
• Zagreb indices
• Topological index
• Chemical graph theory
• Wiener index

References

1. Fajtlowicz, S. (1987). "On conjectures of Graffiti-II". Congressus Numerantium. 60: 187–197.
2. Li, Jianxi; Shiu, Wai Chee (2014). "The harmonic index of a graph". Rocky Mountain Journal of Mathematics. 44 (5): 1607–1620. doi: 10.1216/RMJ-2014-44-5-1607 .
3. Zhong, L. (2012). "The harmonic index on graphs". Applied Mathematics Letters. 25 (3): 561–566. doi:10.1016/j.aml.2011.09.059.
4. Zhong, L. (2012). "The harmonic index on unicyclic graphs" (PDF). Ars Combinatoria. 104: 261–269.
5. Iranmanesh, M. A.; Saheli, M. (2014). "On the harmonic index and harmonic polynomial of Caterpillars with diameter four". Iranian Journal of Mathematical Chemistry. 5 (1): 35–43. doi: 10.22052/ijmc.2015.9044 .
6. Hernández-Gómez, Juan C.; Méndez-Bermúdez, J. A.; Rodríguez, José M.; Sigarreta, José M. (2018). "Harmonic index and harmonic polynomial on graph operations". Symmetry. 10 (10): 456. doi: 10.3390/sym10100456 .
7. Li, Rao (2024). "The harmonic index and some Hamiltonian properties of graphs" (PDF). Discrete Mathematics Letters. 14: 103–107. doi: 10.47443/dml.2024.147 .