The general Albertson irregularity index of graphs

1.   Introduction

Let $G$ be a simple undirected connected graph with the vertex set $V(G)$ and the edge set $E(G)$. For $v\in V(G)$, $N(v)$ denotes the set of all neighbors of $v$, and $d(v) = |N(v)|$ denotes the degree of vertex $v$ in $G$. The minimum and the maximum degree of $G$ are denoted by $\delta(G)$ and $\Delta(G)$, or simply $\delta$ and $\Delta$, respectively. A pendant vertex of $G$ is a vertex of degree one. A graph $G$ is called $(\Delta, \delta)$-semiregular if $\{d(u), d(v)\} = \{\Delta, \delta\}$ holds for all edges $uv\in E(G)$. Denote by $P_n$ and $K_{1, \, n-1}$ the path and the star with $n$ vertices, respectively.

In 1997, the Albertson irregularity index of a connected graph $G$, introduced by Albertson ^[1], is defined as

This index has been of interest to mathematicians, chemists and scientists from related fields due to the fact that the Albertson irregularity index plays a major role in irregularity measures of graphs ^[3,4,7,8,17], predicting the biological activities and properties of chemical compounds in the QSAR/QSPR modeling ^[12,24] and the quantitative characterization of network heterogeneity ^[9]. By the natural extension of the Albertson irregularity index, Gutman et al., ^[13] recently proposed the $\sigma$-index as follows:

where $F$ and $M_2$ are well-known the forgotten topological index and the second Zagreb index of a graph $G$, respectively. Recently, the $\sigma$-index of a connected graph $G$ is studied, such as the characterization of extremal graphs ^[5] and mathematical relations between the $\sigma$-index and other graph irregularity indices ^[21].

The generalization of topological index is a trend of mathematical chemistry in recent years. Many classical topological indices are generalized, such as the general Randić index ^[6], the first general Zagreb index ^[18], the general sum-connectivity index ^[31], the general eccentric connectivity index ^[28], etc. Motivated by this fact, we propose the general Albertson irregularity index of a graph $G$ as follows:

where $p$ is a positive real number. Evidently, $A_1(G) = Alb(G)$ and $A_2^2(G) = \sigma(G)$. The other motivation is that the topological index formed from distance function of the degree of vertex has attracted extensive attention of scholars. In 2021, Gutman ^[10] proposed the Sombor index of a graph $G$ and defined it as $SO(G) = \sum_{uv\in E(G)}\sqrt{d^2(u)+d^2(v)}$, which is the Euclidean norm of $d(u)$ and $d(v)$. According to Gutman ^[11], it is imaginable to use other distance function to study properties of graphs. Based on this, it is not difficult to find that $A_{p}(G)$ is the Minkowski norm of $d(u)$ and $d(v)$, which is unification of absolute distance, Euclidean distance and Chebyshev distance. Hence $A_{p}(G) = \Delta-\delta$ as $p$ becomes infinite. In particular, $A_{p}(G)$ is the $l_p$-norm of $d(u)$ and $d(v)$ for $p\geq 1$.

We will first recall some useful notions and lemmas used further in Section 2. In Section 3, upper and lower bounds on the general Albertson irregularity index of graphs are given, and the extremal graphs are characterized. In Section 4, the first two trees with minimum general Albertson irregularity index are determined in all trees of fixed order. In Section 5, the general Albertson index of the well-known generalized Bethe trees and Kragujevac trees is obtained.

2.   Preliminaries

Let $u\vee G$ be the graph by adding all edges between the vertex $u$ and $V(G)$, see for example in Figure 1. The first general Zagreb index of a graph $G$ is defined as $Z_p(G) = \sum_{v\in V(G)}d^p(v)$ for any real number $p$. The distance between two vertices $u, v \in V(G)$, denoted by $d(u, v)$, is defined as the length of a shortest path between $u$ and $v$. The eccentricity of $v$, $\varepsilon(v)$, is the distance between $v$ and any vertex which is furthest from $v$ in $G$. The line graph $L(G)$ is the graph whose vertex set are the edges in $G$, where two vertices are adjacent if the corresponding edges in $G$ have a common vertex. Let $\mathcal{T}_{n}$ be the set of trees with $n$ vertices. A spider is a tree with at most one vertex of degree more than two.

Lemma 2.1. (Power mean inequality) Let $x_1, x_2, \ldots, x_n$ be positive real numbers and $p$, $q$ real numbers such that $p > q$. Then,

with equality if and only if $x_1 = x_2 = \cdots = x_n$.

Lemma 2.2. (Hölder inequality) Let $(a_1, a_2, \ldots, a_n)$ and $(b_1, b_2, \ldots, b_n)$ be two $n$-tuples of real numbers and let $p$, $q$ be two positive real numbers such that $\frac{1}{p}+\frac{1}{q} = 1$. Then

with equality if and only if $|a_i|^p = \lambda |b_i|^q$ for some real constant $\lambda$, $1\leq i\leq n$.

Lemma 2.3. (^[26]) If $p\geq 1$ is an integer and $0\leq x_1, x_2, \ldots, x_n\leq n-1$, then

Lemma 2.4. (Minkowski inequality) Let $(a_1, a_2, \ldots, a_n)$ and $(b_1, b_2, \ldots, b_n)$ be two $n$-tuples of real numbers. If $p\geq 1$. Then

with equality if and only if $a_i = \lambda b_i$ for some real constant $\lambda$, $1\leq i\leq n$. For $0 < p < 1$, the inequality $(2.1)$ gets reversed.

Lemma 2.5. (^[20]) Let $x = (x_1, x_2, \ldots, x_k, \ldots)$ be a non-zero vector. Then for $p\geq 2$,

with equality if and only if all but one of the $x_i$ are equal to $0$.

Lemma 2.6. Let $G$ be a connected graph. Suppose there exists a vertex $u\in V(G)$ with $d(u)\geq 3$, $v_1, v_2, \ldots, v_l$ and $w_1, w_2, \ldots, w_t$ are two path components in $G-u$, where $N(u) = \{v_1, w_1, u_1, u_2, \ldots, u_{d(u)-2}\}$. Let $G' = G-uw_1+v_lw_1$. Then

${\rm (i)}$ If $p > 0$ and $d(u) > d(u_i)$, then $A_p(G) > A_p(G')$.

${\rm (ii)}$ If $p\geq 1$ and $d(u)\geq d(u_i)$, then $A_p(G) > A_p(G')$.

${\rm (iii)}$ If $p > 0$ and $\Delta = d(u) = 3$, then $A_p(G) > A_p(G')$.

Proof. Let $s = d(u)-2$. Since $d(u) > d(u_i)$, $d(u)\geq 3$, $d(v_1)\leq 2$ and $d(w_1)\leq 2$, we have $|d(u)-d(u_i)|^p-|d(u)-d(u_i)-1|^p > 0$ and $|d(u)-d(v_1)|^p-|d(u)-d(v_1)-1|^p+1 > 0$. Then

Thus we have $A_p(G) > A_p(G')$.

If $p\geq 1$ and $d(u) = d(u_i)$, then we have

Thus we have $A_p(G) > A_p(G')$.

If $p > 0$ and $\Delta = d(u) = 3$, then we have

Thus we have $A_p(G) > A_p(G')$.

Combining the above arguments, we have the proof.

3.   Some bounds for the general Albertson index

Theorem 3.1. Let $G$ be a connected graph with $m$ edges. If $p > q$, then

with equality if and only if $G$ is a regular graph (when $G$ is non-bipartite) or $G$ is a $(\Delta, \delta)$-semiregular bipartite graph (when $G$ is bipartite).

Proof. By Lemma 2.1, we have

that is,

that is,

with equality if and only if $|d(u)-d(v)|$ is a constant for every edge $uv$ in $G$, that is, $G$ is a regular graph (when $G$ is non-bipartite) or $G$ is a $(\Delta, \delta)$-semiregular bipartite graph (when $G$ is bipartite).

Corollary 3.2. Let $G$ be a connected graph with $m$ edges. Then

with equality if and only if $G$ is a regular graph (when $G$ is non-bipartite) or $G$ is a $(\Delta, \delta)$-semiregular bipartite graph (when $G$ is bipartite).

Theorem 3.3. Let $G$ be a connected graph. If $\frac{1}{p}+\frac{1}{q} = 1$, then

with equality if and only if $p = 2$, or $G$ is a regular graph (when $G$ is non-bipartite) or $G$ is a $(\Delta, \delta)$-semiregular bipartite graph (when $G$ is bipartite).

Proof. For $a_i = b_i = d(u)-d(v)$ and apply Lemma 2.2. Then

that is,

with equality if and only if $p = 2$, or $G$ is a regular graph (when $G$ is non-bipartite) or $G$ is a $(\Delta, \delta)$-semiregular bipartite graph (when $G$ is bipartite).

Theorem 3.4. Let $G$ be a connected graph with $m$ edges. If $p\geq 1$ is an integer, then

Proof. Let $x_i = |d(u)-d(v)|$ in Lemma 2.3. Then

that is,

Theorem 3.5. Let $G$ be a connected graph with $m$ edges. If $p\geq 1$, then

If $0 < p < 1$, then

Proof. Let $a_i = 1$ and $b_i = |d(u)-d(v)|$ in Lemma 2.4. Then

for $p\geq 1$. By Bernoulli inequality, we have

that is,

For $0 < p < 1$, by Lemma 2.4 and Bernoulli inequality, we have the proof.

Theorem 3.6. Let $G$ be a connected graph. If $p\geq 2$, then

with equality if and only if $d(u)-d(v)\neq 0$ for unique edge $uv$ and 0 for the other edges in $G$.

Proof. By Lemma 2.5, we have

with equality if and only if $d(u)-d(v)\neq 0$ for only one edge $uv$ and 0 for the other edges in $G$.

Remark 3.7. There exist many graphs such that the equality in $(3.1)$ holds, the following graphs are examples (See Figure 2).

Theorem 3.8. Let $G$ be a connected graph with $n$ vertices. Then

with equality if and only if $G\cong K_{1, \ n-1}$.

Proof. By definition of $A_p(G)$, we have

with equality if and only if $(d(u)-1)(d(v)-1)\leq 0$, that is, $d(v) = 1$ for every edge $uv$ in $G$, that is, $G$ is a star $K_{1, \ n-1}$.

Corollary 3.9. Let $G$ be a connected graph with $n$ vertices and $m$ edges. Then

with equality if and only if $G\cong K_{1, \ n-1}$.

Theorem 3.10. Let $u$ be a vertex and $G$ be a connected graph. Then

where $\overline{G}$ is the complement of $G$.

Proof. By definition of $u \vee G$, we have

Corollary 3.11. Let $G$ be a connected graph with $n$ vertices and $m$ edges. Then

Theorem 3.12. Let $u$ be a pendant vertex of a connected graph $G$ with $n\geq 3$ vertices. If $G+P_t$ $(t\geq 1)$ is the graph by adding a new (pendant) path to $u$, then

${\rm (i)}$ $A_p(G+P_t) > A_p(G)$ for $0 < p < 1$.

${\rm (ii)}$ $A_p(G+P_t) = A_p(G)$ for $p = 1$.

${\rm (iii)}$ $A_p(G+P_t) < A_p(G)$ for $p > 1$.

Proof. Let $v$ be the unique neighbour of $u$ in G. Since $a^p+b^p > (a+b)^p$ for $a > 0$, $b > 0$ and $0 < p < 1$, we have

for $0 < p < 1$. Thus $A_p(G+P_t) > A_p(G)$. By a similar reasoning as above, we have the proof of (ii) and (iii).

Corollary 3.13. Let $u$ be a pendant vertex of a connected graph $G$ with $n\geq 3$ vertices. If $G+P_t$ $(t\geq 1)$ is the graph by adding a new (pendant) path to $u$, then

4.   The general Albertson index of trees

Theorem 4.1. Let $T_n\in \mathcal{T}_{n}$. Then

The lower bound is attained if and only if $T_n\cong P_n$. The upper bound is attained if and only if $T_n\cong K_{1, \, n-1}$.

Proof. If $\Delta \geq 3$, then $T_n$ has at least three pendant vertices. Thus $A_p(T_n) > 3^{\frac{1}{p}} > 2^{\frac{1}{p}} = A_p(P_n)$. In addition, $A_p(T_n)\leq (\Delta-1)(n-1)^{\frac{1}{p}}\leq (n-2)(n-1)^{\frac{1}{p}} = A_p(K_{1, \, n-1})$.

Theorem 4.2. Let $n\geq 10$, $T_n\in \mathcal{T}_{n}-\{P_n\}$, $T^1$ and $T^3$ shown as in Figure 3.

${\rm (i)}$ If $p > 1$, then $A_p(T_n)\geq 6^{\frac{1}{p}}$ with equality if and only if $T_n\cong T^1$.

${\rm (ii)}$ If $p = 1$, then $A_p(T_n)\geq 6$ with equality if and only if $T_n$ is a spider with $\Delta = 3$.

${\rm (iii)}$ If $0 < p < 1$, then $A_p(T_n)\geq (2^{p+1}+2)^{\frac{1}{p}}$ with equality if and only if $T_n\cong T^3$.

Proof. Let $d_1\geq d_2\geq d_3\geq \cdots \geq d_n$ be the degree sequence of $T_n$, and let $k$ be the number of non-pendant edges $uv$ with $d(u)\neq d(v)$. Then

If $d_1\geq 7$, then $A_p^p(T_n) > 7$.

If $d_1\geq 6$ and $d_2\geq 3$, then $A_p^p(T_n) > 6+(3-2) = 7$.

If $d_1\geq 6$ and $d_2 = 2$, then $A_p^p(T_n) > 6+1 = 7$.

If $d_1 = d_2 = 5$, then $A_p^p(T_n) > 5+(5-2) = 8$.

If $d_1 = 5$ and $d_2 = 4$, then $A_p^p(T_n) > 5+(4-2) = 7$.

If $d_1 = 5$ and $d_2 = 3$, then $A_p^p(T_n) > 5+(3-2)+1 = 7$.

If $d_1 = 5$ and $d_2 = 2$, then $A_p^p(T_n) = \left\{ \begin{array}{llll} 4^{p+1}+3^p+1, \\ 3\cdot 4^p+2\cdot 3^p+2, \\ 2\cdot 4^p+3^{p+1}+3, \\ 4^p+4\cdot 3^p+4, \\ 5\cdot 3^p+5. \end{array} \right.$ Thus $A_p^p(T_n) > 6$.

If $d_1 = d_2 = 4$, then $A_p^p(T_n)\geq 4+(4-2)+1 > 7$.

If $d_1 = 4$ and $d_2 = d_3 = d_4 = 3$, then $A_p^p(T_n) > 4+(3-2)+(3-2)+(3-2) = 7$.

If $d_1 = 4$ and $d_2 = d_3 = 3$, then $A_p^p(T_n) > 4+(3-2)+(3-2)+1 = 7$.

If $d_1 = 4$ and $d_2 = 3$, then $A_p^p(T_n) > 4+(3-2)+1 = 6$.

If $d_1 = 4$ and $d_2 = 2$, then $A_p^p(T_n) = \left\{ \begin{array}{llll} 3^{p+1}+2^p+1, \\ 2\cdot 3^p+2^{p+1}+2, \\ 3^p+3\cdot 2^{p}+3, \\ 4\cdot 2^p+4. \end{array} \right.$

If $d_1 = 3$, we can applying Lemma 2.6 repeatedly to the vertices with degree three. Thus the minimum value of $T_n$ has four cases, shown as in Figure 3. By direct computing, we have

By comparing the above cases, we have that $T_1$, $T^2$, $T'^2$ and $T^3$ are the candidates with minimum general Albertson index among $\mathcal{T}_{n}-\{P_n\}$. Further, we have $A_p^p(T^1) > A_p^p(T^2) = A_p^p(T'^2) > A_p^p(T^3)$ for $p > 1$, $A_p^p(T^1) = A_p^p(T^2) = A_p^p(T'^2) = A_p^p(T^3)$ for $p = 1$, and $A_p^p(T^1) < A_p^p(T^2) = A_p^p(T'^2) < A_p^p(T^3)$ for $0 < p < 1$.

Theorem 4.3. Let $T_n$ be a tree with $n$ vertices. If $p\geq1$, then

where $v_{\Delta}$ is a vertex of the maximum degree.

Proof. Let $v_{\Delta}v_1v_2\ldots v_{l_1}$ be the path from the vertex $v_{\Delta}$ to pendant vertex $v_{l_1}$. Then $d(v_{\Delta}, v_{l_1}) = l_1$. Let $f(x) = x^p$. Since $f(x)$ is a increasing and convex function for $x > 0$ and $p\geq 1$, we have

that is,

Since $T_n$ has at least $\Delta$ pendant vertices, we have

where $l_1, l_2, \ldots, l_{\Delta}$ is the distance from maximum degree vertex $v_{\Delta}$ to pendant vertex $v_{l_i}$, $1\leq i \leq \Delta$. Note that $\varepsilon(v_{\Delta}) = \max_{v\in V(G)}d(v_{\Delta}, v)\geq l_i$ for $1\leq i \leq \Delta$. Thus we have $A_p(T_n)\geq (\Delta \varepsilon^{1-p}(v_{\Delta}))^{\frac{1}{p}}(\Delta-1)$.

Corollary 4.4. Let $T_n$ be a tree with $n$ vertices. Then

with equality if and only if $G$ is a spider.

5.   The general Albertson index of generalized Bethe trees and Kragujevac trees

In this section, we give the calculation formula of the general Albertson index of generalized Bethe trees and Kragujevac trees which are a wide range of applications in the field of mathematics ^[22,25], cheminformatics ^[15,27,29], statistical mechanics ^[19], etc.

A generalized Bethe tree ^[23] is a rooted tree in which vertices of the same level (height) have the same degree. We usually use $B_k$ to denote the generalized Bethe tree with $k$ levels with the root at the level 1. More specifically, $B_{k, \, d}$ denotes a Bethe tree ^[16] of $k$ levels with the root degree $d$, and the vertices between the level $2$ and $k-1$ all have degree $d+1$. A regular dendrimer tree ^[14] $T_{k, \, d}$ is a special case of $B_k$, where the degrees of all internal vertices are $d$.

Theorem 5.1. Let $B_k$ be the generalized Bethe tree where the degree of each level is $d_1\geq d_2\geq \cdots \geq d_{k-1}, d_{k} = 1$. Then

Proof. By definition of the generalized Bethe tree, we have

Thus we have the proof.

Corollary 5.2. Let $B_{k, \, d}$ and $T_{k, \, d}$ be the Bethe tree and a regular dendrimer tree, respectively. Then

Let $P_3$ be the 3-vertex tree, rooted at one of its terminal vertices, see Figure 4. For $k = 2, 3, \ldots$, construct the rooted tree $R_k$ by identifying the roots of $k$ copies of $P_3$. The vertex obtained by identifying the roots of $P_3$-trees is the root of $R_k$. Let $d\geq 2$ be an integer and $\gamma_1, \gamma_2, \ldots, \gamma_d$ be rooted trees, i.e., $\gamma_1, \gamma_2, \ldots, \gamma_d\in \{R_2, R_3, \ldots\}$. A Kragujevac tree $KT$ ^[15] is a tree possessing a vertex of degree $d$, adjacent to the roots of $\gamma_1, \gamma_2, \ldots, \gamma_d$. This vertex is said to be the central vertex of $KT$, whereas $d$ is the degree of $KT$. The subgraphs $\gamma_1, \gamma_2, \ldots, \gamma_d$ are the branches of $KT$. Recall that some (or all) branches of $KT$ may be mutually isomorphic.

Theorem 5.3. Let $KT$ be a Kragujevac tree with $n$ vertices and $\gamma_i\cong R_{k_i}$, $i = 1, 2, \ldots, d$. Then

Proof. Since $1+\sum\limits_{i = 1}^{d}(2k_i+1) = n$, by definition of the Kragujevac tree, we have

Thus we have the proof.

Corollary 5.4. Let $KT$ be a Kragujevac tree with $n$ vertices and $\gamma_i\cong R_{k}$, $i = 1, 2, \ldots, d$. Then

6.   Conclusions

In this paper, we propose the general Albertson irregularity index which extends classical Albertson irregularity index and $\sigma$-index. The tight bounds of the general Albertson irregularity index are established. Additionally, the general Albertson irregularity index of trees are studied. In 2014, the total irregularity of a graph $G$, introduced by Abdo, Brandt and Dimitrov ^[2], is defined as $\text{irr}_t(G) = \sum_{\{u, v\}\subseteq V(G)}|d(u)-d(v)|$. For measuring the non-self-centrality of a graph, the non-self-centrality number of $G$ was introduced in ^[30] as $N(G) = \sum_{\{u, v\}\subseteq V(G)}|\varepsilon(u)-\varepsilon(v)|$. Based on these, we can propose the general total irregularity and the general non-self-centrality number of a graph $G$ as follows:

where the summation goes over all the unordered pairs of vertices in $G$. The research interaction among $A_p(G)$, $\text{irr}_{p}(G)$ and $N_{p}(G)$ will be carried out in the near future.

Acknowledgments

The authors are grateful to the anonymous referee for careful reading and valuable comments which result in an improvement of the original manuscript. This work was supported by the Qinghai science and technology plan project (No. 2021-ZJ-703) and the National Natural Science Foundation of China (No. 11771443).

Conflict of interest

The authors declare no conflict of interest.