Albertson index

Short description: Graph invariant measuring irregularity

Not to be confused with Albertson conjecture.

File:Albertson index.svg

The vertices are labeled by their degree, and the edges by their imbalance, the difference of the degrees of the vertices incident to them. The Albertson index $\mathrm{Alb}(G)$ of a graph $G$ is the sum of the imbalances of all edges.

The Albertson index (also known as irregularity or Albertson irregularity index) is a graph invariant that measures the irregularity of a graph by summing the imbalances of all its edges. It was introduced by Michael O. Albertson in 1997 as a single parameter to capture how "non-regular" a graph is.

Definition

For a simple undirected graph $G=(V,E)$, the imbalance of an edge $e=u,v$ is defined as:

$\mathrm{imb}(e)=|\mathrm{deg}(u)-\mathrm{deg}(v)|$

where $\mathrm{deg}(u)$ and $\mathrm{deg}(v)$ denote the degrees of vertices $u$ and $v$.

The Albertson index of $G$, denoted $\mathrm{Alb}(G)$ (sometimes $\mathrm{I}(G)$ or $\mathrm{irr}(G)$ in the literature), is the sum of the imbalances of all edges:

$\mathrm{Alb}(G)=\sum _{uv\in E(G)}|\mathrm{deg}(u)-\mathrm{deg}(v)|$

A graph is regular if and only if its Albertson index is zero.

Properties and bounds

The Albertson index is always an even integer. For a graph with $n$ vertices, the index is bounded by $O(n^3)$.

Maximum irregularity

The maximum Albertson index over all graphs with $n$ vertices is less than $\frac{4n^3}{27}$, and this bound is tight. The extremal graphs that approach this bound are of the form $H_{r,n}=K_r\vee \bar{K}n-r$, the join of a complete graph $K_r$ and an independent set $\bar{K}n-r$, where $r$ is approximately $n/3$.

A graph $G$ is called critical if adding or removing any single edge does not increase its Albertson index. Albertson proved that a graph is critical if and only if it is of the form $H_{r,n}$ for some $r\le \frac{n}{3}$, a result used to establish the general upper bound.

For specific classes of graphs, tighter bounds exist:

If $G$ is bipartite, then

$\mathrm{Alb}(G)\le \frac{2n^3}{27}$.

The irregularity of a complete bipartite graph $K_{t,n-t}$ is $t(n-t)(n-2t)$.

If $G$ is triangle-free, then

$\mathrm{Alb}(G)<\frac{4n^3}{27}$.

Extremal trees

Among all trees with $n$ vertices, the Albertson index is bounded by:

$2\le \mathrm{Alb}(T)\le (n-1)(n-2)$

The lower bound of 2 is achieved exclusively by the path graph $P_n$, while the upper bound is achieved exclusively by the star graph $K_{1,n-1}$.

Minimal irregularity

While the star graph maximizes irregularity for trees, the minimal irregularity for certain graph classes has also been studied. For a connected graph $G$ with $k$ pendant vertices, a general lower bound is $\mathrm{Alb}(G)\ge 2k$.

Related concepts and generalizations

Total irregularity

A related measure, the total irregularity, was introduced by Abdo, Brandt, and Dimitrov. It is defined as the sum of absolute degree differences over all pairs of vertices, not just adjacent ones:

$\mathrm{irr}t(G)=\frac{1}{2}\sum u,v\in V(G)|\mathrm{deg}(u)-\mathrm{deg}(v)|$

Unlike the Albertson index, the total irregularity depends only on the degree sequence of a graph, not its specific edge structure.

Generalized Albertson index

A generalization was introduced by Lin, Zhou, Wang, and Miao in 2022. The general Albertson index (or $p$-Albertson index) is defined as:

$A_p(G)={(\sum _{uv\in E(G)}|\mathrm{deg}(u)-\mathrm{deg}(v){|}^p)}^{1/p}$

where $p$ is a positive real number. This reduces to the classical Albertson index for $p=1$. For $p=2$, its square $A_2^2(G)$ is known as the $\sigma$-index and is related to the Zagreb indices and the forgotten topological index. The extremal trees for the $p$-Albertson index remain the path graph (minimum) and the star graph (maximum).

Applications and connections

The Albertson index has applications in mathematical chemistry for predicting physicochemical properties of molecules in QSAR/QSPR modeling. In network science, it provides a quantitative measure of network heterogeneity.

The concept is also connected to other graph theoretical topics, such as stepwise irregular graphs, where every edge has an imbalance of exactly 1, and the imbalance conjecture, which studies whether sequences of edge imbalances can form a valid degree sequence of some graph.

See also

• Degree sequence
• Graph invariant
• Regular graph
• Topological index
• Zagreb indices