Some New Properties for Degree-Based Graph Entropies

Abstract

The graph entropies inspired by Shannon’s entropy concept become the information-theoretic quantities for measuring the structural information of graphs and complex networks. In this paper, we continue studying some new properties of the graph entropies based on information functionals involving vertex degrees. We prove the monotonicity of the graph entropies with respect to the power exponent. Considering only the maximum and minimum degrees of the $(n,m)$-graph, we obtain some upper and lower bounds for the degree-based graph entropy. These bounds have different performances to restrict the degree-based graph entropy in different kinds of graphs. Moreover the degree-based graph entropy can be estimated by these bounds.

1. Introduction

The entropy of a probability distribution is known as a measure of the unpredictability of information content or a measure of the uncertainty of a system. This concept was introduced first from Shannon’s famous paper [1]. Later, entropy was initiated to be applied to graphs. It was developed for measuring the structural information of graphs and networks [2]. In that paper, Rashevsky proposed the concept of graph entropy based on the classifications of vertex orbits. Recently, graph entropies have been widely applied in many different fields, such as chemistry, biology, ecology and sociology [3,4,5,6,7].

There are several different types of such graph entropy measures [8]. For example, the graph entropy measures that associate probability distributions with elements (vertices, edges, etc.) of a graph can be classified as intrinsic and extrinsic measures. For intrinsic graph entropy measures, the probability distribution is induced by some structural feature of the graph. For extrinsic graph entropy measures, the probability distribution is assigned arbitrarily to elements of the graph. Most of the classical graph entropies are intrinsic. Dehmer introduced graph entropies based on information functionals, which capture structural information, and studied their properties [9,10,11]. The degree powers are extremely significant invariants and studied extensively in graph theory and network science, and they are used as the information functionals to explore the networks [12,13]. For more expansive research, Estrada and co-authors proposed a physically-sound entropy measure for networks/graphs [14] and studied the walk-based graph entropies [15,16,17]. There is am especially close relationship between the graph entropies based on length-two cycles and the graph entropies based on the degree powers for exponent $k=1$. We focus on the degree powers and the graph entropies based on the degrees. Therefore, we continue studying them under certain conditions.

The structure of this paper is as follows: In Section 2, some definitions and notations of graph theory and the graph entropies we are going to study are reviewed. In Section 3, the monotonicity of the graph entropies with respect to the power exponent is discussed. In Section 4, we give four upper bounds and three lower bounds of the graph entropies based on the degrees under certain conditions. In Section 5, numerical results are presented to demonstrate graph entropies. Finally, a short summary and conclusion are drawn in the last section.

2. Preliminaries to Degree-Based Graph Entropies

A graph $G=(V,E)$ is an ordered pair of sets V and E, where the set V of elements named vertices or nodes is a nonempty finite set, and the set E is composed of two-element subsets $uv$ of V named edges. If $e=uv$ is an edge, then u and v are called adjacent to each other, and v is a neighbor of u. The order of G is defined as the number of vertices in the graph G. Additionally, the size of G is defined as the number of edges in the graph G. An $(n,m)$-graph is defined as a graph of order n and size m. If any two vertices are connected by at most one edge in a graph, then the graph is called a simple graph. A path is a finite sequence of edges that connect a sequence of vertices, such that all edges and vertices are distinct from one another. A cycle is a finite sequence of edges that connect a sequence of vertices starting and ending at the same vertex. A graph is connected if there exists at least one path between every pair of vertices. Correspondingly, a graph is disconnected if it is not connected. A tree is a connected graph without any cycle. It is easy to see that a tree is an $(n,n-1)$-graph. A bipartite graph is a graph G whose vertices can be divided into two disjoint sets, such that every edge connects a vertex in one set to a vertex in another set. The two disjoint sets are called partite sets. Additionally, a bipartite graph can be denoted by $n_1\times n_2$ if the orders of the partite sets are $n_1$ and $n_2$, respectively.

The set of neighbors of a vertex u is called its neighborhood $N\left(u\right)$. The number of edges adjacent to the vertex u is the degree of u, which is denoted by $d\left(u\right)$ or in short $d_u$. If each vertex has the same degree in G, then G is a regular graph or is d-regular with vertices of degree d. The maximum and minimum degrees are often denoted by $\Delta \left(G\right)$ and $\delta \left(G\right)$. If $V=\{v_1,v_2,\cdots ,v_n\}$, then $D\left(G\right)=\{d_1,d_2,\cdots ,d_n\}$ is a degree sequence of G. Without loss of generality, we order the vertices, such that the degree sequence is monotone decreasing, for example $\Delta \left(G\right)=d_1\ge d_2\ge \cdots \ge d_n=\delta \left(G\right)$. To a given graph G, the vertex degree is an important graph invariant, which is related to the structural properties of the graph. In the following, we discuss a $(n,m)$-graph with given n and m. The sum of degree powers is defined by:

$$D\left(k\right):=\sum _{i=1}^n{d_i}^k$$

(1)

where k is an arbitrary real number. Obviously, when $k=1$, $D\left(1\right)={\sum }_{i=1}^n{d}_i=2m$ presents the sum of degrees. Observing $D\left(1\right)=Tr\left(L\right)$ where $L=D-A$ is the graph Laplacian associated with G and $Tr\left(L\right)$ is equal to the sum of the eigenvalues of L, as well, we can see that there exists a connection between the degree-based graph entropies and spectral-based graph entropies. The sum of degree powers as an invariant is called the zeroth order general Randić index [18,19,20]. Chen et al. [21] have reviewed it for different values of k and the relationships with some indices, such as the Zagreb index, graph energies, the HOMO-LUMO index and the Estrada index [22,23,24,25,26,27,28,29,30,31,32].

Next, we introduce the definition of Shannon’s entropy in information theory [33]. The logarithms in this paper are base two logarithms.

Definition 1. Let $P=(p_1,p_2,\cdots ,p_n)$ be a probability distribution of discrete random variable X, such that $0\le p_i\le 1$ and $\sum _{i=1}^n{p}_i=1$. Shannon’s entropy of the probability distribution P (of discrete random variable X) is defined by:

$$H\left(P\right)=-\sum _{i=1}^n{p}_{i}log{p}_i$$

(2)

Definition 2. Let $G=(V,E)$ be a connected graph. For any $v_i\in V$, we define:

$$p\left(v_i\right)=\frac{f\left(v_i\right)}{{\sum }_{j=1}^{n}f\left(v_j\right)}$$

(3)

where f is a meaningful information functional. According to the information functional f, the vertices are mapped to the non-negative real numbers.

Owing to ${\sum }_{i=1}^{n}p\left(v_i\right)=1$, the quantities $p\left(v_i\right)$ can be seen as probability values. Then, the graph entropy of G has been defined as follows [9].

Definition 3. Let $G=(V,E)$ be a connected graph and f be a meaningful information functional. The (Shannon’s) graph entropy of G is defined by:

$$I_f\left(G\right)=-\sum _{i=1}^n\frac{f\left(v_i\right)}{{\sum }_{j=1}^{n}f\left(v_j\right)}log\frac{f\left(v_i\right)}{{\sum }_{j=1}^{n}f\left(v_j\right)}$$

(4)

In [10], Dehmer and co-authors presented the parametric information functionals by using the diameter of graph G and the j-sphere of the vertices. In [11], they set other information functionals by using the spectrum of graph G. Because the degrees of the graph G can be seen as one species of the most noticeable invariants and they can be calculated very easily in large-scale networks, we focus on the information functionals by using the degree powers and the graph entropies based on the degrees. In [12,13], the graph entropy of G based on the degree powers’ information functional is defined by:

$$I_f(G,k)=-\sum _{i=1}^n\frac{{d_i}^k}{{\sum }_{j=1}^n{d_j}^k}log\frac{{d_i}^k}{{\sum }_{j=1}^n{d_j}^k}$$

(5)

For simplicity, we write the entropy of graph $I_f(G,1)$ as $I_f^1\left(G\right)$.

3. Monotonicity of $I_f(G,k)$ with Respect to the Parameter k

In [13], the authors have proven the theorem:

Theorem 1. If G is a connected graph with vertices of degree d (d-regular graph), then $I_f(G,k)=logn$ for any k.

In this section, we obtain the monotonicity of $I_f(G,k)$ with respect to the parameter k when G is an ordinary graph.

Theorem 2. If G is a connected graph where each vertex does not have the same degree (not a d-regular graph), then for $k>0$, $I_f(G,k)$ is monotonically decreasing with respect to k; for $k<0$, $I_f(G,k)$ is monotonically increasing with respect to k.

Proof. We have ordered the vertices such that the degree sequence obtained is monotone decreasing $\Delta \left(G\right)=d_1\ge d_2\ge \cdots \ge d_n=\delta \left(G\right)$ and $d_u>d_v$ for some $u,v$. The derivative of the function $I_f(G,k)$ with respect to k is:

$$\begin{array}{cc}\hfill \frac{\mathrm{d}}{\mathrm{d}k}\left(I_f(G,k)\right)=& -\frac{\mathrm{d}}{\mathrm{d}k}\left(\sum _{i=1}^n\frac{{d_i}^k}{{\sum }_{j=1}^n{d_j}^k}log\frac{{d_i}^k}{{\sum }_{j=1}^n{d_j}^k}\right)\hfill \\ \hfill =& -\frac{1}{ln2}·\frac{\mathrm{d}}{\mathrm{d}k}\left(\sum _{i=1}^n\frac{{d_i}^k}{{\sum }_{j=1}^n{d_j}^k}ln\frac{{d_i}^k}{{\sum }_{j=1}^n{d_j}^k}\right)\hfill \\ \hfill =& -\frac{1}{ln2}·\sum _{i=1}^n\left[\frac{{d_i}^{k}ln{d}_{i}ln\left(\frac{{d_i}^k}{D\left(k\right)}\right)}{{\sum }_{j=1}^n{d_j}^k}-\frac{{d_i}^{k}ln\left(\frac{{d_i}^k}{D\left(k\right)}\right)\left({\sum }_{j=1}^n{d_j}^{k}ln{d}_j\right)}{{\left({\sum }_{j=1}^n{d_j}^k\right)}^2}\right]\hfill \\ \hfill =& -\frac{1}{ln2{\left(D\left(k\right)\right)}^2}·\left[\left(\sum _{i=1}^n{d_i}^{k}ln{d}_{i}ln\left(\frac{{d_i}^k}{D\left(k\right)}\right)\right)\left(\sum _{j=1}^n{d_j}^k\right)\right.\hfill \\ & \left.-\left(\sum _{i=1}^n{d_i}^{k}ln\left(\frac{{d_i}^k}{D\left(k\right)}\right)\right)\left(\sum _{j=1}^n{d_j}^{k}ln{d}_j\right)\right]\hfill \\ \hfill =& -\frac{1}{ln2{\left(D\left(k\right)\right)}^2}·\sum _{i=1}^n\sum _{j=1}^n\left[{d_i}^k{d_j}^{k}ln{d}_{i}ln\left(\frac{{d_i}^k}{D\left(k\right)}\right)-{d_i}^k{d_j}^{k}ln{d}_{j}ln\left(\frac{{d_i}^k}{D\left(k\right)}\right)\right]\hfill \\ \hfill =& -\frac{1}{ln2{\left(D\left(k\right)\right)}^2}·\sum _{1\le i<j\le n}{d_i}^k{d_j}^k\left(ln{d}_i-ln{d}_j\right)\left[ln\left(\frac{{d_i}^k}{D\left(k\right)}\right)-ln\left(\frac{{d_j}^k}{D\left(k\right)}\right)\right]\hfill \end{array}$$

Obviously $D\left(k\right)>0$. When $i<j$, we have $ln{d}_i\ge ln{d}_j$. Additionally, if $k>0$, then ${d_i}^k\ge {d_j}^k$; if $k<0$, then ${d_i}^k\le {d_j}^k$. Moreover, for some $u,v$,

$${d_u}^k{d_v}^k\left(ln{d}_u-ln{d}_v\right)\left[ln\left(\frac{{d_u}^k}{D\left(k\right)}\right)-ln\left(\frac{{d_v}^k}{D\left(k\right)}\right)\right]\ne 0$$

These results show that if $k>0$, $\frac{\mathrm{d}}{\mathrm{d}k}\left(I_f(G,k)\right)<0$; if $k<0$, $\frac{\mathrm{d}}{\mathrm{d}k}\left(I_f(G,k)\right)>0$. Thus, we complete the proof.                           ☐

4. Some New Bounds for $I_f^1\left(G\right)$

In this section, we prove some new bounds for the degree-based graph entropy $I_f^1\left(G\right)$ in $(n,m)$-graph $G(n,m)$.

Lemma 1. Let $G(n,m)$ be an $(n,m)$-graph. The symbols Δ and δ denote the maximum degree and the minimum degree of $G(n,m)$, respectively. Then, the inequalities hold:

$$log\left(D\left(k\right)\right)-klog\Delta \le I_f(G,k)\le log\left(D\left(k\right)\right)-klog\delta$$

The above Lemma 1 is Theorem 1 in [13]. Especially, $D\left(1\right)=2m$ in $(n,m)$-graph $G(n,m)$. Therefore, we have the following.

Theorem 3. Let $G(n,m)$ be an $(n,m)$-graph. The symbols Δ and δ denote the maximum degree and the minimum degree of $G(n,m)$, respectively. Then, the inequalities hold:

$$log\left(2m\right)-log\Delta \le I_f^1\left(G\right)\le log\left(2m\right)-log\delta$$

(6)

Theorem 4. Let $G(n,m)$ be an $(n,m)$-graph. The symbols Δ and δ denote the maximum degree and the minimum degree of $G(n,m)$, respectively. If $n>2$, then the inequality holds:

$$I_f^1\left(G\right)\le \frac{2m-\delta -\Delta }{2m}log\frac{2m(n-2)}{2m-\delta -\Delta }-\frac{\delta }{2m}log\frac{\delta }{2m}-\frac{\Delta }{2m}log\frac{\Delta }{2m}$$

(7)

Proof. For $\Delta =d_1\ge d_2\ge \cdots \ge d_n=\delta$ and ${\sum }_{i=1}^n{d}_i=2m$, we have:

$$\begin{array}{cc}\hfill I_f^1\left(G\right)& =-\sum _{i=1}^n\frac{d_i}{{\sum }_{j=1}^n{d}_j}log\frac{d_i}{{\sum }_{j=1}^n{d}_j}=-\sum _{i=1}^n\frac{d_i}{2m}log\frac{d_i}{2m}\hfill \\ & =-\left(\sum _{i=2}^{n-1}\frac{d_i}{2m}log\frac{d_i}{2m}\right)-\frac{\delta }{2m}log\frac{\delta }{2m}-\frac{\Delta }{2m}log\frac{\Delta }{2m}\hfill \end{array}$$

Observe that ${\sum }_{i=2}^{n-1}{d}_i=2m-\delta -\Delta$. Hence, we construct vector $q=(q_1,q_2,\cdots ,q_{n-2})$ where $q_j=d_{j+1}/\left(2m-\delta -\Delta \right),j=1,2,\cdots ,n-2$. Then, $0\le q_j\le 1$ and ${\sum }_{j=1}^{n-2}{q}_j={\sum }_{i=2}^{n-1}{d}_i/\left(2m-\delta -\Delta \right)=1$. The vector q is a probability vector, and Shannon’s entropy of q is:

$$\begin{array}{cc}\hfill H\left(q\right)=& -\sum _{j=1}^{n-2}{q}_{j}log{q}_j=-\sum _{i=2}^{n-1}\frac{d_i}{2m-\delta -\Delta }log\frac{d_i}{2m-\delta -\Delta }\hfill \\ \hfill =& -\sum _{i=2}^{n-1}\frac{d_i}{2m-\delta -\Delta }\left(log\frac{d_i}{2m}+log\frac{2m}{2m-\delta -\Delta }\right)\hfill \\ \hfill =& -\sum _{i=2}^{n-1}\frac{2m}{2m-\delta -\Delta }·\frac{d_i}{2m}log\frac{d_i}{2m}\hfill \\ & -\sum _{i=2}^{n-1}\frac{d_i}{2m-\delta -\Delta }log\frac{2m}{2m-\delta -\Delta }\hfill \\ \hfill =& -\frac{2m}{2m-\delta -\Delta }\left(\sum _{i=2}^{n-1}\frac{d_i}{2m}log\frac{d_i}{2m}\right)-log\frac{2m}{2m-\delta -\Delta }\hfill \end{array}$$

In information theory, it is easy to obtain that $H\left(q\right)\le log(n-2)$ with equality if and only if $q_1=q_2=\cdots =q_{n-2}$ (see [33] Theorem 2.6.4). Then, we have:

$$\begin{array}{cc}\hfill -\sum _{i=2}^{n-1}\frac{d_i}{2m}log\frac{d_i}{2m}& =\frac{2m-\delta -\Delta }{2m}\left[H\left(q\right)+log\frac{2m}{2m-\delta -\Delta }\right]\hfill \\ & \le \frac{2m-\delta -\Delta }{2m}\left[log(n-2)+log\frac{2m}{2m-\delta -\Delta }\right]\hfill \\ & =\frac{2m-\delta -\Delta }{2m}log\frac{2m(n-2)}{2m-\delta -\Delta }\hfill \end{array}$$

(8)

Take (8) into $I_f^1\left(G\right)$:

$$\begin{array}{cc}\hfill I_f^1\left(G\right)& =-\left(\sum _{i=2}^{n-1}\frac{d_i}{2m}log\frac{d_i}{2m}\right)-\frac{\delta }{2m}log\frac{\delta }{2m}-\frac{\Delta }{2m}log\frac{\Delta }{2m}\hfill \\ & \le \frac{2m-\delta -\Delta }{2m}log\frac{2m(n-2)}{2m-\delta -\Delta }-\frac{\delta }{2m}log\frac{\delta }{2m}-\frac{\Delta }{2m}log\frac{\Delta }{2m}\hfill \end{array}$$

Additionally, the equality holds if and only if $d_2=d_3=\cdots =d_{n-1}$. Thus, we complete the proof. ☐

Lemma 2. Define $\mu :=\underset{1\le i\le n}{min}\left\{p_i\right\}$; $\nu :=\underset{1\le i\le n}{max}\left\{p_i\right\}$. Then:

$$\frac{1}{2ln2·n\nu }\sum _{1\le i<j\le n}{(p_i-p_j)}^2\le logn-H\left(p\right)\le \frac{1}{2ln2·n\mu }\sum _{1\le i<j\le n}{(p_i-p_j)}^2$$

(9)

The above Lemma 2 can be seen in [34], Theorem 5. Merely the change of base should be applied to the formula because the logarithms in [34] are base $\mathrm{e}$ logarithms.

Theorem 5. Let $G(n,m)$ be an $(n,m)$-graph. The symbols Δ and δ denote the maximum degree and the minimum degree of $G(n,m)$, respectively. Then, the inequalities hold:

$$\begin{array}{cc}& max\left\{logn-\frac{(2m-n\delta )(n\Delta -2m)}{4ln2·\delta mn},0\right\}\le I_f^1\left(G\right)\hfill \\ \hfill \le & logn-\frac{n(n-2)({\delta }^2+{\Delta }^2)+n{(2m-\delta -\Delta )}^2-4m^2(n-2)}{4ln2·\Delta mn(n-2)}\hfill \end{array}$$

(10)

Proof. Let $p_i=\frac{d_i}{2m}$, then $\mu =\frac{\delta }{2m}$, $\nu =\frac{\Delta }{2m}$ and ${\sum }_{i=1}^n{d}_i=2m$. Firstly,

$$\begin{array}{cc}\hfill \sum _{1\le i<j\le n}{(p_i-p_j)}^2& =\sum _{1\le i<j\le n}{\left(\frac{d_i}{2m}-\frac{d_j}{2m}\right)}^2=\frac{1}{4m^2}\left[n\sum _{i=1}^n{d}_i^2-{\left(\sum _{i=1}^n{d}_i\right)}^2\right]\hfill \\ & =\frac{1}{4m^2}\left(n\sum _{i=1}^n{d}_i^2-4m^2\right)\hfill \end{array}$$

(11)

holds. We observe that:

$$\begin{array}{cc}\hfill 0& \le \sum _{i=1}^n(d_i-\delta )(\Delta -d_i)=(\delta +\Delta )\sum _{i=1}^n{d}_i-n\delta \Delta -\sum _{i=1}^n{d}_i^2\hfill \\ & =2m(\delta +\Delta )-n\delta \Delta -\sum _{i=1}^n{d}_i^2\hfill \end{array}$$

This leads to:

$$\begin{array}{cc}\hfill n\sum _{i=1}^n{d}_i^2-4m^2& \le n\left[2m(\delta +\Delta )-n\delta \Delta \right]-4m^2\hfill \\ & =(2m-n\delta )(n\Delta -2m).\hfill \end{array}$$

(12)

Taking (11) and (12) into Lemma 2, we deduce the inequality:

$$\begin{array}{c}\hfill logn-I_f^1\left(G\right)\le \frac{(2m-n\delta )(n\Delta -2m)}{4ln2·\delta mn}\end{array}$$

(13)

On the other hand,

$$\begin{array}{cc}\hfill \sum _{i=1}^n{d}_i^2& ={\delta }^2+{\Delta }^2+\sum _{i=2}^{n-1}{d}_i^2\hfill \\ & \ge {\delta }^2+{\Delta }^2+\frac{1}{n-2}{\left(\sum _{i=2}^{n-1}{d}_i\right)}^2\hfill \\ & ={\delta }^2+{\Delta }^2+\frac{{(2m-\delta -\Delta )}^2}{n-2}\hfill \end{array}$$

(14)

The inequality is obtained by using Chebyshev’s sum inequality. This leads to:

$$\begin{array}{cc}\hfill n\sum _{i=1}^n{d}_i^2-4m^2& \ge n\left[{\delta }^2+{\Delta }^2+\frac{{(2m-\delta -\Delta )}^2}{n-2}\right]-4m^2\hfill \\ & =\frac{n(n-2)({\delta }^2+{\Delta }^2)+n{(2m-\delta -\Delta )}^2-4m^2(n-2)}{n-2}\hfill \end{array}$$

(15)

Taking (11) and (15) into Lemma 2, we deduce the inequality:

$$\begin{array}{c}\hfill logn-I_f^1\left(G\right)\ge logn-\frac{n(n-2)({\delta }^2+{\Delta }^2)+n{(2m-\delta -\Delta )}^2-4m^2(n-2)}{4ln2·\Delta mn(n-2)}\end{array}$$

(16)

Using (13) and (16), the validity of the inequalities (10) can be obtained.    ☐

Lemma 3. Define $\mu :=\underset{1\le i\le n}{min}\left\{p_i\right\}$; $\nu :=\underset{1\le i\le n}{max}\left\{p_i\right\}$. Then:

$$\psi (\mu ,\nu )\le logn-H\left(p\right)\le min\{\Psi (\mu ,\nu ),n·\psi (\mu ,\nu \left)\right\}$$

(17)

where $\psi (\mu ,\nu ):=\mu log\left(\frac{2\mu }{\mu +\nu }\right)+\nu log\left(\frac{2\nu }{\mu +\nu }\right)$, $\Psi (\mu ,\nu ):=log\left(\frac{{(\mu +\nu )}^2}{4\mu \nu }\right)$.

The above Lemma 3 is proven in [35], Proposition 3.

Theorem 6. Let $G(n,m)$ be an $(n,m)$-graph. The symbols Δ and δ denote the maximum degree and the minimum degree of $G(n,m)$, respectively. Then, the inequalities hold:

$$logn-min\{\Psi (\delta ,\Delta ),n·\psi (\delta ,\Delta )\}\le I_f^1\left(G\right)\le logn-\psi (\delta ,\Delta )$$

(18)

where $\psi (\delta ,\Delta ):=\frac{1}{2m}\left[\delta log\left(\frac{2\delta }{\delta +\Delta }\right)+\Delta log\left(\frac{2\Delta }{\delta +\Delta }\right)\right]$, $\Psi (\delta ,\Delta ):=log\left(\frac{{(\delta +\Delta )}^2}{4\delta \Delta }\right)$.

Proof. Let $\mu =\delta /\left(2m\right)$ and $\nu =\Delta /\left(2m\right)$ in (17). Then, inequality (18) is obtained. ☐

Overall, we obtain four upper bounds:

$$\begin{array}{cc}\hfill U_0& :=log\left(2m\right)-log\delta \hfill \\ \hfill U_1& :=\frac{2m-\delta -\Delta }{2m}log\frac{2m(n-2)}{2m-\delta -\Delta }-\frac{\delta }{2m}log\frac{\delta }{2m}-\frac{\Delta }{2m}log\frac{\Delta }{2m}\hfill \\ \hfill U_2& :=logn-\frac{n(n-2)({\delta }^2+{\Delta }^2)+n{(2m-\delta -\Delta )}^2-4m^2(n-2)}{4ln2·\Delta mn(n-2)}\hfill \\ \hfill U_3& :=logn-\psi (\delta ,\Delta )\hfill \end{array}$$

and three new lower bounds:

$$\begin{array}{cc}\hfill L_0& :=log\left(2m\right)-log\Delta \hfill \\ \hfill L_1& :=max\left\{logn-\frac{(2m-n\delta )(n\Delta -2m)}{4ln2·\delta mn},0\right\}\hfill \\ \hfill L_2& :=logn-min\{\Psi (\delta ,\Delta ),n·\psi (\delta ,\Delta \left)\right\}\hfill \end{array}$$

5. Numerical Results

In this section, we compute the values of the degree-based graph entropy $I_f^1\left(G\right)$ and the bounds obtained above for some special $(n,m)$-graphs.

5.1. Path Graph

Let $P_n$ be a path graph with exactly two pendant vertices and $n-2$ internal vertices. Therefore, in $P_n$ two pendant vertices have degree one, while all others (if any) have degree two. Additionally, $m=n-1$, $\Delta =2$, $\delta =1$.

By calculating the graph entropy of a series of path graphs, we show some values of the degree-based graph entropy and bounds in the following Table 1.

Table 1. The values of the degree-based graph entropy and bounds for $P_n$.

n	4	5	6	7	10	20	30	40	50	100
$I_f^1\left(P_n\right)$	1.918	2.250	2.522	2.752	3.281	4.301	4.892	5.311	5.635	6.639
$U_0$	2.585	3.000	3.322	3.585	4.170	5.248	5.858	6.285	6.615	7.629
$L_0$	1.585	2.000	2.322	2.585	4.170	4.248	4.858	5.285	5.615	6.629
$U_1$	1.959	2.289	2.557	2.782	3.303	4.312	4.900	5.317	5.640	6.642
$L_1$	1.880	2.214	2.489	2.721	3.258	4.288	4.884	5.304	5.630	6.637
$U_2$	1.970	2.298	2.564	2.788	3.307	4.314	4.901	5.318	5.640	6.642
$L_2$	1.837	2.169	2.438	2.664	3.186	4.193	4.780	5.196	5.519	6.520
$U_3$	1.959	2.291	2.560	2.787	3.308	4.315	4.903	5.319	5.641	6.643

Table 1. The values of the degree-based graph entropy and bounds for $P_n$.

n	4	5	6	7	10	20	30	40	50	100
$I_f^1\left(P_n\right)$	1.918	2.250	2.522	2.752	3.281	4.301	4.892	5.311	5.635	6.639
$U_0$	2.585	3.000	3.322	3.585	4.170	5.248	5.858	6.285	6.615	7.629
$L_0$	1.585	2.000	2.322	2.585	4.170	4.248	4.858	5.285	5.615	6.629
$U_1$	1.959	2.289	2.557	2.782	3.303	4.312	4.900	5.317	5.640	6.642
$L_1$	1.880	2.214	2.489	2.721	3.258	4.288	4.884	5.304	5.630	6.637
$U_2$	1.970	2.298	2.564	2.788	3.307	4.314	4.901	5.318	5.640	6.642
$L_2$	1.837	2.169	2.438	2.664	3.186	4.193	4.780	5.196	5.519	6.520
$U_3$	1.959	2.291	2.560	2.787	3.308	4.315	4.903	5.319	5.641	6.643

5.2. Star Graph

Let $S_n$ be a star graph with one internal vertex and $n-1$ pendant vertices. It also can be seen as a complete bipartite graph $K_{1,n-1}$. Therefore, in $S_n$, one internal vertex has degree $n-1$, while all others (if any) have degree 1. Additionally, $m=n-1$, $\Delta =n-1$, $\delta =1$.

By calculating the graph entropy of a series of star graphs, we show some values of the degree-based graph entropy and bounds in the following Table 2.

Table 2. The values of the degree-based graph entropy and bounds for $S_n$.

n	4	5	6	7	10	20	30	40	50	100
$I_f^1\left(S_n\right)$	1.792	2.000	2.161	2.292	2.585	3.124	3.429	3.643	3.807	4.315
$U_0$	2.585	3.000	3.322	3.585	4.170	5.248	5.858	6.285	6.615	7.629
$L_0$	1.000	1.000	1.000	1.000	1.000	1.000	1.000	1.000	1.000	1.000
$U_1$	1.792	2.000	2.161	2.292	2.585	3.124	3.429	3.643	3.807	4.315
$L_1$	1.639	1.673	1.623	1.519	1.104	0.000	0.000	0.000	0.000	0.000
$U_2$	1.880	2.160	2.393	2.593	3.065	4.014	4.582	4.988	5.305	6.294
$L_2$	1.585	1.678	1.737	1.778	1.848	1.926	1.951	1.963	1.971	1.986
$U_3$	1.880	2.160	2.393	2.593	3.065	4.014	4.582	4.988	5.305	6.294

Table 2. The values of the degree-based graph entropy and bounds for $S_n$.

n	4	5	6	7	10	20	30	40	50	100
$I_f^1\left(S_n\right)$	1.792	2.000	2.161	2.292	2.585	3.124	3.429	3.643	3.807	4.315
$U_0$	2.585	3.000	3.322	3.585	4.170	5.248	5.858	6.285	6.615	7.629
$L_0$	1.000	1.000	1.000	1.000	1.000	1.000	1.000	1.000	1.000	1.000
$U_1$	1.792	2.000	2.161	2.292	2.585	3.124	3.429	3.643	3.807	4.315
$L_1$	1.639	1.673	1.623	1.519	1.104	0.000	0.000	0.000	0.000	0.000
$U_2$	1.880	2.160	2.393	2.593	3.065	4.014	4.582	4.988	5.305	6.294
$L_2$	1.585	1.678	1.737	1.778	1.848	1.926	1.951	1.963	1.971	1.986
$U_3$	1.880	2.160	2.393	2.593	3.065	4.014	4.582	4.988	5.305	6.294

5.3. Monocentric Homogeneous Dendrimer Graph

Let the monocentric dendrimer be a special tree, which is controlled by two parameters t and r. The parameter t denotes the progressive level, and the parameter r denotes the radius of the tree. The degrees of all internal vertices are equal to $t+1$. As there exists one central vertex in a monocentric dendrimer, the maximum distance from one pendant vertex to the central vertex is referred to as the radius. If the distances from the central vertex to all pendant vertices are equal to r, then we call the tree a monocentric homogeneous dendrimer. For more details, please see [36,37]. Figure 1 is an example of a monocentric homogeneous dendrimer with three as the value of t and s, respectively.

Figure 1. A monocentric homogeneous dendrimer with $t=3$ and $r=3$.

Figure 1. A monocentric homogeneous dendrimer with $t=3$ and $r=3$.

For parameters t and r, we have the order $n=1+\frac{(t+1)(t^r-1)}{t-1}$, and $m=n-1$, $\Delta =t+1$, $\delta =1$. Let $t=3$; we change the value of parameter r to compute the degree-based graph entropy and bounds. The results are listed in Table 3.

Table 3. The values of the degree-based graph entropy and bounds for monocentric homogeneous dendrimer $D(3,r)$.

r	1	2	3	4	5	6	7	8	9	10
$I_f^1\left(D(3,r)\right)$	2.000	3.750	5.393	6.997	8.588	10.175	11.761	13.346	14.931	16.516
$U_0$	3.000	5.000	6.700	8.322	9.919	11.508	13.094	14.680	16.265	17.850
$L_0$	1.000	3.000	4.700	6.322	7.919	9.508	11.094	12.680	14.265	15.850
$U_1$	2.000	4.035	5.713	7.326	8.920	10.508	12.094	13.680	15.265	16.850
$L_1$	1.673	3.371	5.007	6.610	8.201	9.787	11.373	12.958	14.543	16.128
$U_2$	2.160	4.057	5.719	7.328	8.921	10.509	12.094	13.680	15.265	16.850
$L_2$	1.678	3.444	5.084	6.687	8.278	9.865	11.451	13.036	14.621	16.206
$U_3$	2.148	4.044	5.715	7.327	8.920	10.508	12.094	13.680	15.265	16.850

Table 3. The values of the degree-based graph entropy and bounds for monocentric homogeneous dendrimer $D(3,r)$.

r	1	2	3	4	5	6	7	8	9	10
$I_f^1\left(D(3,r)\right)$	2.000	3.750	5.393	6.997	8.588	10.175	11.761	13.346	14.931	16.516
$U_0$	3.000	5.000	6.700	8.322	9.919	11.508	13.094	14.680	16.265	17.850
$L_0$	1.000	3.000	4.700	6.322	7.919	9.508	11.094	12.680	14.265	15.850
$U_1$	2.000	4.035	5.713	7.326	8.920	10.508	12.094	13.680	15.265	16.850
$L_1$	1.673	3.371	5.007	6.610	8.201	9.787	11.373	12.958	14.543	16.128
$U_2$	2.160	4.057	5.719	7.328	8.921	10.509	12.094	13.680	15.265	16.850
$L_2$	1.678	3.444	5.084	6.687	8.278	9.865	11.451	13.036	14.621	16.206
$U_3$	2.148	4.044	5.715	7.327	8.920	10.508	12.094	13.680	15.265	16.850

5.4. Complete Bipartite Graph $K_{s,2s}$

Let $K_{n_1,n_2}$ be a complete bipartite graph. In other words, $K_{n_1,n_2}$ is an $n_1\times n_2$ bipartite graph, where every vertex of one partite set is connected to every vertex of the other partite set. For a special class of complete bipartite graphs $K_{s,2s}$, we have the order $n=3s$, and $m=2s^2$, $\Delta =2s$, $\delta =s$.

By calculating the graph entropy of the special class of complete bipartite graphs $K_{s,2s}$, we show some values of the degree-based graph entropy and bounds in the following Table 4.

Table 4. The values of the degree-based graph entropy and bounds for $K_{s,2s}$.

n	4	5	6	7	10	20	30	40	50	100
$I_f^1\left(K_{s,2s}\right)$	3.500	3.822	4.085	4.307	4.822	5.822	6.407	6.822	7.144	8.144
$U_0$	4.000	4.322	4.585	4.807	5.322	6.322	6.907	7.322	7.644	8.644
$L_0$	3.000	3.322	3.585	3.807	4.322	5.322	5.907	6.322	6.644	7.644
$U_1$	3.567	3.893	4.158	4.382	4.900	5.903	6.490	6.905	7.227	8.228
$L_1$	3.465	3.787	4.050	4.272	4.787	5.787	6.372	6.787	7.109	8.109
$U_2$	3.572	3.897	4.161	4.385	4.902	5.904	6.490	6.906	7.228	8.228
$L_2$	3.415	3.737	4.000	4.222	4.737	5.737	6.322	6.737	7.059	8.059
$U_3$	3.570	3.895	4.160	4.384	4.901	5.904	6.490	6.905	7.228	8.228

Table 4. The values of the degree-based graph entropy and bounds for $K_{s,2s}$.

n	4	5	6	7	10	20	30	40	50	100
$I_f^1\left(K_{s,2s}\right)$	3.500	3.822	4.085	4.307	4.822	5.822	6.407	6.822	7.144	8.144
$U_0$	4.000	4.322	4.585	4.807	5.322	6.322	6.907	7.322	7.644	8.644
$L_0$	3.000	3.322	3.585	3.807	4.322	5.322	5.907	6.322	6.644	7.644
$U_1$	3.567	3.893	4.158	4.382	4.900	5.903	6.490	6.905	7.227	8.228
$L_1$	3.465	3.787	4.050	4.272	4.787	5.787	6.372	6.787	7.109	8.109
$U_2$	3.572	3.897	4.161	4.385	4.902	5.904	6.490	6.906	7.228	8.228
$L_2$	3.415	3.737	4.000	4.222	4.737	5.737	6.322	6.737	7.059	8.059
$U_3$	3.570	3.895	4.160	4.384	4.901	5.904	6.490	6.905	7.228	8.228

Observe the four tables above, and we summarize the findings as follows:

• The value of degree-based entropy $I_f^1\left(G\right)$ corresponds to the scale of the graph. The larger the order and size are, the bigger the degree-based entropy is. This means that the corresponding graph is more complex in the structure information.
• To the graph $P_n$ and $S_n$ of the same order and size, $I_f^1\left(P_n\right)\ge I_f^1\left(S_n\right)$. This means that if $P_n$ and $S_n$ have the same scale, $P_n$ is more complex in the structure information.
• The upper bound $U_1$ is the closest to $I_f^1\left(G\right)$ or better than $U_0,U_2,U_3$, and the lower bound $L_2$ is the closest to $I_f^1\left(G\right)$ or better than $L_0,L_2$. The upper bound $U_0$ is the farthest from $I_f^1\left(G\right)$ or worse than $U_1,U_2,U_3$. The closeness of $I_f^1\left(G\right)$ and other upper bounds $U_1,U_2$ or lower bound $L_0,L_1$ is uncertain.
• In Table 2, when the size n is big enough and continues to increase, the value of $L_0$ is always one, and the value of $L_1$ approaches zero. This means that these lower bounds are not ideal. However, in other tables, all bounds correspond to the scale of the graph. Therefore, we infer that the bounds are closely related to the structure information of the graph. The more complex a graph of the same order and size is in the structure information, the better the bounds are.

6. Summary and Conclusions

In this paper, we studied the properties for degree-based graph entropies. We discussed the degree powers’ information functional and obtained the monotonicity of the graph entropy $I_f(G,k)$ with respect to the parameter k. Specifically, for the degree-based graph entropy $I_f^1\left(G\right)$, we introduced some new bounds, which can estimate $I_f^1\left(G\right)$ by only using the order n, the size m and the maximum and minimum degrees of a given graph G. The numerical results for special graphs show that the new bounds have different effects to restrict $I_f^1\left(G\right)$. The monotonicity and bounds might prove useful in further structure information investigation of graphs and real networks, such as estimating the complexity and analyzing the aggregation or homogeneity.