Path planning for mobile robots in complex environments based on improved ant colony algorithm

1.   Introduction

Let $G = (V, E)$ be a connected, undirected and unweighted simple graph having $\mid V(G)\mid = n$ vertices and $\mid E(G)\mid = m$ edges unless stated. Simple means that we do not allow loops or multiple edges. For a vertex $v \in V(G)$, we denote the degree of $v$ by $d_{G}(v)$ or briefly by $d_v$. A vertex with degree one is called a pendant vertex and we shall use the term pendant edge for an edge having a pendant vertex.

Topological graph indices are defined and used in many areas in recent years to study several properties of different objects such as atoms and molecules solely by means of some mathematical techniques. Several topological graph indices have been defined and studied by many mathematicians and chemists as most graphs are generated from molecules by replacing atoms with vertices and bonds between them with edges. These indices are defined as invariants measuring several physical, chemical, pharmaceutical, biological properties of graphs which are modelling real situations. They can be grouped mainly into three classes according to the way they are defined; by vertex degrees, by distances or by matrices. The first graph index was defined in 1947 by Wiener to determine the boiling points of alkanes ^[17]. In ^[8], the notion of energy in relation with the Estrada index of the Phenylenes were studied. In ^[10], some physico-chemical parameters of alkanes were studied by means of three graph indices called reciprocal Randić index, reduced second Zagreb index and reduced reciprocal Randić index. Two of the earliest defined topological graph indices are called the first and second Zagreb indices defined in 1972 by Gutman and Trinajstic, ^[11], and are often referred to due to their uses in QSAR and QSPR studies. In ^[3], some results on the first Zagreb index together with some other indices are given. In ^[4], the multiplicative versions of these indices are studied. Zagreb indices of subdivision graphs were studied in ^[15] and these were calculated for the line graphs of the subdivision graphs in ^[14]. In ^[16], all versions of Zagreb indices of subdivision graphs were studied. In ^[13], relations between indices and graph energy was considered.

If all the vertices of a graph have the same degree, then the graph is called regular. Regularity makes calculations easier in many occasions and regular graphs usually form examples or counterexamples in many areas of graph theory. A graph is not regular, called irregular, which has at least two unequal vertex degrees. Irregularity may occur slightly or strongly. As a result of this, several measures for irregularity have been defined and used by some authors. The most throughly investigated ones are the Albertson index (which is also called irregularity index, third Zagreb index or Kekule index) defined as

see ^[1,7,9], the Bell index

see ^[2] and ^[9] and sigma index

In this paper, we study the effect of adding a new edge to a graph on Albertson and Bell indices by considering the possible ways of adding the new edge. We will construct a graph class such that $Alb$ index of the graphs in this class covers all positive even integers. We do the similar calculations for Bell index. For both indices, we exclude adding a new edge which increases the number of components of the graph.

2.   Effect of edge addition on Albertson irregularity index

First we recall some properties of the Albertson index. First we note that the Albertson index $Alb(G)$ of a simple graph $G$ is even: As the parities of each term $|d_u - d_v|$ and $(d_u - d_v)^2$ in these indices given in Eqs (1.1) and (1.3) are the same, the result follows by the fact that the sigma index of a simple graph is even, see ^[12].

We now study the effect of adding a new edge to a graph on its irregularity index. There are three possible ways of adding a new edge. The new edge can be added to the graph either at a pendant vertex or at a vertex of degree greater than $1$ to form a new pendant edge, or between two existing vertices to form a new non-pendant edge.

Theorem 2.1. Let $G$ be a connected simple graph having at least three vertices. Let the neighbours of the vertex $u$ with degree $d_G(u) = t > 1$ be $v_1, \ v_2, \ \cdots, \ v_t$ with degrees $d_G(v_1), \ d_G(v_2), \ \cdots, \ d_G(v_t)$, respectively. Let $k$ be a positive integer such that $d_G(v_i) \leq d_G(u)$ for $i = 1, \ 2, \ \cdots, \ k$ with $k \leq t$, and $d_G(v_i) > d_G(u)$ for $i = k+1, \ k+2, \ \cdots, \ t$. Then $Alb(G)$ increases by $2k$ when a new pendant edge $e$ is added to $G$ at $u$.

Proof. As $d_G(u) = t$, we have

Secondly consider the graph $G+e$ where $e$ is the new pendant edge with end points $u$ and $w$. Then noting that $d_{G+e}(u) = t+1$ and $d_{G+e}(w) = 1$, we have

giving the required result as the degrees of each pair of vertices $r$ and $s$ in the last sum increase by one and as $\sum_{i = 1}^{t} d_{G+e}(v_i) = \sum_{i = 1}^{t} d_{G}(v_i)$:

Note that the last sum in each row taken over all edges of $G$ which are not incident to the vertex $u$ is fixed and does not effect the Albertson index.

This result means that the increase of the Albertson index when a new pendant edge $e = uw$ is added to a vertex $u$ having degree $d_G(u) > 1$ is equal to twice the number of the neighbouring vertices of $u$ which have degree less than or equal to $d_G(u)$.

Note that in Theorem 2.1, we had the condition that $d_G(u) = t > 1$. We now specially mention a frequently used and therefore very useful situation where $d_G(u) = t = 1$, that is, the vertex $u$ of $G$ is a pendant vertex:

Theorem 2.2. Let $G$ be a connected simple graph with at least three vertices. If $u$ is a pendant vertex, then adding a new (pendant) edge to $u$ does not change $Alb (G)$.

Proof. Let $u$ be a pendant vertex of the graph $G$ and let $v$ be its unique neighbour in $G$ with degree $d_G(v)$, see Figure 1. Then

Adding a new pendant edge $uw$ to $G$ at $u$ increases $d_G(u)$ by 1 and clearly $d_{G+e}(w) = 1$ implying

as $G+e$ has at least four vertices. That gives the result.

The condition that $G$ has at least three vertices is necessary as when $G$ has only one vertex, it is trivial; and if $G$ has two vertices then $G$ is $P_2$ and adding a new edge to obtain $P_3$ increases $Alb (G)$ by 2.

Finally, we try to determine the effect of adding a new edge on $Alb$ index, which joins two existing non-adjacent vertices of $G$:

Theorem 2.3 (Joining two existing non-adjacent vertices of $G$). Assume that $G$ is a connected simple graph and let $u$ and $v$ be two non-adjacent vertices of $G$. Let $d_G(u) = t$ and $d_G(v) = k$. Let us denote the degrees of the $t$ neighbours $x_1, \ x_2, \ \cdots, \ x_t$ of $u$ with $r_1, \ r_2, \ \cdots, \ r_t$, and the degrees of the $k$ neighbours $y_1, \ y_2, \ \cdots, \ y_k$ of $v$ with $s_1, \ s_2, \ \cdots, \ s_k$ (some of $x_i$'s could coincide with some of $y_j$'s). Without loss of generality, we can assume that $r_i \leq t$ for $1 \leq i \leq t_0 \leq t$ and $r_i > t$ for $t_0+1 \leq i \leq t$, and that $s_j \leq k$ for $1 \leq j \leq k_0 \leq k$ and $s_j > k$ for $k_0+1 \leq j \leq k$. If we add a new edge $e = uv$ to $G$ by joining the vertices $u$ and $v$, then

Proof. Now

Let us add a new edge $e = uv$ to join the non-adjacent vertices $u$ and $v$ in $G$. Denote the graph obtained in this way by $G+e$. Then

Therefore

Now $|t+1-r_i| - |t-r_i| = 1 \ \ \mbox{or} \ -1$ according to $r_i \leq t$ or $r_i > t$, respectively. Similarly $|k+1-s_j| - |k-s_j| = 1 \ \ \mbox{or} \ -1$ according to $s_j \leq k$ or $s_j > k$, respectively. Hence

Note that we can omit calculating the term $|d_G(u)-d_G(v)|$ corresponding to the edges with $d_G(u) = d_G(v)$ by the definition of Albertson index $Alb(G)$. We can apply this fact to paths and cycles. Whenever there are $n$ consecutive vertices on a path all of degree $2$, replacing them with a single vertex of degree $2$ does not change the Albertson index. In ^[12], this method was called path reduction. Similarly, if there are $n$ successive vertices on a cycle all having degree $2$, we can replace them with only one vertex of degree $2$. This is called cyclic reduction. These reduction ideas are very useful in reducing the graphs under question to calculate the $Alb(G)$. We can replace all branches of length at least two with an edge. That is, we can calculate the $Alb(G)$ for the graph on the right in Figure 2 instead of calculating the same number which is the same for the graph on the left.

For example, let $T_{r, s}$ be the tadpole graph of order $r+s$ obtained by adding a path of length $s$ at a vertex of a cycle of length $r$ and let us want to calculate the Albertson index of the tadpole graphs $T_{5, 4}$, $T_{7, 3}$ or in general $T_{r, s}$, with $r \geq 3$ and $s \geq 1$, instead, we can calculate only the Albertson index of $T_{3, 2}$ as all of these indices are the same after path and cyclic reduction.

The following transformation will be useful in solving the inverse problem for Albertson index:

Transformation 1. Let $G$ be a graph possessing a vertex $v$ of degree $d_G(v)\geq 3$. Let $u$ be a pendant vertex of $G$ adjacent to $v$. Construct the graph $G^{*}$ by attaching two new pendant edges to $u$, cf. Figure 3 and 4.

The following result says that applying Transformation 1 to a connected simple graph having a pendant vertex increases the Albertson index by 2:

Lemma 2.1. For any connected simple graph $G$, different from the null graphs and path graphs, with at least four vertices,

Proof. As $d_G(v) \geq 3$ and as $Alb(G) = d_G(v) -1 + \sum_{xy \in E(G-\{u\})} |d_G(x)-d_G(y)|$ and $Alb(G^*) = d_G(v) - 3 + 2 + 2 + \sum_{xy \in E(G-\{u\})} |d_G(x)-d_G(y)|$, we obtain the required result.

Note that we had the condition that $v$ is a vertex of degree at least $3$ in defining Transformation 1. If we omit this condition and allow that $d_G(v)$ could be any positive integer, then similarly to the proof of Lemma 2.1, we would have

for the graph $G$ in Figure 3. The graph $G+\{e_1, e_2\}$ in Figure 4 has

Then we have,

Now we have several cases to consider:

If $d_G(v) = 1$, then $G$ is $P_2$ which has Albertson irregularity index equal to 0, and $G+\{e_1, e_2\}$ is $S_4 = K_{1, 3}$. In this case, the increase of Albertson irregularity index is $6$ by Eq (2.1).

If $d_G(v) = 2$, then our graph $G$ is as in Figure 5.

Applying Transformation 1 to $G$ gives the graph in Figure 6.

Here the increase is $4$ by Eq (2.1).

If $d_G(v) = 3$, then the increase of Albertson index is equal to $2$.

3.   Effect of edge addition on Bell index

Secondly we focus on the Bell index. As it is defined by means of the average vertex degree, we should concentrate on some properties of this special degree. Let $D = \{1^{(a_{1})}, 2^{(a_{2})}, 3^{(a_{3})}, \cdots, \Delta^{(a_{\Delta})}\}$ be a realizable degree sequence and $G$ be one of its realizations. In ^[5], an invariant number denoted by $\Omega(G)$ for a graph $G$ was defined as

Some of its properties were studied in ^[5,6]. It is closely related to the cyclomatic number of the graph gives direct information on all the realizations of a given degree sequence. $\Omega(G)$ has the following important computational property: For any graph $G$,

In ^[5], the number $r$ of the closed regions (faces) which are bounded by the edges of the graph $G$ was formulized by

Note that a closed region could be bounded by any $n$-cycle ($n$-gon) where $n \geq 3$, a loop (1-gon) or multiple edges (2-gon). Also in ^[6], some extremal problems on the numbers of components and loops of all realizations of a given degree sequence. We now apply this new invariant $\Omega$ to Bell irregularity index. First we prove the following lemma:

Lemma 3.1. The necessary and sufficient condition for the average vertex degree of a connected simple planar graph to be greater than 2 is that $\Omega(G) \geq 2$.

Proof. Let the average vertex degree of a connected simple graph $G$ be denoted by $\overline{d}$. $\overline{d} > 2$ iff $m > n$ iff $G$ has at least two cycles iff $\frac{\Omega(G)}{2}+1 \geq 2$ by above iff $\Omega(G) \geq 2$.

As we consider the integer values of the Bell index, we shall assume that the average vertex degree $\overline{d}$ of $G$ is an integer. In general, if $n|2m$, then $\overline{d}$ is a positive integer. In particular, when $n$ is odd and $n|m$, then $\overline{d}$ is a positive integer. We first have

Lemma 3.2. A tree $T_n$ with $n$ vertices has integer average vertex degree iff $n|2$. Hence no tree having at least 3 vertices cannot have integer average vertex degree.

Proof. Let $G \cong T_n$ be a tree with $n$ vertices. Then it is well known that $n = m+1$. Then the average vertex degree is

and for this number to be an integer we must have $n|2$.

That is, among all trees, only those with 1 or 2 vertices can have integer average vertex degree.

Theorem 3.1. Let $G$ be a connected graph. Adding a pendant edge to $G$ does not change the average vertex degree iff $G$ is unicyclic. That is

Proof. Let the new pendant edge be $e = uv$ as in Figure 7.

Let $d_G(u)$ be the degree of $u$ in $G$. Then $d_{G+e}(u) = d_G(u)+1$. Note that

and

as the degree of $u$ increases by 1 and $d_{G+e}(v) = 1$. Therefore to have $\overline{d_{G+e}} = \overline{d_G}$, we must have

and hence $m = n$. This means that $\Omega(G) = 2(m-n) = 0$ and we have $r = 1$. That is $G$ must be unicyclic.

Corollary 3.1. If $G$ is a connected unicyclic graph, then $\overline{d_G} = 2$.

Proof. By Theorem 3.1, we know that $m = n$. So $\overline{d_G} = \frac{2m}{n} = 2$.

Theorem 3.2. The necessary and sufficient condition for $\Omega(G) = 0$ is $\overline{d} = 2$.

Proof. $\Omega(G) = 0$ iff $2(m-n) = 0$ iff $m = n$ iff $\overline{d} = \frac{2m}{n} = 2$.

Theorem 3.2 implies the following useful result:

Theorem 3.3. Let $G$ be a connected simple graph. Then $G$ is unicyclic iff $m = n$.

Proof.

Corollary 3.2. If $\Omega(G) = 0$, then $n \geq 3$.

Proof. By Theorem 3.2, $\overline{d} = 2$. That is $\frac{2m}{n} = 2$ implying $m = n$. We know that for a simple graph, we have

so the fact that $m = n$ gives the required result.

Theorem 3.4. Let $G$ be a connected simple graph with average vertex degree $\overline{d} \geq 2$. Then

Proof. The fact that $\overline{d} = 2m/n$ implies that $2m = n\overline{d}$. As $\Omega(G) = 2(m-n)$, we obtain the result.

We can now investigate the change of the Bell index under the addition of a pendant edge.

Theorem 3.5. Let $G$ be a connected unicylic graph and let $u \in V(G)$ have degree $d_G(u)$. Then adding a pendant edge to $G$ at $u$ increases the Bell index of $G$ by $2d_G(u)-2$.

Proof. Let $G$ be a connected unicyclic graph. Then $G+e$ is also a connected unicyclic graph as we add a pendant edge. By Corollary 3.1, we have

Now

and

implying that

as required.

Corollary 3.3. Let $G$ be a connected unicyclic graph and let $u \in V(G)$ be a pendant vertex. Adding a new pendant edge to $G$ at $u$ does not change the Bell index.

Proof. As $d_G(u) = 1$, by Theorem 3.5, the result follows.

We can give another property of the average degree:

Theorem 3.6. Let $G$ be a connected graph having at least three vertices and let $u$ and $v$ be two non-adjacent vertices having degree $d_G(u)$ and $d_G(v)$, respectively. Let $\overline{d_G}$ be an integer. If we add a new edge $e = uv$ to $G$, the obtained graph $G+e$ has non-integer average vertex degree.

Proof. Let us assume that the degrees of the $n$ vertices of $G$ are $d_G(v_1), \ d_G(v_2), \ \cdots, \ d_G(v_{n-2})$, $\ d_G(u)$ and $d_G(v)$. Then the degrees of the same $n$ vertices in $G+e$ would be $d_G(v_1), \ d_G(v_2), \ \cdots$, $\ d_G(v_{n-2}), d_G(u)+1$ and $d_G(v)+1$. Hence

is an integer by the assumption. Then

cannot be an integer as $n \geq 3$.

We now consider the general case of adding a new edge $e$ which can be seperated into two: Adding a new pendant edge at a vertex $u$ of degree $d_G(u)$ and adding a new non-pendant edge between two existing vertices $u$ and $v$ of the graph $G$. First we study the former case:

Theorem 3.7. Let $G$ be a connected graph. Let $G+e$ be the graph obtained by adding a new pendant edge $e$ at an existing vertex $u$ of degree $d_G(u)$. Then

Proof. Let $e = uw$. Recall that

The Bell index of $G+e$ is

as $d_{G+e}(u) = d_{G}(u)+1$, $d_{G+e}(w) = 1$ and as each vertex $v$ of $G+e$ different from $u$ and $w$ is a vertex of $G$ different from $u$. Hence

as $\sum_{v\in V(G), v \neq u} d_{G}(v) = 2m-2$, $\sum_{v\in V(G), v \neq u} 1 = n-1$, $\sum_{v\in V(G+e), v \neq u, w} d_{G+e}(v) = 2m_{G+e} - d_{G+e}(u) - d_{G+e}(w) = 2m - d_G(u)$ and $\sum_{v\in V(G+e), v \neq u, w} 1 = n-1.$

Our last result deals with the case of adding a new non-pendant edge between two existing vertices $u$ and $v$ of the graph $G$:

Theorem 3.8. Let $G$ be a connected graph. Let $G+e$ be the graph obtained by adding a new non-pendant edge $e$ between two existing vertices $u$ and $v$ of degrees $d_G(u)$ and $d_G(v)$ of $G$, respectively. Then

Proof. Note that

Similarly, the Bell index of $G+e$ is

Hence

4.   Conclusion

One of the ways of obtaining information on a graph by means of information on another graph obtained from the first graph is the vertex and edge deletion and/or addition. When we know the change of some parameter of a graph when a vertex or an edge is deleted or added, it is possible to apply this operation successively and obtain the required parameter of a large graph by means of the same parameter of a relatively smaller graph.

Regular graphs have some easily-guessed properties which makes irregular ones more popular. To determine the irregularity of a graph, some irregularity indices such as Bell, Albertson, sigma indices are introduced. In this work, the effect of edge and vertex addition on two of the irregularity indices, Bell and Albertson indices, are determined.

As the irregularity is closely related to the variance of a graph, it is also possible to study the connections between graph theory and statistics by means of the results given here.

Conflicts of interest

The authors declare no conflict of interest.