Albertson index

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.^[1]

Not to be confused with Albertson conjecture.

Definition

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

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

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

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

${\displaystyle \operatorname {Alb} (G)=\sum _{uv\in E(G)}|\deg(u)-\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 ${\displaystyle n}$ vertices, the index is bounded by ${\displaystyle O(n^{3})}$.^[1]

Maximum irregularity

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

A graph ${\displaystyle 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 ${\displaystyle H_{r,n}}$ for some ${\displaystyle r\leq {\frac {n}{3}}}$, a result used to establish the general upper bound.^[1]

For specific classes of graphs, tighter bounds exist:

If ${\displaystyle G}$ is bipartite, then

${\displaystyle \operatorname {Alb} (G)\leq {\frac {2n^{3}}{27}}}$.

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

If ${\displaystyle G}$ is triangle-free, then

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

Extremal trees

Among all trees with ${\displaystyle n}$ vertices, the Albertson index is bounded by:

${\displaystyle 2\leq \operatorname {Alb} (T)\leq (n-1)(n-2)}$

The lower bound of 2 is achieved exclusively by the path graph ${\displaystyle P_{n}}$, while the upper bound is achieved exclusively by the star graph ${\displaystyle K_{1,n-1}}$.^[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 ${\displaystyle G}$ with ${\displaystyle k}$ pendant vertices, a general lower bound is ${\displaystyle \operatorname {Alb} (G)\geq 2k}$.^[2]

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:^[3]

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

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

Generalized Albertson index

A generalization was introduced by Lin, Zhou, Wang, and Miao in 2022. The general Albertson index (or ${\displaystyle p}$-Albertson index) is defined as:^[4]

${\displaystyle A_{p}(G)=\left(\sum _{uv\in E(G)}|\deg(u)-\deg(v)|^{p}\right)^{1/p}}$

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

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,^[5] and the imbalance conjecture, which studies whether sequences of edge imbalances can form a valid degree sequence of some graph.^[6]

See also

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