Harmonic index


The harmonic index is a topological index based on the degrees of vertices in a graph. Introduced by Fajtlowicz in 1987, 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 with vertex set and edge set, the harmonic index is defined as:
where and denote the degrees of vertices and respectively, and the sum is taken over all edges in.

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 as the edge weight, the harmonic index uses the harmonic mean of the endpoint degrees.
The harmonic index is also related to the inverse degree of a graph:

Properties

Bounds

For a connected graph with vertices, edges, maximum degree, minimum degree, and pendant edges:
Lower bound:
Equality holds if and only if is the star graph, a regular graph, or a -semiregular graph.
Upper bounds: Various upper bounds have been established for specific graph classes. For example, for trees:
  • For any tree of order :, with equality if and only if is the path graph
  • For any tree of order :, with equality if and only if is the star graph

    Extremal graphs

Among all connected graphs with vertices:
  • The complete graph maximizes the harmonic index
  • The path graph maximizes the harmonic index among trees
  • The star graph has the minimum harmonic index among trees
For unicyclic graphs of order :
  • The cycle achieves the maximum value:
  • The graph achieves the minimum value

    Harmonic polynomial

The harmonic polynomial of a graph is defined as:
This polynomial is named for its relationship to the harmonic index:
The harmonic polynomial is also related to the first Zagreb polynomial
by the equality:

Values for specific graphs

For several common graph families, the harmonic index has closed-form expressions:
Recent work has established connections between the harmonic index and Hamiltonian properties of graphs:
Theorem : Let be a -connected graph with vertices and edges, where and. If
where, then is Hamiltonian.
A similar result holds for traceable graphs with and.

Operations on graphs

The harmonic index has been studied extensively for various graph operations:

Cartesian product

For graphs and, the harmonic index of their Cartesian product satisfies:

Other products

Similar results have been established for:
The harmonic index exhibits predictable behavior under certain graph operations:
  • Edge separation: If is a cut edge with both components having at least two vertices, contracting 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: for any pendant vertex.

    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, the harmonic index has proven useful for correlating molecular structure with biological activity and physical properties.
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.

Computational complexity

The harmonic index can be computed in time for a graph with edges, since it requires only a single pass through all edges. An algorithm for computing the harmonic polynomial has been developed.