Methods used to parameterize the spatially-explicit components of a state-and-transition simulation model

1.   Preliminaries

By a graph $ G = (V(G), E(G)) $, with $ V(G) $ and $ E(G) $ the set of vertices and edges of $ G $ respectively, we mean an undirected simple graph without isolated vertices (i.e., each vertex has at least a neighbor).

Given a graph $ G $, representing a chemical structure,

is said a topological descriptor and, if also it correlates with a molecular property, it is called a topological index. Above, by $ uv $ we mean the edge of a graph $ G $ joining the vertices $ u $ and $ v $, $ d_u $ denotes the degree of $ u $, and $ F $ is an appropriate chosen function. Remarkably, topological indices capture physical properties of a chemical compound in a single number.

A great number of topological indices have been defined and studied over more than four decades. Among them, probably the most popular topological indices are the Randić and the Zagreb indices. The first and second Zagreb indices, denoted by $ M_1 $ and $ M_2 $, respectively, were defined by Gutman and Trinajstić (see ^[1]) in $ 1972 $ by

For more details of the applications and mathematical properties of Zagreb indices see ^[2,3,4], and the references therein. Zagreb indices have many connections with other topological indices, see e.g., ^[5,6].

The concept of variable molecular descriptors was proposed as a way of characterizing heteroatoms (see ^[7,8]), but also to assess structural differences in alkylcycloalkanes ^[9]. The idea behind the variable molecular descriptors is that the variables are determined during the regression in order to minimize the error of estimate for a particular chemical property (see, e.g., ^[10]).

In this line of ideas, the variable versions of the first and second Zagreb indices were introduced as ^[10,11,12]

with $ \alpha \in \mathbb{R} $. Evidently, $ M_1^{2} $ and $ M_2^{1} $ are the first and second Zagreb indices, respectively. In addition, the first and second variable Zagreb indices include several known indices. As examples we note that $ M_2^{-1/2} $ is the Randić index, $ M_1^{3} $ is the forgotten index $ F $, $ M_1^{-1} $ is the inverse index $ ID $, and $ M_2^{-1} $ is the modified Zagreb index.

In 2011, Vukičević proposed the variable symmetric division deg index ^[13]

Note that $ SDD_{-\alpha}(G) = SDD_\alpha(G) $ and so, it suffices to consider positive values of $ \alpha $. The symmetric division deg index is the best predictor of total surface area for polychlorobiphenyls ^[14].

In this work we perform studies of the variable symmetric division deg index from analytical and computational viewpoints. We obtain new inequalities for the variable symmetric division deg index $ SDD_\alpha(G) $ and we characterize graphs extremal with respect to them. Some of these inequalities generalize and improve previous results for the symmetric division deg index. In addition, we computationally apply the $ SDD_\alpha(G) $ index on random graphs and we demonstrate that the ratio $ \langle SDD_\alpha(G) \rangle/n $ ($ n $ denotes the order of the graph) depends only on the average degree $ \langle d \rangle $.

One of our main results is Theorem 8, which provides upper and lower bounds of $ SDD_\alpha(G) $ in terms of the number of edges, the maximum and the minimum degree of $ G $.

2.   Analytical study of the variable symmetric division deg index

Let us start by proving a monotonicity property of these indices.

Theorem 1. Let $ G $ be a graph and $ 0 < \alpha < \beta $.Then

and the equality in the bound is attained if and only if each connected component of $ G $ is a regular graph.

Proof. Let us consider $ x \ge 1 $. Thus, $ x^{ \alpha} \ge x^{- \beta} $ and

for every $ x \ge 1 $. Since $ u(x) = x^{ \alpha} + x^{- \alpha} $ satisfies $ u(1/x) = u(x) $ for every $ x > 0 $, we have $ x^{ \beta} + x^{- \beta} \ge x^{ \alpha} + x^{- \alpha} $ for every $ x > 0 $. Note that we obtain the equality if and only if $ x = 1 $.

Thus, we have

The previous argument gives that we have the equality in the bound if and only if $ d_u/d_v = 1 $ for every $ uv \in E(G) $, i.e., each connected component of $ G $ is a regular graph.

Our next results in this section provide bounds of $ SDD_\alpha(G) $ involving the maximum and minimum degree of the graph $ G $. Since scientists often estimate average degree of large networks, we present in the next section results involving the average degree.

Our next theorem relates the $ SDD_ \alpha $ and the variable Zagreb indices.

Theorem 2. If $ G $ is a graph with minimum degree $ \delta $ and maximum degree $ \Delta $, and $ \alpha > 0 $, then

and we have the equality in each bound if and only if $ G $ is regular.

Proof. First of all recall that for every function $ f $ the following equality

holds. In particular,

Since

and $ \alpha > 0 $, we obtain

and

We also have

and

If $ G $ is a regular graph, then each lower bound and its corresponding upper bound are the same, and both are equal to $ SDD_{ \alpha}(G) $.

Assume now that the equality in either the first or second bound holds. The previous argument gives that we have either $ d_u^{2 \alpha}+d_v^{2 \alpha} = 2 \Delta^{2 \alpha} $ for any $ uv \in E(G) $ or $ d_u^{2 \alpha}+d_v^{2 \alpha} = 2 \delta^{2 \alpha} $ for any $ uv \in E(G) $. Since $ \alpha > 0 $, we have $ \delta^{2 \alpha} \le d_u^{2 \alpha}, d_v^{2 \alpha} \le \Delta^{2 \alpha} $, and we conclude that $ d_u = d_v = \Delta $ for any $ uv\in E(G) $, or $ d_u = d_v = \delta $ for any $ uv\in E(G) $. Hence, $ G $ is a regular graph.

Finally, assume that the equality in either the third or fourth bound holds. The previous argument gives that we have either $ (d_u d_v)^{ \alpha} = \delta^{2 \alpha} $ for any $ uv \in E(G) $ or $ (d_u d_v)^{ \alpha} = \Delta^{2 \alpha} $ for any $ uv \in E(G) $. Since $ \alpha > 0 $, we have $ \delta^{ \alpha} \le d_u^{ \alpha}, d_v^{ \alpha} \le \Delta^{ \alpha} $, and we conclude that $ d_u = d_v = \delta $ for any $ uv\in E(G) $, or $ d_u = d_v = \Delta $ for every $ uv\in E(G) $. Therefore, $ G $ is a regular graph.

We will need the following technical result.

Lemma 3. Let $ 0 < a < A $. Then

for every $ a \le x, y \le A $.The lower bound is attained if and only if $ x = y = a $.The upper bound is attained if and only if $ x = y = A $.

Proof. If $ a \le x, y \le A $, then $ ax+ay\le x^{2}+y^{2} \le Ax+Ay $, and the statement holds.

A large kind of topological indices, named Adriatic indices, was introduced in ^[14,15]. Twenty of them were selected as significant predictors of chemical properties. One of them, the inverse sum indeg index, defined by

appears in ^[14,15] as a good predictor of total surface area of octane isomers.

Next, we relate $ SDD_{ \alpha}(G) $ with the variable inverse sum deg index defined, for each $ a \in \mathbb{R} $, as

Note that $ ISD_{-1} $ is the inverse sum indeg index $ ISI $.

Theorem 4. If $ G $ is a graph with $ m $ edges and minimum degree $ \delta $, and $ \alpha > 0 $, then

and the equality in the bound holds if and only if $ G $ is regular.

Proof. Lemma 3 gives

for every $ \delta \le x, y \le \Delta $. This last inequality and Cauchy-Schwarz inequality give

If $ G $ is a regular graph, then $ SDD_{ \alpha}(G) = 2m $, $ ISD_{- \alpha}(G) = m \delta^{ \alpha}/2 $ and the equality in the bound holds.

Assume now that the equality in the bound holds. Thus, by the previous argument,

for any $ uv \in E(G) $. Then Lemma 3 gives $ d_u = d_v = \delta $ for any $ uv\in E(G) $. Hence, $ G $ is a regular graph.

The modified Narumi-Katayama index is defined by

in ^[16], inspired in the Narumi-Katayama index ^[17]. Next, we present an inequality relating $ SDD_{ \alpha}(G) $ and $ NK^*(G) $.

Theorem 5. Let $ G $ be a graph with $ m $ edges and minimum degree $ \delta $, and $ \alpha > 0 $.Then

and the equality in the bound holds if and only if $ G $ is a regular graph.

Proof. Since the geometric mean is at most the arithmetic mean, we have

If $ G $ is a regular graph, then

Finally, assume that the equality in the bound holds. The previous argument gives that $ d_u^{2 \alpha}+d_v^{2 \alpha} = 2 \delta^{2 \alpha} $ for any $ uv \in E(G) $. Since $ \alpha > 0 $, we obtain $ \delta^{2 \alpha} \le d_u^{2 \alpha}, d_v^{2 \alpha} $, and we have $ d_u = d_v = \delta $ for any $ uv \in E(G) $. Hence, $ G $ is regular.

Next, we obtain additional bounds of $ SDD_{ \alpha} $.

Theorem 6. Let $ G $ be a graph with $ m $ edges, minimum degree $ \delta $ and maximum degree $ \delta+1 $, $ \alpha > 0 $ and let $ A $ be the number of edges $ uv \in E(G) $ with $ d_u \ne d_v $.Then $ A $ is an even integer and

Proof. Let $ F = \left\lbrace uv\in E(G):\; d_u \ne d_v \right\rbrace $, then $ A $ is the cardinality of the set $ F $. Since the maximum degree of $ G $ is $ \delta+1 $ and its minimum degree is $ \delta $, if $ uv\in F $, then $ d_u = \delta $ and $ d_v = \delta+1 $ or viceversa, and therefore

If $ uv\in F^c = E(G) \setminus F $, then $ d_u = d_v = \delta $ or $ d_u = d_v = \delta+1 $, and therefore

Since there are exactly $ A $ edges in $ F $ and $ m-A $ edges in $ F^c $, we have

This gives the equality.

Seeking for a contradiction assume that $ A $ is an odd integer.

Let $ \Gamma_1 $ be a subgraph of $ G $ obtained as follows: $ \Gamma_1 $ is induced by the $ n_1 $ vertices with degree $ \delta $ in $ V(G) $; denote by $ m_1 $ the number of edges of $ \Gamma_1 $. Handshaking Lemma implies $ n_1 \delta - A = 2m_1 $. Since $ A $ is an odd integer, $ \delta $ is also an odd integer. Thus, $ \delta+1 $ is even.

Let $ \Gamma_2 $ be the subgraph of $ G $ induced by the $ n_2 $ vertices with degree $ \delta+1 $ in $ V(G) $, and denote by $ m_2 $ the number of edges of $ \Gamma_2 $. Handshaking Lemma implies $ n_2(\delta+1) - A = 2m_2 $, a contradiction, since $ A $ is odd and $ \delta+1 $ is even.

Thus, we conclude that $ A $ is an even integer.

We will need the following result in the proof of Theorem 8 below.

Lemma 7. Given $ \alpha > 0 $, consider the function $ u: (0, \infty) \rightarrow (0, \infty) $ defined as $ u(t) = t^{ \alpha}+t^{- \alpha} $.Then $ u $ strictly decreases on $ (0, 1] $, $ u $ strictly increases on $ [1, \infty) $ and $ u(t) \ge u(1) = 2 $.

Proof. We have

Since $ \alpha > 0 $, we have $ u' < 0 $ on $ (0, 1) $ and $ u' > 0 $ on $ (1, \infty) $. This gives the result. The following figure shows the function $ u(t) $ for some values of $ \alpha $.

Theorem 6 gives the precise value of $ SDD_{ \alpha} $ when $ \Delta = \delta+1 $. Theorem 8 below provides a lower bound when $ \Delta > \delta+1 $.

Theorem 8. Let $ G $ be a graph with $ m $ edges, minimum degree $ \delta $ and maximum degree $ \Delta > \delta+1 $. Denote by $ A_0, A_1, A_2, $ the cardinality of the subsets of edges $ F_0 = \{ uv \in E(G) : \, d_{u} = \delta, d_{v} = \Delta \} $, $ F_1 = \{ uv \in E(G) : \, d_{u} = \delta, \delta < d_{v} < \Delta \} $, $ F_2 = \{ uv \in E(G) : \, d_{u} = \Delta, \delta < d_{v} < \Delta \} $, respectively. If $ \alpha > 0 $, then

Proof. Lemma 7 gives that the function

is increasing in $ d_{v} \in [\delta+1, \Delta-1] $ and so,

for every $ uv \in F_1 $.

In a similar way, Lemma 7 gives that the function

is decreasing in $ d_{v} \in [\delta+1, \Delta-1] $ and so,

for every $ uv \in F_2 $.

Also,

for any $ uv \in E(G) $.

We obtain

Hence,

We also have

3.   Computational study of the variable symmetric division deg index on random graphs

Here we deal with two classes of random graphs $ G $: Erdös-Rényi (ER) graphs $ G(n, p) $ and bipartite random (BR) graphs $ G(n_1, n_2, p) $. ER graphs are formed by $ n $ vertices connected independently with probability $ p \in [0, 1] $. While BR graphs are composed by two disjoint sets, sets 1 and 2, with $ n_1 $ and $ n_2 $ vertices each such that there are no adjacent vertices within the same set, being $ n = n_1+n_2 $ the total number of vertices in the bipartite graph. The vertices of the two sets are connected randomly with probability $ p \in [0, 1] $. Another work in this spirit is ^[18].

We stress that the computational study of the variable symmetric division deg index we perform below is justified by the random nature of the graph models we want to explore. Since a given parameter set $ (n, p) $ [$ (n_1, n_2, p) $] represents an infinite-size ensemble of ER graphs [BR graphs], the computation of $ SDD_\alpha(G) $ on a single graph is irrelevant. In contrast, the computation of $ \left < SDD_\alpha(G) \right > $ (where $ \left < \cdot \right > $ indicates ensemble average) over a large number of random graphs, all characterized by the same parameter set $ (n, p) $ [$ (n_1, n_2, p) $], may provide useful average information about the full ensemble. This computational approach, well known in random matrix theory studies, is not widespread in studies involving topological indices, mainly because topological indices are not commonly applied to random graphs; for very recent exceptions see ^{[19,20,21,22]}.

3.1.   Average properties of the $ SDD_\alpha $ index on Erdös-Rényi random graphs

From the definition of the variable symmetric division deg index, see Eq (1.1), we have that:

(i) For $ \alpha = 0 $, $ \left < SDD_0(G)\right > $ gives twice the average number of edges of the ER graph. That is,

(ii) When $ np\gg 1 $, we can approximate $ d_u \approx d_v \approx \left < d \right > $, then

(iii) By recognizing that the average degree of the ER graph model reads as

we can rewrite Eq (3.2) as

We stress that Eq (3.4) is expected to be valid for $ np \gg 1 $.

In Figure 2(a) we plot $ \left < SDD_\alpha(G) \right > $ as a function of the probability $ p $ of ER graphs of size $ n = 500 $. All averages in Figure 2 are computed over ensembles of $ 10^7/n $ random graphs. In Figure 2(a) we show curves for $ \alpha\in[0, 4] $. The dashed-magenta curve corresponds to the case $ \alpha = 0 $, which coincides with Eq (3.1). Moreover, we observe that

However, once $ \alpha > 0.5 $, the curves $ \left < SDD_\alpha(G) \right > $ versus $ p $ deviate from Eq (3.1), at intermediate values of $ p $, in the form of a bump which is enhanced the larger the value of $ \alpha $ is. Also, in Figure 2(a) we can clearly see that Eq (3.2) is satisfied when $ np\gg 1 $, as expected.

Now, in Figure 2(b) we present $ \left < SDD_\alpha(G) \right > $ as a function of the probability $ p $ of ER graphs of three different sizes. It is clear from this figure that the blocks of curves, characterized by the different graph sizes (and shown in different colors), display similar curves but displaced on both axes. Moreover, the fact that these blocks of curves, plotted in semi-log scale, are shifted the same amount on both $ x- $ and $ y- $axis when doubling $ n $ make us anticipate the scaling of $ \left < SDD_\alpha(G) \right > $. We stress that other average variable degree-based indices on ER random graphs (normalized to the graph size) have been shown to scale with the average degree ^[22]. Indeed, this statement is encoded in Eq (3.4), that we derived for $ np\gg 1 $ but should serve as the global scaling equation for $ \left < SDD_\alpha(G) \right > $.

Therefore, in Figure 2(c) we show $ \left < SDD_\alpha(G) \right > /n $ as a function of the average degree $ \left < d \right > $ where the same curves of Figure 2(b) have been used. There we verify the global scaling of $ \left < SDD_\alpha(G) \right > $, as anticipated in Eq (3.4), by noticing that the blocks of curves (painted in different colors) for different graph sizes fall on top of each other.

Also, from Figure 2(a)–(c) we observe that the inequality of Theorem 1 is extended to the average variable symmetric division deg index on random graphs:

see e.g., the blue arrow in Figure 2(a) which indicates increasing $ \alpha $. Here, the equality is attained if and only if $ p = 1 $. However, we have observed that $ \left < SDD_{ \alpha}(G) \right > \approx \left < SDD_{ \beta}(G) \right > $ already for $ \left < d \right > \ge 10 $.

3.2.   Average properties of the $ SDD_\alpha $ index on bipartite random graphs

In Figure 2(d), (e) we present curves of the $ \left < SDD_\alpha(G) \right > $ as a function of the probability $ p $ of BR graphs. For simplicity we show results for BR graphs composed by sets of equal sizes $ n_1 = n_2 $. In Figure 2(d) we consider the case of $ n_1 = n_2 = 500 $ while in (e) we report $ n_1 = n_2 = \{125, 250, 500\} $. In both figures we show curves for $ \alpha\in[0, 4] $ in steps of $ 0.5 $.

Since edges in a bipartite graph join vertices of different sets, and we are labeling here the sets as sets 1 and 2, we replace $ d_u $ by $ d_1 $ and $ d_v $ by $ d_2 $ in the expression for the $ SDD_\alpha(G) $ index below. Thus,

(i) For $ \alpha = 0 $, $ \left < SDD_0(G)\right > $ gives twice the average number of edges of the BG graph. That is,

(ii) When both $ n_1p\gg 1 $ and $ n_2p\gg 1 $, we can approximate $ d_1 \approx \left < d_1 \right > $ and $ d_2 \approx \left < d_2 \right > $, then

(iii) In the case we consider in Figure 2(d)–(f), where $ n_1 = n_2 = n/2 $, so that $ \left < d_1 \right > = \left < d_2 \right > = \left < d \right > $, Equation (3.7) reduces to

(iv) By recognizing that $ \left < d \right > = np/2 $ we can rewrite Eq (3.8) as

We stress that Eq (3.9) is expected to be valid for $ np \gg 1 $. We also note that Eq (3.9) has exactly the same form as Eq (3.4).

From Figure 2(d), (e) we note that

see the dashed-magenta curve in Figure 2(d). But once $ \alpha > 0.5 $, the curves $ \left < SDD_\alpha(G) \right > $ versus $ p $ deviate from Eq (3.6), at intermediate values of $ p $, in the form of bumps which are enhanced the larger the value of $ \alpha $ is. These bumps make clear the validity of inequality (3.5) on BR graphs; see e.g., the blue arrow in Figure 2(d) which indicates increasing $ \alpha $.

Finally, following the scaling analysis made in the previous subsection for ER graphs, in Figure 2(f) we plot the $ \left < SDD_\alpha(G) \right > /n $ as a function of the average degree $ \left < d \right > $ where the same data sets of Figure 2(e) have been used. Thus we verify that $ \left < SDD_\alpha(G) \right > $/n scales with $ \left < d \right > $, as anticipated in Eq (3.9); that is, the blocks of curves (painted in different colors) for different graph sizes coincide.

4.   Conclusions

In this paper we have performed analytical and computational studies of the variable symmetric division deg index $ SDD_\alpha(G) $. First, we provided a monotonicity property and obtained new inequalities connecting $ SDD_\alpha(G) $ with other well–known topological indices such as the variable inverse sum deg index, as well as the the modified Narumi-Katayama index. Then, we apply the index $ SDD_\alpha(G) $ on two ensembles of random graphs: Erd\H{o}s-Rényi graphs and bipartite random graphs. Thus, we computationally showed, for both random graph models, that the ratio $ \langle SDD_\alpha(G) \rangle/n $ is a function of the average degree $ \langle d \rangle $ only ($ n $ being the order of the graph). We note that this last result, also observed for other variable topological indices ^[22], is valid for random bipartite graphs only when they are formed by sets of the same size.

Since many important topological indices can be written as

an open problem is to extend the results of this paper to other indices of this kind.

Acknowledgments

J. A. M.-B. has been supported by CONACyT (Grant No. CB-2016-286633-F). J. M. R. and J. M. S. have been supported by a grant from Agencia Estatal de Investigación (PID2019-106433GBI00/AEI/10.13039/501100011033), Spain. J. M. R. has been supported by the Madrid Government (Comunidad de Madrid-Spain) under the Multiannual Agreement with UC3M in the line of Excellence of University Professors (EPUC3M23), and in the context of the V PRICIT (Regional Programme of Research and Technological Innovation).

Conflict of interest

The authors declare there is no conflict of interest.