1. Introduction
Topological indices, which are real numbers that represent the topology of (molecular) graphs, play a significant role in mathematical chemistry, especially in the study of the quantitative structure–property relationship (QSPR) and the quantitative structure–activity relationship (QSAR) [Reference Devillers and Balaban10, Reference Estrada14]. The well-known Zagreb index, the first degree-based topological index [Reference Gutman17], was originally proposed by Gutman and Trinajstić more than 50 years ago [Reference Gutman and Trinajstić21]. This index, defined as the sum of squares of the degrees of vertices in a graph, has been utilized to discuss the QSAR/QSPR of the different chemical structures such as chirality, complexity, heterosystems, ZE isomers and
$\pi$
-electron energy [Reference Diudea11]. For more details of the mathematical properties and chemical applications of the Zagreb index, see, for example, [Reference Das, Xu and Nam8, Reference Gutman and Das19, Reference Horoldagva and Das22, Reference Wang and Yuan40] and the references therein.
Let
$G=(V,E)$
be a simple graph with vertex set V and edge set E. For any vertex
$v\in V$
, let d(v) denote the degree of v, that is, the number of vertices adjacent to v. Then the most straightforward modification of the Zagreb index is to introduce a variable parameter in its definition:
\begin{align*} Z_{G}^{(k)}=\sum_{v\in V} [d(v)]^{k},\end{align*}
where k is an arbitrary real number. This generalization of the Zagreb index was first considered in [Reference Li and Zhao28], and then followed by many other authors (see, for example, [Reference Bedratyuk and Savenko2, Reference Gutman18, Reference Gutman, Milovanović and Milovanović20, Reference Li and Zheng29, Reference Zhang and Zhang44]). We refer to an excellent survey [Reference Ali, Gutman, Milovanović and Milovanović1] for relations between the generalized Zagreb indices and other topological indices. These generalized indices have also been the subject of considerable attention in graph theory (see, for example, [Reference Cheng and Wu6, Reference Cioabă7]). For the sake of simplicity, we only consider the case where k is a positive integer in this work. When
$k=1$
, the index
$Z_G^{(1)}$
is the total sum of degrees of vertices in G. Then, from basic graph theory, it is equal to twice the number of edges in G. The case of the ordinary Zagreb index is
$k=2$
. Another important special case is
$k=3$
, where
$Z_{G}^{(3)}$
is referred to as the forgotten index in the literature for historical reasons (see, for example, [Reference Furtul and Gutman16, Reference Jahanbani23]).
In the study of random graphs or network data analysis, one of the fundamental concepts is the degree distribution (see, for example, [Reference Van der Hofstad39]). Consider an observed graph on finite vertices generated from a random graph model, where the number of vertices could grow to infinity. From a statistical point of view, the kth-order generalized Zagreb index of this graph divided by the total number of vertices is an empirical estimation of the kth moment of the asymptotic degree distribution of the underlying graph model. Consequently, the generalized Zagreb indices of various random graph models are of independent interest in probability theory and statistics despite of their chemical background.
Erdős–Rényi (ER) random graphs are possibly the most extensively studied random graph model in the literature. We refer the reader to the monographs [Reference Bollobás5, Reference Janson, Łuczak and Ruciński24, Reference Van der Hofstad39] for the enormous range of results on this classical model. In this work, we aim to derive the asymptotic properties of the generalized Zagreb indices of ER random graphs, as the number of vertices grows to infinity. In [Reference Feng, Hu and Su15], several limit laws have been established for the ordinary Zagreb index of ER random graphs, as well as for another type of Zagreb index. The expectation of the generalized Zagreb index of any positive integer order has recently been obtained in [Reference Došlić, Hosseinzadeh, Hossein-Zadeh, Iranmanesh and Rezakhanlou12], as well as for ER random graphs. For some recent developments of other topological indices with chemical backgrounds in the field of random graphs, see, for example, [Reference Yuan42, Reference Yuan43].
Throughout this paper, we shall use the following notation. For an event
${\mathcal E}$
, let
$|{\mathcal E}|$
be its cardinality, and
$I({\mathcal E})$
be the indicator of
${\mathcal E}$
. Let
$\textrm{Poi}(\lambda)$
denote by the Poisson distribution with parameter
$\lambda>0$
. For two sequences of positive numbers
$a_n$
and
$b_n$
, we write
$a_n\sim b_n$
for
$a_n/b_n\to 1$
,
$a_n=o(b_n)$
for
$a_n/b_n\to 0$
, and
$a_n=O(b_n)$
if
$a_n/b_n$
is bounded, as
$n\to\infty$
. For probabilistic convergence, we use
$\buildrel {D} \over \longrightarrow $
and
${\buildrel {P} \over \longrightarrow}$
to denote convergence in distribution and in probability, respectively.
The rest of this paper is organized as follows. The generalized Zagreb indices of ER random graphs are formally defined in Section 2, and reformulated in terms of the number of star graphs of various sizes. Through this reformulation, in Section 3 we obtain the first two moments of these indices, as well as several results of weak convergence. In Section 4, under different conditions we establish the joint asymptotic normality of the first kth-order generalized Zagreb indices for any
$k\ge2$
, and then provide a necessary and sufficient condition for the kth-order generalized Zagreb index for any
$k\ge1$
.
2. Generalized Zagreb Index and Star Graphs
Let us denote by G(n, p) an ER random graph on the vertex set
$\{1,2,\ldots,n\}$
, where each possible edge exists independently with probability
$0<p<1$
. Typically, we consider
$p=p(n)$
as a function of n in this work. For any pair of vertices (i, j), let
$I_{ij}$
denote the indicator of the event that there exists an edge between i and j in G(n, p). Then
$I_{ii}=0$
,
$I_{ij}=I_{ji}$
, and
$\{I_{ij},1\le i < j\le n\}$
is a sequence of independent Bernoulli variables with common success rate p. For any integer
$k\ge 1$
, the kth-order generalized Zagreb index of G(n, p) is then formally defined as
\begin{align} Z_{n}^{(k)}=\sum_{i=1}^n\bigg(\sum_{j=1}^n I_{ij}\bigg)^k,\end{align}
where the term
$\sum_{j=1}^n I_{ij}$
stands for the degree of vertex i. In particular, the first three indices
$Z_{n}^{(1)},Z_{n}^{(2)}$
and
$Z_{n}^{(3)}$
are the total sum of vertex degrees, the ordinary Zagreb index, and the forgotten index of G(n, p), respectively.
For a positive integer m, a star graph of size m, sometimes simply known as an m-star, is a tree on m vertices with one vertex having degree
$m-1$
and the other
$m-1$
vertices having degree 1 (see, for example, [Reference Tutte38]). In a star graph, we call the vertex with highest degree the center. As a special case, a 2-star may have two different centers, since both of its vertices have common degree 1. Here, we may distinguish two 2-stars that are defined on the same pair of vertices but have different centers. As a result, in any graph, the number of 2-stars is equal to twice the number of edges. For another special case, the number of 3-stars corresponds to the number of paths of length 2 (or wedges) in a graph. Let
$S_{m,n}^{(i)}$
denote the number of m-stars with the center at vertex i in G(n, p). That is, for any
$1\le i\le n$
,
\begin{align} S_{m,n}^{(i)}=\sum_{1\le j_1 < \cdots < j_{m-1}\le n}I_{ij_1}\cdots I_{ij_{m-1}}, \quad m\ge2.\end{align}
Then, for any integer
$m\ge2$
, the sum
\begin{align} S_{m,n}=\sum_{i=1}^nS_{m,n}^{(i)}\end{align}
denotes the number of m-stars in G(n, p).
The Stirling numbers of the second kind, denoted by
$\left\{ \begin{matrix}n\\k\end{matrix}\right\}$
, are the numbers of partitions of a set of n elements into k nonempty classes (see, for example, [Reference Wilf41]). For any two nonnegative integers
$n\ge k$
, the linear recurrence relation
\begin{equation} \left\{ \begin{matrix}n\\k\end{matrix}\right\}=k\left\{ \begin{matrix}n-1\\k\end{matrix}\right\}+\left\{ \begin{matrix}n-1\\k-1\end{matrix}\right\}\end{equation}
holds, where, by convention,
\begin{equation*} \left\{ \begin{matrix}0\\0\end{matrix}\right\}=1\quad\mbox{and}\quad \left\{ \begin{matrix}n\\0\end{matrix}\right\}=0, \quad n\ge1.\end{equation*}
The following proposition plays an important role in deriving the asymptotic behavior of the generalized Zagreb indices of G(n, p), as well as their first two moments.
Proposition 1. For any
$k\ge 1$
, the kth-order generalized Zagreb index of G(n,p) can be expressed as
\begin{align} Z_{n}^{(k)}=\sum_{m=1}^k m!\left\{ \begin{matrix}k\\m\end{matrix}\right\}S_{m+1,n}. \end{align}
Proof. To prove Proposition 1, we first show that in a simple graph, the kth power of the degree of any given vertex i can be expressed in terms of the number of m-stars with center i for all
$2\le m\le k+1$
. More precisely,
\begin{equation} \bigg(\sum_{j=1}^n I_{ij}\bigg)^{k}=\sum_{m=1}^k m!\left\{ \begin{matrix}k\\m\end{matrix}\right\} S_{m+1,n}^{(i)},\quad k\ge1. \end{equation}
Indeed, we can prove (6) by induction on
$k\ge1$
. For
$k=1$
, both sides of (6) are the degree of vertex i, which initializes the induction hypothesis. To advance the induction hypothesis, we suppose that (6) holds for k. Recall that
$\left\{ \begin{matrix}k\\0\end{matrix}\right\}=0$
and
$\left\{ \begin{matrix}k\\k\end{matrix}\right\}=1$
for any
$k\ge1$
. Taking into account the number of repetitions, for any given vertex i in G(n, p), we have
\begin{align*} \sum_{1\le j_1 < \dots < j_m\le n}I_{ij_1}\cdots I_{ij_m}\sum_{j\in\{j_1,\ldots,j_m\}} I_{ij}=mS_{m+1,n}^{(i)}, \end{align*}
and
\begin{align*} \sum_{1\le j_1<\dots < j_m\le n}I_{ij_1}\cdots I_{ij_m}\sum_{j\notin\{j_1,\ldots,j_m\}} I_{ij} =\binom{m+1}{m}S_{m+2,n}^{(i)}=(m+1)S_{m+2,n}^{(i)}. \end{align*}
Then, by (2), (4), and the induction hypothesis, we obtain that
\begin{align*} \bigg(\sum_{j=1}^n I_{ij}\bigg)^{k+1} &=\sum_{m=1}^k m!\left\{ \begin{matrix}k\\m\end{matrix}\right\}S_{m+1,n}^{(i)}\cdot\bigg(\sum_{j=1}^n I_{ij}\bigg)\\ &=\sum_{m=1}^k m!\left\{ \begin{matrix}k\\m\end{matrix}\right\}\sum_{1\le j_1 < \dots < j_m\le n}I_{ij_1}\cdots I_{ij_m}\bigg(\sum_{j\in\{j_1,\ldots,j_m\}} I_{ij} +\sum_{j\notin\{j_1,\ldots,j_m\}} I_{ij}\bigg)\\ &=\sum_{m=1}^km!\left\{ \begin{matrix}k\\m\end{matrix}\right\}\Big(mS_{m+1,n}^{(i)} +(m+1)S_{m+2,n}^{(i)}\Big)\\ &=\sum_{m=1}^km!\bigg(\left\{ \begin{matrix}k+1\\m\end{matrix}\right\}-\left\{ \begin{matrix}k\\m-1\end{matrix}\right\}\bigg)S_{m+1,n}^{(i)} +\sum_{m=1}^k(m+1)!\left\{ \begin{matrix}k\\m\end{matrix}\right\}S_{m+2,n}^{(i)}\\ &=\sum_{m=1}^{k+1} m!\left\{ \begin{matrix}k+1\\m\end{matrix}\right\}S_{m+1,n}^{(i)}, \end{align*}
which advances the induction, and thus (6) holds for any
$k\ge1$
.
Using relation (6), it follows by (1) that
\begin{align*} Z_{n}^{(k)}=\sum_{i=1}^n\sum_{m=1}^k m!\left\{ \begin{matrix}k\\m\end{matrix}\right\}S_{m+1,n}^{(i)} =\sum_{m=1}^k m!\left\{ \begin{matrix}k\\m\end{matrix}\right\}\sum_{i=1}^n S_{m+1,n}^{(i)}, \end{align*}
which, by (3), is equal to the right-hand side of (5). This completes the proof of Proposition 1.
The above proposition states that in any simple graph, the generalized Zagreb index is a linear combination of the numbers of star graphs of various sizes, in which the coefficients involve the Stirling numbers of the second kind. Specially, it immediately follows from Proposition 1 that in a simple graph, the ordinary Zagreb index
\begin{equation*} Z_n^{(2)}=S_{2,n}+2S_{3,n},\end{equation*}
which, in fact, has been shown in [Reference Feng, Hu and Su15], and the forgotten index can be expressed as
\begin{equation*} Z_n^{(3)}=S_{2,n}+6S_{3,n}+6S_{4,n}.\end{equation*}
3. Mean and Variance
As previously stated in Section 1, the explicit expression for the mean
$\mathbb{E}[Z_n^{(k)}]$
is obtained in [Reference Došlić, Hosseinzadeh, Hossein-Zadeh, Iranmanesh and Rezakhanlou12] for any integer
$k\ge1$
. This is achieved through an approach using the generating polynomial of the degree sequence [Reference Sedghi, Shobe and Salahshoor37]. Nevertheless, in view of Proposition 1, we can directly derive the first two moments of the generalized Zagreb index of G(n, p) by considering the numbers of star graphs of sizes not less than 2.
For the expectation of
$S_{m+1,n}$
, it follows by (2) and (3) that
\begin{equation} \mathbb{E} [S_{m+1,n}]=n\binom{n-1}{m}p^{m}, \quad 1\le m\le n-1.\end{equation}
Let m and l be two fixed integers satisfying
$1\le m, l\le n-1$
. Recalling (3), by symmetry it follows that the covariance of
$S_{m+1,n}$
and
$S_{l+1,n}$
is given by
\begin{align} \textrm{cov}(S_{m+1,n},S_{l+1,n}) &=\textrm{cov}\bigg(\sum_{i=1}^nS_{m+1,n}^{(i)},\sum_{j=1}^nS_{l+1,n}^{(j)}\bigg)\notag\\ &=n\ \textrm{cov}\Big(S_{m+1,n}^{(1)},S_{l+1,n}^{(1)}\Big) +n(n-1)\textrm{cov}\Big(S_{m+1,n}^{(1)},S_{l+1,n}^{(2)}\Big).\end{align}
We next compute the covariances on the right-hand side of (8) separately. Consider any two possible star graphs with common center at vertex 1, but of sizes
$m+1$
and
$l+1$
, respectively. Then the covariance of the two products of indicators
$I_{1i_1}\cdots I_{1i_{m}}$
and
$I_{1j_1}\cdots I_{1j_{l}}$
depends on the number of elements in the intersection of sets
$\{i_1,\ldots,i_{m}\}$
and
$\{j_1,\ldots,j_{l}\}$
. Specially, if the intersection is empty, these two products are independent. Furthermore, if there are exactly
$s\ge1$
elements in this intersection,
\begin{align*} \textrm{cov}(I_{1i_1}\cdots I_{1i_{m}},I_{1j_1}\cdots I_{1j_{l}}) =p^{m+l-s}-p^{m+l}=p^{m+l-s}(1-p^s),\end{align*}
where the integer s ranges from
$\max\{1,m+l-n+1\}$
to
$\min\{m,l\}$
. This implies that
\begin{align} \textrm{cov}(S^{(1)}_{m+1,n},S^{(1)}_{l+1,n}) &=\textrm{cov}\bigg(\sum_{1\le i_1 < \cdots < i_{m}\le n}I_{1i_1}\cdots I_{1i_{m}},\sum_{1\le j_1 < \cdots < j_{l}\le n}I_{1j_1}\cdots I_{1j_{l}}\bigg)\notag\\ &=\sum_{s=\max\{1,m+l-n+1\}}^{\min\{m,l\}}\binom{n-1}{s,m-s,l-s,n-m-l+s-1} p^{m+l-s}(1-p^s),\end{align}
where the multinomial coefficient
\begin{align*} \binom{n-1}{s,m-s,l-s,n-m-l+s-1}= \frac{(n-1)!}{s!(m-s)!(l-s)!(n-m-l+s-1)!}.\end{align*}
Note that two star graphs with different centers have at most one common edge, which connects their centers. From this we obtain
\begin{align} \textrm{cov}(S^{(1)}_{m+1,n},S^{(2)}_{l+1,n}) &=\textrm{cov}\bigg(\sum_{3\le i_2 < \cdots < i_{m}\le n}I_{12}I_{1i_2}\cdots I_{1i_{m}},\sum_{3\le j_2 < \cdots < j_{l}\le n}I_{21}I_{2j_2}\cdots I_{2j_{l}}\bigg)\notag\\ &=\binom{n-2}{m-1}\binom{n-2}{l-1}\textrm{cov}\bigg(I_{12}I_{13}\cdots I_{1(m+1)}, I_{21}I_{23}\cdots I_{2(l+1)}\bigg)\notag\\ &=\binom{n-2}{m-1}\binom{n-2}{l-1}p^{m+l-1}(1-p).\end{align}
Plugging (9) and (10) into (8), we thus have
\begin{align} \textrm{cov}(S_{m+1,n},S_{l+1,n}) &=n\sum_{s=\max\{1,m+l-n+1\}}^{\min\{m,l\}} \binom{n-1}{s,m-s,l-s,n-m-l+s-1}\notag\\ &\quad \cdot p^{m+l-s}(1-p^s) +n(n-1)\binom{n-2}{m-1}\binom{n-2}{l-1}p^{m+l-1}(1-p).\end{align}
For our purposes in this work, we are more interested in the case where n could grow to infinity. By (7) and (11) we have that, as
$n\to\infty$
, for any
$m\ge1$
,
\begin{align} \mathbb{E}[S_{m+1,n}]&=\frac{n^{m+1}p^m}{m!}\Big(1+O\Big(\frac1n\Big)\Big),\end{align}
and for any
$m,l\ge1$
,
\begin{align} \textrm{cov}\big(S_{m+1,n},S_{l+1,n}\big) =n\bigg(\frac{(np)^{m+l-1}(1-p)}{(m-1)!(l-1)!}+\sum_{s=1}^{\min\{m,l\}}\frac{(np)^{m+l-s}(1-p^s)}{s!(m-s)!(l-s)!}\bigg)\Big(1+O\Big(\frac1n\Big)\Big).\end{align}
In particular, letting
$m=l$
in (13) yields
\begin{align}\mathrm{Var}[S_{m+1,n}]=n\bigg(\frac{(np)^{2m-1}(1-p)}{[(m-1)!]^2}+\sum_{s=1}^m\frac{(np)^{2m-s}(1-p^s)}{s![(m-s)!]^2}\bigg)\Big(1+O\Big(\frac1n\Big)\Big), \quad m\ge1.\end{align}
Applying Proposition 1, together with (7) and (11), it is straightforward to obtain the explicit expressions for the mean and variance of
$Z_n^{(k)}$
, for any
$k\ge1$
. We summarize these results in the following proposition, and omit the details.
Proposition 2. For any
$k\ge1$
, let
$Z^{(k)}_n$
be the kth-order generalized Zagreb index of G(n, p). Then we have
\begin{equation} \mathbb{E} \big[Z^{(k)}_n\big]=\sum_{m=1}^k \left\{ \begin{matrix}k\\m\end{matrix}\right\}\frac{n!}{(n-m-1)!}p^m \end{equation}
and
\begin{align} \mathrm{Var}\big[Z^{(k)}_n\big]&=n\sum_{m=1}^k\sum_{l=1}^km!\,l!\left\{ \begin{matrix}k\\m\end{matrix}\right\} \left\{ \begin{matrix}k\\l\end{matrix}\right\} \bigg[(n-1)\binom{n-2}{m-1}\binom{n-2}{l-1}p^{m+l-1}(1-p)\notag\\ &\quad +\sum_{s=\max\{1,m+l-n+1\}}^{\min\{m,l\}} \binom{n-1}{s,m-s,l-s,n-m-l+s-1} p^{m+l-s}(1-p^s) \bigg]. \end{align}
For any given
$k\ge 1$
, it is also useful to obtain the asymptotics of the expectation and variance of
$Z^{(k)}_n$
. As
$n\to\infty$
, it follows that, by (15),
\begin{equation} \mathbb{E}\big[Z^{(k)}_n\big]=\sum_{m=1}^k \left\{ \begin{matrix}k\\m\end{matrix}\right\}n^{m+1}p^m\Big(1+O\Big(\frac1n\Big)\Big),\end{equation}
and that, by (16),
\begin{align} \mathrm{Var}\big[Z^{(k)}_n\big]&=n\sum_{m=1}^k\sum_{l=1}^km!\,l!\left\{ \begin{matrix}k\\m\end{matrix}\right\}\left\{ \begin{matrix}k\\l\end{matrix}\right\} \bigg(\frac{(np)^{m+l-1}(1-p)}{(m-1)!(l-1)!}\notag\\ &\quad +\sum_{s=1}^{\min\{m,l\}}\frac{(np)^{m+l-s}(1-p^s)}{s!(m-s)!(l-s)!}\bigg)\Big(1+O\Big(\frac1n\Big)\Big).\end{align}
In particular, for
$k=1,2,3$
, expressions (17) and (18) reduce to
\begin{align*} \mathbb{E} [Z^{(1)}_n]&=n^2p\Big(1+O\Big(\frac1n\Big)\Big),\\ \mathrm{Var} [Z^{(1)}_n]&=2n^2p(1-p)\Big(1+O\Big(\frac1n\Big)\Big);\\ \mathbb{E} [Z^{(2)}_n]&=n^2p(np+1)\Big(1+O\Big(\frac1n\Big)\Big),\\ \mathrm{Var} [Z^{(2)}_n]&=2n^2p(1-p)\big(4n^2p^2+5np+1\big)\Big(1+O\Big(\frac1n\Big)\Big);\\ \mathbb{E} [Z^{(3)}_n]&=n^2p\big(n^2p^2+3np+1\big)\Big(1+O\Big(\frac1n\Big)\Big),\\ \mathrm{Var} [Z^{(3)}_n]&=2n^2p(1-p)\big(9n^4p^4+45n^3p^3+63n^2p^2+21np+1\big)\Big(1+O\Big(\frac1n\Big)\Big).\end{align*}
The first two moments of
$Z^{(k)}_n$
given in (17) and (18) lead to the following results on weak convergence, which generalize Propositions 1 and 2 in [Reference Feng, Hu and Su15] from
$k=2$
to general cases.
Proposition 3. Let
$Z^{(k)}_n$
be the kth-order generalized Zagreb index of G(n, p). As
$n\rightarrow\infty$
, the following assertions hold for any
$k\ge1$
.
-
(i) If
$n^2p\rightarrow 0$
, then
$ Z^{(k)}_n \buildrel {P} \over \longrightarrow 0$
. -
(ii) If there exists a constant
$\lambda>0$
such that
$n^2 p\rightarrow\lambda$
, then
$Z^{(k)}_n/2 \buildrel {D} \over \longrightarrow \mathrm{Poi}(\lambda/2)$
. -
(iii) If
$n^2 p\rightarrow \infty$
, then
$Z^{(k)}_n/ \mathbb{E} [Z^{(k)}_n] \buildrel {P} \over \longrightarrow 1$
. -
(iv) If
$n^2(1-p)\rightarrow 0$
, then
$\mathbb{P}(Z^{(k)}_n=n(n-1)^k)\rightarrow 1$
. -
(v) If there exists a constant
$\lambda>0$
such that
$n^2 (1-p)\rightarrow \lambda$
, then
\begin{align*}\frac{n(n-1)^k-Z^{(k)}_n}{2kn^{k-1}} \buildrel {D} \over \longrightarrow \mathrm{Poi}(\lambda/2).\end{align*}
-
(vi) If
$n^2 (1-p)\rightarrow \infty$
, then
\begin{align*}\frac{n(n-1)^k-Z^{(k)}_n}{n^{k+1}(1-p^k)}\buildrel {P} \over \longrightarrow 1.\end{align*}
Proof. We prove the assertions in Proposition 3 in turn. If
$n^2 p\rightarrow 0$
, by (17) and (18), both
$\mathbb{E} [Z^{(k)}_n]$
and
$\mathrm{Var} [Z^{(k)}_n]$
tend to 0 for any
$k\ge 1$
, which implies (i). In fact, under the condition
$n^2 p\rightarrow 0$
, the probability that G(n, p) is an empty graph tends to 1.
Assume that
$n^2 p\rightarrow \lambda>0$
. Then, for any
$m\ge2$
, it follows that
$n^{m+1}p^m\to 0$
. This implies that for any
$m\ge2$
, both
$\mathbb{E} [S_{m+1,n}]$
and
$\mathrm{Var} [S_{m+1,n}]$
tend to 0, by (12) and (14). Therefore, similarly to (i), we can obtain that
$S_{m+1,n}$
converges in probability to 0 for any
$m\ge2$
. This implies that, by Proposition 1, for any
$k\ge2$
, the index
$Z^{(k)}_n$
has the same asymptotic behavior as
$S_{2,n}$
, which is equal to twice the number of edges in G(n, p). To prove (ii), it is sufficient to show that
$S_{2,n}/2$
converges in distribution to
$\textrm{Poi}(\lambda/2)$
, which, in fact, is already known (see, for example, Theorem 3.19 in [Reference Janson, Łuczak and Ruciński24]).
If
$n^2 p\rightarrow \infty$
, it follows by (17) and (18) that
$\mathrm{Var} [Z^{(k)}_n]=o((\mathbb{E} [Z^{(k)}_n])^2)$
whether np converges or not. Then (iii) holds by Chebyshev’s inequality.
To prove (iv) and (v), we shall consider
$\overline{G}(n, p)$
, the complement graph of G(n, p). Recall that the graphs
$\overline{G}(n, p)$
and G(n, p) have the same vertex set
$\{1,2,\ldots,n\}$
, but any two distinct vertices are adjacent in
$\overline{G}(n, p)$
if and only if they are not adjacent in G(n, p). For any two vertices
$1\le i\neq j\le n$
, denote by
$\overline{I}_{ij}$
the indicator of the existence of an edge between i and j in
$\overline{G}(n, p)$
. Then we have that
$\overline{I}_{ii}=0$
, and
\begin{align*} \overline{I}_{ij}+I_{ij}=1, \quad 1\le i\neq j\le n. \end{align*}
If
$n^2(1-p) \rightarrow 0$
, by symmetry, (i) implies that the probability that
$\overline{G}(n, p)$
is empty tends to 1, and thus G(n, p) is a complete graph with probability tending to 1. Then (iv) holds by the fact that the kth-order generalized Zagreb index of a complete graph on n vertices is
$n(n-1)^k$
for any
$k\ge1$
.
In the complementary graph
$\overline G(n, p)$
, we also define
$\overline{S}_{m,n}$
to be the number of m-stars for any
$m\ge1$
, and
$\overline{Z}_{n}^{(k)}=\sum_{i=1}^n(\sum_{j=1}^n \overline I_{ij})^k$
to be the kth-order generalized Zagreb index. Note that
\begin{align} Z_{n}^{(k)} &= \sum_{i=1}^n\bigg(n-1-\sum_{j=1}^n \overline{I}_{ij}\bigg)^k \notag\\ &= n(n-1)^k+\sum_{i=1}^n\sum_{m=1}^k (\!-1)^m \binom{k}{m}(n-1)^{k-m}\bigg(\sum_{j=1}^n\overline{I}_{ij} \bigg)^m\notag\\ &= n(n-1)^k+\sum_{m=1}^k (\!-1)^m \binom{k}{m}(n-1)^{k-m}\overline{Z}_{n}^{(m)} \end{align}
and
\begin{align} -\sum_{m=1}^k (\!-1)^m \binom{k}{m}(n-1)^{k-m}=(n-1)^k-(n-2)^k=kn^{k-1}\Big(1+O\Big(\frac1n\Big)\Big). \end{align}
By Proposition 1, we have
\begin{align*} \overline{Z}_{n}^{(k)}=\sum_{m=1}^k m!\left\{ \begin{matrix}k\\m\end{matrix}\right\}\overline{S}_{m+1,n}. \end{align*}
Therefore, if
$n^2(1-p)\to\lambda$
, from the proof of (ii) it follows that
$\mathbb{P}(\overline{Z}_{n}^{(k)}=\overline{S}_{2,n})\to1$
for any given
$k\ge1$
, and
$\overline{S}_{2,n}/2 \buildrel {P} \over \longrightarrow \mathrm{Poi}(\lambda/2)$
. Hence, assertion (v) holds by (19) and (20).
If
$n^2 (1-p)\rightarrow \infty$
, it follows that, by (17),
\begin{align*} n(n-1)^k-\mathbb{E}[Z^{(k)}_n]&=n(n-1)^k-\sum_{m=1}^k \left\{ \begin{matrix}k\\m\end{matrix}\right\}n^{m+1}p^m\\ &=n^{k+1}(1-p^k)\Big(1+O\Big(\frac1n\Big)\Big) \end{align*}
and that, by (18),
\begin{align*} \mathrm{Var} [n(n-1)^k-Z^{(k)}_n]=\mathrm{Var}[Z^{(k)}_n] =O(n^{2k}(1-p)) =o\big(\mathbb{E}\big[n(n-1)^k-Z^{(k)}_n\big]^2\big). \end{align*}
This implies that (vi) holds by Chebyshev’s inequality, and thus completes the proof of Proposition 3.
4. Asymptotic Normality of Generalized Zagreb Indices
In this section, we shall establish the asymptotic normality of the generalized Zagreb indices of G(n, p). As in the previous section, our methodology depends heavily on the limiting behaviors of the numbers of star graphs of various sizes. Indeed, there is a substantial body of research on the asymptotic properties of subgraph counts in G(n, p) that has been conducted over several decades (see [Reference Janson, Łuczak and Ruciński24] and references therein). A necessary and sufficient condition for asymptotic normality of the number of a given subgraph was first given by Ruciński [Reference Ruciński36]. More precisely, for any fixed simple graph
$\mathbb{H}$
, let
$H_n=H_n(\mathbb{H})$
denote the number of subgraphs of G(n, p) that are isomorphic to
$\mathbb{H}$
. As
$n\to\infty$
, the normalized random variable
$(H_n-\mathbb{E}[H_n])/\sqrt{\mathrm{Var}[H_n]}$
converges in distribution to the standard normal distribution N(0,1) if and only if
\[\min_{\mathbb{G}\subset \mathbb{H}:\, e_{\mathbb{G}}\ge1}\big\{n^{v_\mathbb{G}}p^{e_\mathbb{G}}\big\}\to\infty \quad \mbox{and} \quad n^2(1-p)\to\infty,\]
where
$v_\mathbb{G}$
and
$e_\mathbb{G}$
stand for the numbers of vertices and edges of
$\mathbb{G}$
, respectively. In particular, for the number of m-stars
$S_{m,n}$
in G(n, p) with any fixed
$m\ge2$
, we have that
$(S_{m,n}-\mathbb{E}[S_{m,n}])/\sqrt{\mathrm{Var}[S_{m,n}]}$
converges in distribution to N(0,1) if and only if one of the following three conditions holds: (1)
$np\to 0$
and
$n^{m+1}p^m\to\infty$
; (2)
$np\to c$
for some constant
$c > 0$
; (3)
$np\to\infty$
and
$n^2(1-p)\to\infty$
. Until recently, Ruciński’s result was complemented by explicit bounds on the Kolmogorov distance in [Reference Privault and Serafin33]; see also [Reference Eichelsbacher and Rednoss13, Reference Röllin35]. When
$0<p<1$
is fixed, the joint normality of the numbers of several distinct subgraphs is shown in [Reference Janson and Nowicki25, Reference Reinert and Röllin34], with a corresponding result on the convergence rate in [Reference Krokowski and Thäle27]. In addition to ER random graphs, the problems of subgraph counting are also considered in other random graph models, such as the Poisson random connection model [Reference Liu and Privault30, Reference Penrose32], the graphon-based random graphs [Reference Bhattacharya, Chatterjee and Janson3, Reference Kaur and Röllin26], the uniform attachment model [Reference Björklund, Holmgren, Janson and Lo4], and the random hypergraphs [Reference De Jong9, Reference Michalczuk, Nieradko and Serafin31].
The following theorem establishes the joint asymptotic normality of the numbers of k different stars under suitable conditions where p is allowed to be vary with n.
Theorem 1. For any
$m\ge 2$
, let
$S_{m,n}$
be the number of m-stars in G(n,p). For any given integer
$k\ge 1$
, as
$n\rightarrow \infty$
, the following assertions hold.
-
(i) If
$np\rightarrow c$
for some constant
$c > 0$
, then where
\begin{equation*} \frac{1}{\sqrt{n}}\big( S_{2,n}-\mathbb{E}[S_{2,n}],S_{3,n}-\mathbb{E}[S_{3,n}],\ldots, S_{k+1,n}-\mathbb{E}[S_{k+1,n}] \big)^{\top}\buildrel {D} \over \longrightarrow N\big({\boldsymbol{0}},\boldsymbol{\Sigma}_{k}^{\star}\big), \end{equation*}
$\boldsymbol{0}$
is a k-dimensional vector of zeros, and the (m, l)th entry of the covariance matrix
$\boldsymbol{\Sigma}_{k}^{\star}$
is given by
\begin{equation*} \sigma_{ml}^{\star}=\frac{c^{m+l-1}}{(m-1)!(l-1)!} +\sum_{s=1}^{\min(m,l)}\frac{c^{m+l-s}}{s!(m-s)!(l-s)!}, \quad 1\le m,l\le k. \end{equation*}
-
(ii) If
$np\rightarrow \infty$
and
$n^2 (1-p)^3\rightarrow \infty$
, then, where
\begin{equation*} \sqrt{\frac{p}{2(1-p)}} \Bigg( \frac{S_{2,n}-\mathbb{E}[S_{2,n}]}{np},\frac{S_{3,n}-\mathbb{E}[S_{3,n}]}{(np)^2},\ldots,\frac{S_{k+1,n}-\mathbb{E}[S_{k+1,n}]}{\frac{1}{(k-1)!}(np)^k} \Bigg)^{\top}\buildrel {D} \over \longrightarrow N\big(\boldsymbol{0},\mathbf{U}_{k}\big), \end{equation*}
$\mathbf{U}_{k}$
is a matrix of order k with all entries equal to 1.
It is noteworthy that in both (i) and (ii) of Theorem 1, the expectation
$\mathbb{E}[S_{m+1,n}]$
cannot be replaced by its leading term for any
$1 \le m \le k$
, since Slutsky’s theorem cannot be directly applied here. The reason is as follows. We first consider (ii) in the special case where
$p\in(0,1)$
is a constant. By (12) and (14), we now have that the difference
$\mathbb{E}[S_{m+1,n}]-n^{m+1}p^m/m!=O(n^m)$
is of the same order as the standard deviation of
$S_{m+1,n}$
. Then, in case (i), also by (12) and (14) we have that for any
$m\ge1$
,
\begin{align} \mathbb{E}[S_{m+1,n}]&\sim \frac{c^{m}}{m!}n, \end{align}
\begin{align} \mathrm{Var}[S_{m+1,n}]&\sim \bigg(\frac{c^{2m-1}}{[(m-1)!]^2}+\sum_{s=1}^{m}\frac{c^{2m-s}}{s![(m-s)!]^2}\bigg)n, \\[8pt]\nonumber\end{align}
both of which are of the same order n. At this time, we choose the probabilities
$p=c(1+a_n)^{1/m}/n$
, such that the sequence
$\{a_n, n\ge1\}$
satisfies
$a_n\to 0$
and
$\lim\sqrt{n}\,a_n>0$
. After straightforward calculations, from (7) one can obtain
\begin{align*}\mathbb{E}[S_{m+1,n}]-n{c^{m}}/{m!}=n\binom{n-1}{m}p^m-n{c^{m}}/{m!}=\frac{c^{m}n}{m!}\Big(a_n+O\Big(\frac1n\Big)\Big).\end{align*}
Therefore, we cannot assert that the difference
$\mathbb{E}[S_{m+1,n}]-nc^m/m!$
is of order
$o(\sqrt{n})$
, due to the assumption that
$\sqrt{n}\,a_n$
converges to a positive limit.
Before proving Theorem 1, we shall briefly introduce the concept of the dependency graph for random variables [Reference Janson, Łuczak and Ruciński24]. Let
$\{X_i\}_{i\in {\mathcal I}}$
be a family of random variables defined on a common probability space, where
${\mathcal I}$
is an index set. A dependency graph for
$\{X_i\}_{i\in {\mathcal I}}$
is any graph L with the vertex set
${\mathcal I}$
, such that, for any two disjoint subsets
${\mathcal A}, {\mathcal B}\subset {\mathcal I}$
, if there exist no edges between them, the families
$\{X_i\}_{i\in {\mathcal A}}$
and
$\{X_j\}_{j\in {\mathcal B}}$
are mutually independent. For any integer
$m\ge1$
and
$i_1,i_2,\ldots,i_m\in {\mathcal I}$
, let
\begin{align} \overline{N}_L(i_1,i_2,\ldots,i_m)=\bigcup_{s=1}^m\{j\in{\mathcal I}\,:\, j=i_s\ \mbox{or there exists an edge between}\ j\ \mbox{and}\ i_s\ \mbox{in}\ L\}\end{align}
denote the closed neighborhood of vertices
$i_1,i_2,\ldots,i_m$
in L.
The following auxiliary lemma, stated as Theorem 6.33 in [Reference Janson, Łuczak and Ruciński24], is a particularly useful tool to determine the asymptotic normality of the sum of a family of dependent random variables.
Lemma 1. Let
$\{Y_n\}_{n=1}^{\infty}$
be a sequence of random variables such that
$Y_n=\sum_{\alpha\in {\mathcal A}_n}X_{n\alpha}$
, where for each n, the random variables
$\{X_{n\alpha}\,:\, \alpha\in {\mathcal A}_n\}$
have dependency graph
$L_n$
. Suppose that there exist numbers
$M_n$
and
$Q_n$
such that
$\sum_{\alpha\in {\mathcal A}_n}\mathbb{E}[|X_{n\alpha}|]\le M_n$
, and for every
$\alpha_1,\alpha_2$
,
\begin{align*} \sum_{\alpha\in \overline{N}_{L_n}(\alpha_1,\alpha_2)}\mathbb{E}\big[|X_{n\alpha}|\big|X_{n\alpha_1},X_{n\alpha_2}\big]\le Q_n. \end{align*}
As
$n\to \infty$
, if
$M_nQ_n^2/(\mathrm{Var}[Y_n])^{3/2} \to 0$
, then
\begin{align*} \frac{Y_n-\mathbb{E}[Y_n]}{\sqrt{\mathrm{Var}[Y_n]}}\buildrel {D} \over \longrightarrow N(0,1). \end{align*}
We now give a formal proof of Theorem 1.
Proof of Theorem
1. If
$np\to c$
for some constant
$c>0$
, it follows by (13) that
\begin{equation} \lim_{n\to\infty}\textrm{cov}\bigg(\frac{S_{m+1,n}}{\sqrt{n}},\frac{S_{l+1,n}}{\sqrt{n}}\bigg)=\frac{c^{m+l-1}}{(m-1)!(l-1)!}+ \sum_{s=1}^{\min\{m,l\}}\frac{c^{m+l-s}}{s!(m-s)!(l-s)!}, \end{equation}
for
$ m,l\ge1$
. Then, by (24), the limit of the covariance matrix
$\textrm{cov}(\mathbf{S}_{k,n}/\sqrt{n})$
, where the random vector
\begin{align*} \mathbf{S}_{k,n}\,:\!=\big(S_{2,n}, S_{3,n},\ldots,S_{k+1,n}\big)^{\top}, \end{align*}
is given by
\begin{align} \boldsymbol{\Sigma}_{k}^{\star}=\left( \begin{array}{cccc} 2c & \frac{2c^2}{1!} & \cdots & \frac{2c^k}{(k-1)!}\\ \frac{2c^2}{1!} & \frac{2c^3}{1!}+\frac{c^2}{2!} & \cdots & \frac{2c^{k+1}}{(k-1)!}+\frac{c^k}{2!(k-2)!}\\ \frac{2c^3}{2!} & \frac{2c^4}{2!}+\frac{c^3}{2!1!} & \cdots & \frac{2c^{k+2}}{2!(k-1)!}+\frac{c^{k+1}}{2!(k-2)!}+\frac{c^k}{3!(k-3)!}\\ \vdots & \vdots & \ddots & \vdots\\ \frac{2c^k}{(k-1)!} & \frac{2c^{k+1}}{(k-1)!}+\frac{c^k}{2!(k-2)!} & \cdots & \frac{c^{2k-1}}{[(k-1)!]^2} +\sum_{s=1}^k\frac{c^{2k-s}}{s![(k-s)!]^2} \\ \end{array} \right). \end{align}
For all
$1\le m < k$
and for all
$m < l\le k$
, by adding
$-c^{l-m}/(l-m)!$
times the mth column to the lth column, we can obtain a triangular matrix with diagonal elements
$2c, c^2/2!, c^3/3!,\ldots, c^k/k!$
. Hence, the determinant of
$\boldsymbol{\Sigma}_{k}^{\star}$
is
\begin{equation*} \det \big(\boldsymbol{\Sigma}_{k}^{\star}\big)=2c^{\frac{k(k+1)}{2}}\prod_{m=1}^{k}\frac{1}{m!}, \end{equation*}
which implies that
$\boldsymbol{\Sigma}_{k}^{\star}$
is a positive definite matrix for any
$k\ge1$
. Consequently, there exists a real number
$\lambda_{\min}>0$
, which only depends on c and k, such that
$\lambda_{\min}$
is the smallest eigenvalue of
$\boldsymbol{\Sigma}_k^{\star}$
.
To prove (i), we use the well-known Cramér–Wold theorem. For any given integer
$k\ge1$
, consider an arbitrary linear combination of the form
\begin{equation} T_{k,n}=\sum_{m=1}^{k} a_{m} S_{m+1,n}, \end{equation}
where
$a_1, a_2,\ldots,a_k$
are real numbers such that
$\sum_{m=1}^k a_m^2=1$
. Then we have that
$|a_m|\le 1$
for all
$1\le m\le k$
. Then, by Slutsky’s theorem together with (22), it is sufficient to show that
\begin{equation} \frac{T_{k,n}-\mathbb{E} [T_{k,n}]}{\sqrt{\mathrm{Var} [T_{k,n}]}}\buildrel {D} \over \longrightarrow N(0,1). \end{equation}
To apply Lemma 1, let us denote by
$\{\mathbb{S}_{n\alpha}\}_{\alpha \in {\mathcal B}_n}$
the set of all possible
$(m+1)$
-stars in G(n, p) for
$1\le m\le k$
, where
${\mathcal B}_n$
is an index set with cardinality
\begin{equation} |{\mathcal B}_n|=n\sum_{m=1}^{k}\binom{n-1}{m}. \end{equation}
For any
$\alpha \in {\mathcal B}_n$
, let
$s_{n\alpha}$
be the size of
$\mathbb{S}_{n\alpha}$
(i.e. the number of vertices in
$\mathbb{S}_{n\alpha}$
),
\begin{equation} I_{n\alpha}=I(\mathbb{S}_{n\alpha}\ \mbox{is contained in}\ G(n,p)) \quad \mbox{and} \quad X_{n\alpha}=a_{s_{n\alpha}-1}I_{n\alpha}. \end{equation}
Then the sum
$T_{k,n}$
given in (26) can be rewritten as
\begin{equation*} T_{k,n}=\sum_{\alpha\in {\mathcal B}_n}X_{n\alpha}. \end{equation*}
Further, we can construct a dependency graph
$L_n$
with the vertex set
${\mathcal B}_n$
for the random variables
$\{X_{n\alpha}\,:\,\alpha\in {\mathcal B}_n\}$
as follows. In this context, all the
$(m+1)$
-stars with
$1\le m\le k$
in
$\mathbb{K}_n$
, the complete graph with vertex set
$\{1,2,\ldots,n\}$
, are now regarded as the new ‘vertices’ in
$L_n$
. Then the number of vertices in
$L_n$
is
$|{\mathcal B}_n|$
, which is given by (28). In order to form the edge set of
$L_n$
, for each pair of vertices
$\alpha$
and
$\beta$
in
${\mathcal B}_n$
we connect them by an edge if their corresponding star graphs
$\mathbb{S}_{n\alpha}$
and
$\mathbb{S}_{n\beta}$
have at least one common edge in
$\mathbb{K}_n$
.
We now verify the condition in Lemma 1. By definition it is clear to see that
\begin{equation} \sum_{\alpha\in {\mathcal B}_n}\mathbb{E} [|X_{n\alpha}|]\le \sum_{m=1}^{k} \mathbb{E}[S_{m+1,n}]. \end{equation}
Then, by (21) and (30), we have that when n is sufficiently large,
\begin{equation} \sum_{\alpha\in {\mathcal B}_n}\mathbb{E} [|X_{n\alpha}|]\le M_n\,:\!=2n\sum_{m=1}^{k}\frac{c^m}{m!}, \end{equation}
which is of order n. For any given
$\alpha_1,\alpha_2 \in {\mathcal B}_n$
, let
$V_n=V_n(\alpha_1,\alpha_2)$
be the vertex set of the subgraph
$\mathbb{S}_{n\alpha_1}\cup \mathbb{S}_{n\alpha_2}$
. Since the size of
$\mathbb{S}_{n\alpha}$
is at most
$k+1$
for any
$\alpha\in {\mathcal B}_n$
, the number of vertices in
$V_n$
does not exceed
$2(k+1)$
. Recall the definition of the closed neighborhood of given vertices in a dependency graph, as given in (23). Then
$\overline N_{L_n}(\alpha_1,\alpha_2)$
, which is a subset of
${\mathcal B}_n$
, represents all the star graphs of size at most
$k+1$
in
$\mathbb{K}_n$
that share at least one edge with either
$\mathbb{S}_{n\alpha_1}$
or
$\mathbb{S}_{n\alpha_2}$
. For any
$\alpha\in \overline N_{L_n}(\alpha_1,\alpha_2)$
, consider the number of vertices in
$\mathbb{S}_{n\alpha}$
that are not in
$V_n$
. Denote
\begin{equation*} \overline N_s=\big\{\alpha\in \overline N_{L_n}(\alpha_1,\alpha_2)\,:\, \mathbb{S}_{n\alpha}\ \textrm{has exactly}\ s\ \textrm{vertices out of}\ V_n\big\}, \end{equation*}
for
$s=0,1,\dots,k-1$
. Then
$\bigcup_{s=0}^{k-1}\overline N_s=\overline N_{L_n}(\alpha_1,\alpha_2)$
, and for any
$0\le s\le k-1$
there exists a sufficiently large number
$C_k$
, which does not depend on n but on k, such that the number of star graphs in
$\overline N_s$
is not greater than
$C_k\binom{n-2}{s}$
. Since, for any
$\alpha\in\overline N_s$
,
\begin{equation*} \mathbb{E} \big[|X_{n\alpha}|\big|X_{n\alpha_1},X_{n\alpha_2}\big]\le p^s, \end{equation*}
we have
\begin{equation} \sum_{\alpha\in \overline N_s}\mathbb{E}\big[|X_{n\alpha}|\big|X_{n\alpha_1},X_{n\alpha_2}\big] \le C_k\binom{n-2}{s}p^s, \quad 0\le s\le k-1, \end{equation}
for sufficiently large n. Then, by (32), we can set
\begin{equation} Q_n=2C_k\sum_{s=0}^{k-1}\frac{c^s}{s!}, \end{equation}
which is a constant, regardless of n. Recall that
$\lambda_{\min}>0$
is the smallest eigenvalue of the limiting covariance matrix
$\boldsymbol{\Sigma}_k^{\star}$
given in (25). Then it follows that, for sufficiently large n,
\begin{equation*} \mathrm{Var} \bigg(\frac{T_{k,n}}{\sqrt{n}}\bigg) =\mathbf{a}^{\top}\textrm{cov}\Big(\frac{\mathbf{S}_{k,n}}{\sqrt{n}}\Big)\mathbf{a}\ge \lambda_{\min}(1+o(1)), \end{equation*}
where
$\mathbf{a}$
denotes the vector
$(a_1,a_2,\ldots,a_k)^{\top}$
. This implies that the variance of
$T_{k,n}$
is of order n. Collecting the orders of magnitude of
$M_n$
in (31) and
$Q_n$
in (33), we thus have
\begin{equation*} \frac{M_nQ_n^2}{(\mathrm{Var} [T_{k,n}])^{3/2}}=O\Big(\frac1{\sqrt n}\Big)\to 0. \end{equation*}
This proves (27) by Lemma 1, and thus (i) holds.
Next we prove (ii). If
$np\rightarrow \infty$
and
$n^{2}(1-p)^3\rightarrow \infty$
, by (13) and (14) we have that
\begin{align} \textrm{cov}(S_{m+1,n},S_{l+1,n})=\frac{2}{(m-1)!(l-1)!}n^{m+l}p^{m+l-1}(1-p)\Big(1+O\Big(\frac1{np}\Big)\Big), \quad m,l\ge1, \end{align}
and
\begin{align} \mathrm{Var}[S_{m+1,n}]=\frac{2}{[(m-1)!]^2}n^{2m}p^{2m-1}(1-p)\Big(1+O\Big(\frac1{np}\Big)\Big), \quad m\ge1. \end{align}
Denote
\begin{align*} S_{m+1,n}'\,:\!=\frac{S_{m+1,n}}{\sqrt{n^{2m}p^{2m-1}(1-p)}}, \quad 1\le m\le k. \end{align*}
Then the linear combination
\begin{align*} T_{k,n}'\,:\!=\sum_{m=1}^ka_mS_{m+1,n}'=\sum_{\alpha\in {\mathcal B}_n}X_{n\alpha}', \end{align*}
where
$a_1, a_2,\ldots,a_k$
are arbitrary real numbers such that
$\sum_{m=1}^k a_m^2=1$
, and
\begin{align*} X'_{n\alpha}=\frac{X_{n\alpha}}{\sqrt{n^{2s_{n\alpha}-2}p^{2s_{n\alpha}-3}(1-p)}},\quad \alpha \in {\mathcal B}_n, \end{align*}
with random variables
$X_{n\alpha}$
given by (29).
By (35), we have that
$\mathrm{Var} [T'_{k,n}]$
is of order 1. It follows by (12) that we can set
\begin{align*} M_n'&\,:\!=\sum_{m=1}^{k} \mathbb{E}[S_{m+1,n}']=O\Big(n\sqrt{\frac{p}{1-p}}\Big). \end{align*}
For any
$1\le s\le k-1$
, it follows by (32) that
\begin{align*} \sum_{\alpha\in \overline N_s}\mathbb{E}\big[|X_{n\alpha}'|\big|X_{n\alpha_1}',X_{n\alpha_2}'\big] & = \sqrt{\frac{p}{1-p}}\sum_{\alpha\in \overline N_s}\frac{\mathbb{E}\big[|X_{n\alpha}|\big|X_{n\alpha_1},X_{n\alpha_2}\big]}{(np)^{s_{n\alpha}-1}}\\ & \le \frac{1}{(np)^{s+1}}\sqrt{\frac{p}{1-p}}\sum_{\alpha\in \overline N_s}\mathbb{E}\big[|X_{n\alpha}|\big|X_{n\alpha_1},X_{n\alpha_2}\big]\\ & =O\Big(\frac{1}{n\sqrt{p(1-p)}}\Big). \end{align*}
Analogously to (33), for every
$\alpha_1,\alpha_2 \in {\mathcal B}_n$
, there exists a constant
$Q_n'$
such that
\begin{align*} \sum_{\alpha\in \overline N_L(\alpha_1,\alpha_2)}\mathbb{E}\big[|X_{n\alpha}'|\big|X_{n\alpha_1}',X_{n\alpha_2}'\big]= \sum_{s=0}^{k-1}\sum_{\alpha\in \overline N_s}\mathbb{E}\big[|X_{n\alpha}'|\big|X_{n\alpha_1}',X_{n\alpha_2}'\big]\le Q_n' =O\Big(\frac{1}{n\sqrt{p(1-p)}}\Big). \end{align*}
Thus, we have
\begin{equation*} \frac{M_n'(Q_n')^2}{(\mathrm{Var} [T_{k,n}'])^{3/2}}=O\bigg(\frac{1}{\sqrt{n^{2}p(1-p)^3}}\bigg). \end{equation*}
Note that now the correlation coefficient of
$S_{m+1,n}$
and
$S_{l+1,n}$
tends to 1 whenever
$np\to\infty$
, by (34) and (35). Since
$np\rightarrow \infty$
and
$n^{2}(1-p)^3\rightarrow \infty$
imply
$n^{2}p(1-p)^3\to \infty$
, it follows by Lemma 1 that (ii) holds, completing the proof of Theorem 1.
For any given integer
$k\ge2$
, Theorem 1 gives us a tool to study the joint asymptotic normality of the first k generalized Zagreb indices, as
$n\to\infty$
. Let
$\mathbf{Z}_{k,n}$
denote the random vector
$(Z_n^{(1)}, Z_n^{(2)},\ldots,Z_n^{(k)})^{\top}$
. It thus follows from Proposition 1 that
\begin{align*} \mathbf{Z}_{k,n}=\mathbf{A}_k\mathbf{S}_{k,n},\end{align*}
where
$\mathbf{A}_k=(a_{ml})_{k\times k}$
is a lower triangular matrix, which does not depend on n, with
\begin{align*} a_{ml}=\left\{\begin{array}{cc} l!\left\{ \begin{matrix}m\\l\end{matrix}\right\}, & m\ge l, \\[2pt] 0, & m < l. \end{array}\right.\end{align*}
Therefore, under the same conditions in Theorem 1, the random vector
$\mathbf{Z}_{k,n}$
has asymptotic normality when suitably normalized.
Theorem 2. For any
$m\ge 1$
, let
$Z^{(m)}_n$
be the mth-order generalized Zagreb index of G(n, p). For any given integer
$k\ge 2$
, as
$n\rightarrow \infty$
, the following assertions hold.
-
(i) If
$np\rightarrow c$
for some constant
$c > 0$
, then where the covariance matrix
\begin{equation*} \frac{1}{\sqrt{n}}\big(Z^{(1)}_n-\mathbb{E}[Z^{(1)}_n],Z^{(2)}_n-\mathbb{E}[Z^{(2)}_n],\ldots, Z^{(k)}_n-\mathbb{E}[Z^{(k)}_n] \big)^{\top}\buildrel {D} \over \longrightarrow N(\boldsymbol{0},\boldsymbol{\Sigma}_k), \end{equation*}
$\boldsymbol{\Sigma}_k=(\sigma_{ml})_{k\times k}$
is given by
\begin{equation*} \sigma_{ml}=\sum_{i=1}^{m}\sum_{j=1}^{l}\left\{ \begin{matrix}m\\i\end{matrix}\right\}\left\{ \begin{matrix}l\\j\end{matrix}\right\} \bigg[ij c^{i+j-1}+\sum_{s=1}^{\min\{i,j\}}\frac{i!\,j!\, c^{i+j-s}}{s!(i-s)!(j-s)!}\bigg], \quad 1\le m,l\le k. \end{equation*}
-
(ii) If
$np\rightarrow \infty$
and
$n^2 (1-p)^3\rightarrow \infty$
, then
\begin{equation*} \sqrt{\frac{p}{2(1-p)}} \bigg( \frac{Z^{(1)}_n-\mathbb{E}[Z^{(1)}_n]}{np},\frac{Z^{(2)}_n-\mathbb{E}[Z^{(2)}_n]}{2(np)^2},\ldots,\frac{Z^{(k)}_n-\mathbb{E}[Z^{(k)}_n]}{k(np)^k} \bigg)^{\top}\buildrel {D} \over \longrightarrow N\big(\boldsymbol{0},\mathbf{U}_{k}\big). \end{equation*}
-
(iii) If
$np\rightarrow 0$
and
$n^{2}p\rightarrow \infty$
, then
\begin{equation*} \frac{1}{\sqrt{2n^2p}}\bigg(Z^{(1)}_n-n^2p,Z^{(2)}_n-n^3p^2-n^2p,\ldots,Z^{(k)}_n-\sum_{m=1}^k \left\{ \begin{matrix}k\\m\end{matrix}\right\}n^{m+1}p^m\bigg)^{\top}\buildrel {D} \over \longrightarrow N\big(\boldsymbol{0},\mathbf{U}_{k}\big). \end{equation*}
Proof. Similarly to Proposition 2, for any integers
$m,l\ge1$
, after straightforward calculations we can first obtain that the asymptotic covariance of
$Z^{(m)}_n$
and
$Z^{(l)}_n$
is given by
\begin{align} \textrm{cov} \big(Z^{(m)}_n,Z^{(l)}_n\big)&=n\sum_{i=1}^{m}\sum_{j=1}^{l}\left\{ \begin{matrix}m\\i\end{matrix}\right\}\left\{ \begin{matrix}l\\j\end{matrix}\right\} \bigg[ij(np)^{i+j-1}(1-p) \notag\\ &\quad +\sum_{s=1}^{\min\{i,j\}} \frac{i!\,j!}{s!(i-s)!(j-s)!}(np)^{i+j-s}(1-p^s) \bigg]\Big(1+O\Big(\frac1n\Big)\Big). \end{align}
We first consider (i). Since Theorem 1, together with Proposition 1, guarantees the asymptotic normality of the k-dimensional random vector
$(\mathbf{Z}_{k,n}-\mathbb{E} [\mathbf{Z}_{k,n}])/\sqrt{n}$
, by Slutsky’s theorem it is sufficient to check its asymptotic covariance matrix. Thus, (i) follows directly by (36).
The proof of (ii) is similar to that of (i). By (18), we have that
$\mathrm{Var}[Z^{(k)}_n]\sim 2k^2n^{2k}p^{2k-1}(1-p)$
for any
$k\ge1$
. It thus follows by (36) that for any
$1\le m\le l\le k$
, the correlation coefficient of
$(Z^{(m)}_n-\mathbb{E}[Z^{(m)}_n])/[m(np)^m]$
and
$(Z^{(l)}_n-\mathbb{E}[Z^{(l)}_n])/[l(np)^l]$
tends to 1, as
$n\to\infty$
. Then (ii) holds.
We next prove (iii). If
$np\rightarrow 0$
and
$n^{2}p\rightarrow \infty$
, by (12) and (14) we now have that
$\mathbb{E}[S_{m+1,n}]\sim {n^{m+1}p^m}/{m!}$
for
$m\ge1$
, and
\begin{align*} \mathrm{Var}[S_{2,n}]\sim 2n^{2}p, \quad \mathrm{Var}[S_{m+1,n}]\sim \frac{n^{m+1}p^m}{m!}, \quad m\ge2, \end{align*}
which implies that for any
$m\ge2$
,
\begin{align*} \mathbb{E}[S_{m+1,n}]=o(\mathbb{E}[S_{2,n}]), \quad \mathrm{Var}[S_{m+1,n}]=o(\mathrm{Var}[S_{2,n}]). \end{align*}
Using Chebyshev’s inequality, it thus follows from Proposition 1 that, for any
$k\ge2$
,
\begin{align} \frac{(Z^{(k)}_n-\mathbb{E} [Z^{(k)}_n])-(S_{2,n}-\mathbb{E}[S_{2,n}])}{\sqrt{\mathrm{Var}[S_{2,n}]}} =\frac{\sum_{m=2}^km!\left\{ \begin{matrix}k\\m\end{matrix}\right\}(S_{m+1,n}-\mathbb{E}[S_{m+1,n}])}{\sqrt{\mathrm{Var}[S_{2,n}]}} \buildrel {P} \over \longrightarrow 0. \end{align}
This says that the quantity
$S_{2,n}$
makes a dominant contribution to the kth-order generalized Zagreb index for any
$k\ge1$
if
$np\rightarrow 0$
and
$n^{2}p\rightarrow \infty$
. On the other hand, applying Theorem 6.5 in [Reference Janson, Łuczak and Ruciński24], we have
\begin{align*} \frac{S_{2,n}-\mathbb{E}[S_{2,n}]}{\sqrt{\mathrm{Var}[S_{2,n}]}}\buildrel {D} \over \longrightarrow N(0,1), \end{align*}
which, together with (37), implies that (iii) holds.
In particular, for
$k=3$
, an immediate consequence of Theorem 2 is that if
$np\rightarrow c$
for some constant
$c > 0$
, we have
\begin{equation*} \frac{1}{\sqrt{n}}\big( Z^{(1)}_n-c n,Z^{(2)}_n-(c^2+c) n,\ldots, Z^{(3)}_n-(c^3+3c^2+c) n \big)^{\top}\buildrel {D} \over \longrightarrow N(\boldsymbol{0},\boldsymbol{\Sigma}_3),\end{equation*}
where the covariance matrix
\begin{equation*} \boldsymbol{\Sigma}_3=2c \left(\begin{array}{c@{\quad}c@{\quad}c} 1 & 2c+1& 3c^2+6c+1\\ 2c+1 & 4c^2+5c+1 & 6c^3+18c^2+11c+1\\ 3c^2+6c+1& 6c^3+18c^2+11c+1& 9c^4+45c^3+63c^2+21c+1 \end{array}\right).\end{equation*}
The next theorem, which is, in fact, a generalization of Theorem 3 in [Reference Feng, Hu and Su15], establishes a necessary and sufficient condition for the asymptotic normality of the generalized Zagreb indices of G(n, p), as
$n\rightarrow \infty$
.
Theorem 3. For any given integer
$k\ge 1$
, let
$Z^{(k)}_n$
be the kth-order generalized Zagreb index of a random graph G(n, p). If
$n^2p(1-p)\rightarrow\infty$
, then
\begin{equation} \frac{Z^{(k)}_{n}-\sum_{m=1}^k\left\{ \begin{matrix}k\\m\end{matrix}\right\}\frac{n!}{(n-m-1)!}p^m} {\sqrt{n\sum\limits_{m=1}^k\sum\limits_{l=1}^k\left\{ \begin{matrix}k\\m\end{matrix}\right\}\left\{ \begin{matrix}k\\l\end{matrix}\right\} \Big(ml(np)^{m+l-1}(1-p) +\sum\limits_{s=1}^{\min\{m,l\}}\frac{m!\,l!(np)^{m+l-s}(1-p^s)}{s!(m-s)!(l-s)!}\Big)}} \buildrel {D} \over \longrightarrow N(0,1). \end{equation}
Conversely, if
$(Z^{(k)}_n - a_n)/b_n \buildrel {D} \over \longrightarrow N(0, 1)$
for some constants
$a_n$
and
$b_n$
, then
$n^2p(1-p)\rightarrow\infty$
.
Remark. It is straightforward to see that the condition that
$n^2p(1-p)\rightarrow\infty$
is equivalent to
$n^2p\to\infty$
and
$n^2(1-p)\to \infty$
, while the quantities
$n^2p/2$
and
$n^2(1-p)/2$
are the asymptotic expected numbers of edges in G(n, p) and its complement
$\overline{G}(n, p)$
, respectively. Then Theorem 3 states that, for any
$k\ge1$
, the kth-order generalized Zagreb index of G(n, p) has asymptotic normality if G(n, p) is not too close to either an empty graph or a complete graph. This also indicates that for the ultra-dense ER random graphs, there remains a small gap in Theorem 2 that needs to be filled. If the parameter p is such that
$n^2 (1-p)\to \infty$
but
$n^2 (1-p)^3\to c$
for some constant
$c\ge0$
, then the single generalized Zagreb index
$Z_n^{(m)}$
has asymptotic normality for any
$1\le m\le k$
, but it is unknown whether these random variables have joint asymptotic normality.
Proof of Theorem
3. Here we employ a technique similar to that is used in [Reference Feng, Hu and Su15], and begin by proving the necessity part. If
$n^2p(1-p)$
does not go to
$\infty$
, then there exists a sequence
$\{n_l, l = 1, 2,\ldots\}$
such that
$n_l^2p(1-p)\rightarrow c_1$
for some constant
$c_1\in [0, \infty)$
with
$p=p(n_l)\to 0$
or 1. Thus, we can conclude that
$n_l^2p\to c_1$
or
$n_l^2(1-p)\to c_1$
. By Proposition 3, the subsequence
$\{Z^{(k)}_{n_l} \}$
rules out asymptotic normality for any normalization, and thus necessity holds.
To prove the sufficiency part of Theorem 3, we first note that (38) is equivalent to
\begin{equation} \frac{Z^{(k)}_{n}-\mathbb{E}[Z^{(k)}_{n}]}{\sqrt{\mathrm{Var}[Z^{(k)}_{n}]}}\buildrel {D} \over \longrightarrow N(0,1), \end{equation}
by (17) and (18). Also using Lemma 1, we next show that (39) holds under a stronger condition
$n^2p(1-p)^3\rightarrow\infty$
. Similarly to the proof of Theorem 1, it follows from Proposition 1 that
\begin{align} Z^{(k)}_{n}=\sum_{\alpha\in {\mathcal B}_n}(s_{n\alpha}-1)!\left\{ \begin{matrix}k\\{s_{n\alpha}-1}\end{matrix}\right\}I_{n\alpha}\,:\!=\sum_{\alpha\in {\mathcal B}_n}Y_{n\alpha}, \end{align}
where random variables
$Y_{n\alpha}$
also have the same dependency graph
$L_n$
, and
$2\le s_{n\alpha}\le k+1$
for all
$\alpha\in {\mathcal B}_n$
. To verify the condition of Lemma 1 for
$Z^{(k)}_{n}$
in the form of (40), by (17) we can directly set
\begin{align} M_n''\,:\!=2\sum_{m=1}^k \left\{ \begin{matrix}k\\m\end{matrix}\right\}n^{m+1}p^m=O\bigg(n^2p\Big(1+\sum_{m=1}^{k-1} (np)^m\Big)\bigg). \end{align}
Suppose that two star graphs
$\alpha_1,\alpha_2\in {\mathcal B}_n$
are given. Let
$V_{12}$
be the vertex set of the induced subgraph
$S_{n\alpha_1}\cup S_{n\alpha_1}$
. Note that the cardinality of
$V_{12}$
is at most
$2(k+1)$
, since both the sizes of
$\alpha_1,\alpha_2$
are not greater than
$k+1$
. Consider the star graphs in
${\mathcal B}_n$
that share at least one edge with
$\alpha_1$
or
$\alpha_2$
and have exactly s vertices out of
$V_{12}$
, for
$s=0, 1,\ldots,k-1$
. Recalling the constant
$C_k$
defined for any
$\alpha\in {\mathcal B}_n$
in the proof of (i) of Theorem 1, here we can analogously define a constant
$C_k'$
for any
$\alpha_1,\alpha_2\in {\mathcal B}_n$
. Therefore, by (40) we have
\begin{align} \sum_{\alpha\in \overline{N}_{L_n}}\mathbb{E}\big[|Y_{n\alpha}|\big|Y_{n\alpha_1},Y_{n\alpha_2}\big] &\le \max_{1\le s\le k}\Big(s!\left\{ \begin{matrix}k\\m\end{matrix}\right\}\Big)\cdot \sum_{\alpha\in \overline{N}_{L_n}}\mathbb{E}\big[I_{n\alpha}\big|I_{n\alpha_1},I_{n\alpha_2}\big]\notag\\ &\le \max_{1\le s\le k}\Big(s!\left\{ \begin{matrix}k\\s\end{matrix}\right\}\Big)\cdot C_k'\sum_{s=0}^{k-1}\binom{n}{s}p^s\notag\\ &\,:\!=Q_n'', \end{align}
which is of order
$1+\sum_{s=1}^{k-1} (np)^s$
. By (18), (41), and (42), we thus have
\begin{align*} \frac{M_n'' (Q_n'')^2}{(\mathrm{Var} [Z^{(k)}_n])^{3/2}}&=O\bigg(\frac{n^2p(1+\sum_{s=1}^{k-1} (np)^s)^3}{\big[n^2 p(1-p)(1+\sum_{s=1}^{2(k-1)} (np)^s)\big]^{3/2}}\bigg)\\ &=O\Big(\frac{1}{\sqrt{n^2p(1-p)^3}}\Big)\rightarrow 0. \end{align*}
which implies that (39) holds, if
$n^2p(1-p)^3\rightarrow\infty$
.
Finally, we prove that (39) also holds under the desired condition
$n^2p(1 - p)\rightarrow\infty$
. It is sufficient to consider the case where
$n^2p(1-p)^3\rightarrow\infty$
does not hold. Consider any subsequence of positive integers
$n_1 < n_2 < \cdots$
such that
$n^2_l p(1-p)^3\to c_1$
for some constant
$c_1\in[0,\infty)$
, as
$n_l\to\infty$
. Since
$n_l^2 p(1-p)$
still tends to infinity, it follows that
\begin{equation*} \frac{n_l^2 p(1-p)^3}{n_l^2 p(1-p)}=(1-p)^2\rightarrow 0, \end{equation*}
which implies that we must have
$p\rightarrow 1$
, and thus both
$n_l p$
and
$n_l^2 (1-p)$
tend to infinity. Then we just need to prove that (39) holds under the condition that
\begin{equation} np\to\infty,\quad n^2 (1-p)\to\infty, \end{equation}
for simplicity omitting the subscripts l. Under the condition (43), it follows by (35) that
\begin{align} \mathrm{Var}[S_{m+1,n}]=o\big(\mathrm{Var}[S_{k+1,n}]\big), \quad m=1,2,\ldots,k-1, \end{align}
and further, by Proposition 1,
\begin{align} \mathrm{Var}[Z^{(k)}_n]\sim (k!)^2\mathrm{Var}[S_{k+1,n}]. \end{align}
Note that if
$np\to\infty$
, then
$np^{m/(m+1)}\to \infty$
for any
$m\ge1$
. Applying Theorem 6.5 in [Reference Janson, Łuczak and Ruciński24], it follows that for any given integer number
$m\ge1$
,
\begin{align*} \frac{S_{m+1,n}-\mathbb{E}[S_{m+1,n}]}{\sqrt{\mathrm{Var}[S_{m+1,n}]}}\buildrel {D} \over \longrightarrow N(0,1). \end{align*}
Therefore, we have that, for any
$k\ge1$
,
\begin{align} \frac{Z^{(k)}_n-\mathbb{E}[Z^{(k)}_n]}{\sqrt{\mathrm{Var}[Z^{(k)}_n]}} &=\frac{\sum_{m=1}^{k} m!\left\{ \begin{matrix}k\\m\end{matrix}\right\} (S_{m+1,n}-\mathbb{E}[S_{m+1,n}])}{\sqrt{\mathrm{Var}[Z^{(k)}_n]}}\notag\\ &=\frac{\sum_{m=1}^{k-1} m!\left\{ \begin{matrix}k\\m\end{matrix}\right\} (S_{m+1,n}-\mathbb{E}[S_{m+1,n}])}{\sqrt{\mathrm{Var}\big[\sum_{m=1}^{k-1} m!\left\{ \begin{matrix}k\\m\end{matrix}\right\} S_{m+1,n}\big]}}\cdot \frac{\sqrt{\mathrm{Var}\big[\sum_{m=1}^{k-1} m!\left\{ \begin{matrix}k\\m\end{matrix}\right\} S_{m+1,n}\big]}}{\sqrt{\mathrm{Var}[Z^{(k)}_n]}}\notag\\ &\quad +\frac{k!(S_{k+1,n}-\mathbb{E}[S_{k+1,n}])}{k!\sqrt{\mathrm{Var}[S_{k+1,n}]}}\cdot \frac{k!\sqrt{\mathrm{Var}[S_{k+1,n}]}}{\sqrt{\mathrm{Var}[Z^{(k)}_n]}}\notag\\ &\buildrel {D} \over \longrightarrow N(0,1), \end{align}
by (44), (45), and Slutsky’s theorem. This completes the proof of Theorem 3.
Acknowledgements
We wish to thank two anonymous referees for their constructive comments that helped improve the quality of the paper.
Funding information
There are no funding bodies to thank relating to the creation of this paper.
Competing interests
There were no competing interests to declare which arose during the preparation or publication process of this article.
