# Certain Distance-Based Topological Indices of Parikh Word Representable Graphs

Authors: Nobin Thomas; Lisa Mathew; Sastha Sriram; Atulya K. Nagar; K. G. Subramanian
Journal: Journal of Mathematics
 (2021)

---

## Abstract

Relating graph structures with words which are finite sequences of symbols, Parikh word representable graphs (PWRGs) were introduced. On the other hand, in chemical graph theory, graphs have been associated with molecular structures. Also, several topological indices have been defined in terms of graph parameters and studied for different classes of graphs. In this study, we derive expressions for computing certain topological indices of PWRGs of binary core words, thereby enriching the study of PWRGs.


---

## Body

## 1. Introduction

Among various studies that involve graphs for analyzing and solving different kinds of problems, relating words that are finite sequences of symbols with graphs is an interesting area of investigation (for example, [1–5]). Based on the notion of subwords (also called scattered subwords) of a word and the concept of a matrix called Parikh matrix of a word, introduced in [6] and intensively investigated by many researchers (for example, [7–13] and references therein) with entries of the Parikh matrix giving the counts of certain subwords in a word, a graph called Parikh word representable graph (PWRG) of a word, was introduced in [14] and its relationship with the corresponding word and partition was studied in [15].On the other hand, there has been a great interest in various topological indices associated with graphs (for example, [16–19]) due to their application in the area of chemical graph theory [20], which deals with representations of organic compounds or equivalently their molecular structures as graphs, with atoms other than hydrogen often represented by vertices and covalent chemical bonds by edges. In fact, in chemical graph theory, there have been attempts to capture the molecular structure in terms of the topological index of the corresponding graph.There are a number of studies (for example, [21]) of various topological indices of graphs establishing formulae for computing the indices and also providing upper and lower bounds on the values of such indices. Recently, in [22], properties of one of the important topological indices, namely, Wiener index and some of its variants related to PWRGs of binary words, were studied. In this study, certain distance-based topological indices of PWRGs of binary core words are investigated.


## 2. Preliminaries

The basic definitions and notations relating to words are as given in [23, 24]. We recall here some of the needed notions.An ordered alphabetΣ is a set of symbols with an ordering on its symbols. For example, Σ=a1,a2,…,ak with an ordering a1<a2<⋯<ak is an ordered alphabet, written as Σ=a1<a2<⋯<ak. A word w over Σ is a finite sequence of symbols belonging to Σ. A word w′ is a scattered subword or simply called a subword of a word w over Σ if and only if there exist u1,u2,…,un, ui∈Σ for 1≤i≤n and words (possibly empty) v0,v1,…,vn over Σ, such that w′=u1u2,…,un,andw=v0u1v1u2v2,…,vn−1unvn. The number of occurrences of a word u as a subword of w is denoted by wu. For example, in the word w=aababb over the ordered binary alphabet a<b, the number of a’s is wa=3, the number of b’s is wb=3, and the number of subwords ab’s is wab=8. In fact, the word ab as a subword of aababb is shown with the symbols a and b of ab shown in bold in aababb.(1)aababb,aababb,aababb,aababb,aababb,aababb,aababb,aababb.The set of all words over an alphabetΣ, including the empty word λ with no symbols, is denoted by Σ∗. Unless stated otherwise, we consider only a binary alphabet Σ=a<b.Definition 1.
[13] Let w∈Σ∗. The core of w, denoted by corew, is the unique word w0 of w with the smallest possible length, such that w∈b∗w0a∗. A word w∈Σ∗ is called a core word if and only if corew=w.
Clearly, a nonempty binary wordw∈Σ∗ is a core word if and only if w starts with a and ends with b.
In [14], a simple graph, called Parikh word representable graph (PWRG), was defined corresponding to a word over an ordered alphabet. Restricting our attention to binary words, we recall now this PWRG.Definition 2.
[14] For a binary word w of length n over Σ=a<b, we define a simple graph G=Gw, called Parikh word representable graph (PWRG), with n labeled vertices 1,2,…,n representing the positions of the consecutive letters of w, such that for each occurrence of the subword ab in w, there is an edge between the vertices in G, corresponding to the positions of a and b in w. We say that the binary word w represents the graph G=Gw and a graph G is Parikh word representable if there exists a binary word w that represents G.
It is to be noted thatPWRGGw of a binary word w over a<b is a bipartite graph [14] with as many vertices as the length w of w and as many edges as the number of occurrences of the subword ab in w. Figure 1 shows the PWRG of a binary word aababab over the ordered binary alphabet Σ=a<b. The graph Gaababab has 7 vertices and 9 edges. Note that the length of the word aababab is 7, and there are 9 occurrences of the subword ab in aababab.
In this study, we deal with only binary core words and the corresponding PWRGs. Also, we note that for a nonempty binary core word of the formw=an1ban2b,…,anwbb, where n1≥1 and nk is nonnegative for each k, 2≤k≤wb, the number of edges in the corresponding PWRG G(w) is(2)wab=n1+n2+⋯+nwb+⋯+n1+n2+n1.
Note that in the wordw, nk,1≤k≤wb, which is a power of a, indicates that there are nk vertices labeled a in the graph Gw with each of these joined to all the vertices that correspond to the subsequent b’s in the word w.Figure 1
ThePWRG of the word aababab.


## 3. Distance-Based Topological Indices

We consider only simple graphs, and for notions related to graphs, we refer to [25]. Let G=V,E be a connected graph with vertex set VG=V and edge set EG=E. The distance between the vertices u and v of G, denoted by du,v, is defined as the length of a shortest path between u and v in G. The degree of a vertex u of G, which is the number of edges incident at u, is denoted by degu. For a given vertex u in a connected graph G, the eccentricity ϵu is defined as the maximum distance between u and any other vertex in G.Definition 3.
[26] The Harary index of a connected graph G is defined as the sum of the reciprocals of distances between all pairs of vertices of G, i.e.,(3)HG=∑u,v⊆VG1du,v.
The Harary index [26] of a connected graph is a topological index which has been extensively investigated (for example, [27–29]).Theorem 1.
The Harary index of the PWRGG(w), for w=an1ban2b,…,anlb, n1≥1, nk≥0 for 2≤k≤l, is given by(4)HGw=1123wawa−1+3wbwb−1+8wab+4wawb.Proof.
We consider pairs of verticesu,v in the PWRG G(w) corresponding to the word w=an1ban2b…anlb, with u,v∈1,2,…,n, where the label of u appears before the label of v in w. There are now four cases to be considered. We will refer to a pair u,v of such vertices with(i)
Bothu and v labeled a(ii)
u labeled a and v labeled b(iii)
u labeled b and v labeled a(iv)
Bothu and v labeled b
They are given as a pair of type 1, 2, 3, and 4, respectively. There aren1+n2+⋯+nlC2=waC2=1/2wawa−1 pairs of vertices of type 1 and lC2=wbC2=1/2wbwb−1 of type 4, and the distance between each such pair is 2. Here, nCr is the binomial representing the number of ways of choosing r objects from n objects). There are ln1+l−1n2+⋯+nl=wab pairs of vertices of type 2 with distance 1 and n2+2n3+⋯+l−1nl=wawb−wab pairs of vertices of type 3 with distance 3, since wab=n1+n2+⋯+nwb+⋯+n1+n2+n1. Hence,(5)HGw=14wawa−1+wbwb−1+wab+13wawb−wab,which yields the required result.Theorem 2.
The Harary indexHGw of a PWRGGw=V1∪V2,E with V1=wa=p,V2=wb=q for the word w=an1ban2b,…,anqb,n1≥1,nk≥0 for 2≤k≤l, is bounded by(6)1123p2+3q2+4pq+5p+5q−8,and above by(7)14p2+q2+4pq−p−q.
The bounds are attained onGabq−1ap−1b and Gapbq, respectively.Proof.
SinceGw is connected, wab=E≥p+q−1 [25]. Also, wab≤pq [6]. Hence, from Theorem 1, the Harary index of Gw is(8)HGw≤1123p2+3q2+12pq−3p−3q=14p2+q2+4pq−p−q,which is the Harary index of the PWRGGapbq and(9)HGw≥1123p2+3q2+4pq+5p+5q−8,which is the Harary index of the PWRGGabq−1ap−1b.Definition 4.
[30] The eccentric connectivity index of a connected graph G with vertex set V is defined as ζcG=∑v∈Vϵvdegv, where ϵv is the eccentricity of v.
The total eccentricity index [31] of the graph G is ζG=∑v∈Vϵv.
The topological index, namely, eccentric connectivity index, was introduced in [30] and has been widely investigated for different classes of graphs (for example, [32–35] and references therein).Theorem 3.
The eccentric connectivity index of thePWRGGw, for w=an1ban2b,…,anlb,n1≥1, is given by(10)ζcGw=6wab−kwa−n1wb,ifwa>1andwb=l>1,3wb,ifn1=1,ni=0,for1<i≤landl>1,3wa,ifn1>1andl=1,2,ifn1=1,l=1,where k be the number of b’s succeeding the last a in w.Proof.
LetGw be the PWRG corresponding to w=an1ban2b,…,anlb. Then, the vertices representing all a’s preceding the first b and all b’s succeeding the last a are of eccentricity two, whereas the eccentricity of each of the remaining vertices is three. The vertices u and v in Gw are adjacent if and only if u represents a and v represents b, such that the position of b in w is greater than the position of a in w. This implies that the contribution to the eccentric connectivity index from the vertices in Gw represents(i)
a’s in the first block an1b is 2n1wb, as each vertex corresponding to a has degree wb(ii)
b’s succeeding the last a is 2kwa (where k≥1 is the number of b’s succeeding the last a) as each vertex corresponding to such ab has degree wa and(iii)
The remaininga’s and b’s in w is 32wab−n1wb−kwa, since the sum of the degrees of all vertices in Gw is 2wab
Therefore,(11)ζcGw=2n1wb+2kwa+32wab−n1wb−kwa=6wab−n1wb−kwa.
Now, ifn1=1 and ni=0 for 1<i≤l, then w=abl, and a is of eccentricity one and degree l and each b is of eccentricity two and degree one. Therefore,(12)ζcGw=3wb,ifn1=1andni=0,1<i≤l.
Similarly, ifn1>1 and l=1, w=an1b and b is of eccentricity one and degree n1, while each a is of eccentricity two and degree one. Thus, ζcGw=3wa. Again, if n1=1 and l=1, then w=ab, and both vertices have eccentricity one and degree one and so ζcGw=2. Hence the result.Remark 1.
It can be seen that the total eccentricity index of thePWRGGw, for w=an1ban2b,…,anlb,n1≥1, is given by(13)ζGw=3w−k−n1,ifwa>1andwb=l>1,2wb+1,ifn1=1,ni=0,for1<i≤landl>1,2wa+1,ifn1>1andl=1,2,ifn1=1,l=1,where k is the number of b’s succeeding the last a in w.Theorem 4.
The eccentric connectivity indexζcGw of a PWRGGw=V1∪V2,E with V1=wa=p>1,V2=wb=q>1 for the word w=an1ban2b,…,anqb,n1≥1,ni≥0 for 2≤i≤l, is bounded above by ζcmax and below by ζcmin where(14)ζcmax=4pq,ifp+q≤6,4pq+p+q−6,ifp+q≥6and2pq−8p−8q+24≤0,6pq−7p−7q+18,ifp+q>6and2pq−8p−8q+24≥0,ζcmin=5p+5q−6.
The upper bound is attained onGapbq when p+q≤6, on Gap−1babq−1 when p+q≥6,2pq−8p−8q+24≤0 and on Gabap−2bq−2ab when p+q>6,2pq−8p−8q+24≥0, while the lower bound is attained on Gabq−1ap−1b.Proof.
Sincewa=p>1,wb=q>1, using Theorem 3, the eccentric connectivity index ζcGw=6wab−kwa−n1wb will be a maximum if wab is as large as possible, while n1 and k are as small as possible. Here, k is the number of b’s succeeding the last a in w. It is known [10] that for a binary word w,wab≤pq when wa=pandwb=q. The word apbq has the maximum number pq of subwords ab, and so the eccentric connectivity index of the PWRG corresponding to this word is maximum but only when p+q≤6. We note that p>1 and q>1, and the word w is a core word by the hypothesis. When p+q>6, it can be verified that this word fails to provide the maximum eccentric connectivity index for the corresponding PWRG due to the fact that all the vertices in the PWRG of apbq have only eccentricity 2. When wab=pq−1, which is the largest number nearer to the maximum pq, the word ap−1babq−1 has pq−1 subwords ab, while the vertices in the PWRG corresponding to the first b and the next a in this word have eccentricity 3 and degrees p−1 and q−1, respectively. The eccentric connectivity index of the PWRG corresponding to this word ap−1babq−1 is maximum when p+q≥6 but only when 2pq−8p−8q+24≤0. When p+q>6 and 2pq−8p−8q+24>0, it can be verified that the word ap−1babq−1 fails to provide the maximum eccentric connectivity index for the corresponding PWRG. On the other hand, the word abap−2bq−2ab has the minimum value 1 for n1 and k and has as many a’s as possible to the left and as many b’s as possible to the right of the word, thus providing maximum degrees for the vertices in the PWRG corresponding to the a’s and b’s in ap−2bq−2 which have eccentricity 3. In fact, more formally, for w=an1ban2b,…,anqb,n1≥1,q>1, n1+n2+⋯nq=p>1, we can show that(15)ζcGw=6pq−n1q−3qnq+2p−3n1+3n2+5n3+⋯+2q−3nq−1+q−1nq.
In order to maximize this expression with the constraintn1+n2+⋯+nq−1+nq=p>1, we have to minimize the negative terms, and so we have to take n1=nq=1 and n2=p−2, while ni=0, for 3≤i≤q−1. Note that we cannot choose n2=0 as there are p>1 number of a’s. Hence, it may be observed that for given values of p and q, the maximum value of ζcGw is attained on one of the three words w1=apbq,w2=ap−1babq−1, or w3=abap−2bq−2ab whose corresponding PWRGs Gw1,Gw2,Gw3 have their eccentric connectivity indices as η1=4pq,η2=4pq+p+q−6,η3=6pq−7p−7q+18, respectively. Note that η1≥η2 when p+q≤6, while the expression 2pq−8p−8q+24 is the difference η3−η2. Hence, the maximum value is attained on Gapbq when p+q≤6, on Gap−1babq−1 when p+q≥6,2pq−8p−8q+24≤0, and on Gabap−2bq−2ab, when p+q>6 and 2pq−8p−8q+24>0.
On the other hand, forp>1,q>1, ζcGw is minimum when wab is minimum, and this happens for w=an1bq−kap−n1bk with wab=n1q+pk−n1k minimum when n1=k=1. Hence, the minimum value 5p+5q−6 of ζcGw is attained on Gabq−1ap−1b.Theorem 5.
The total eccentricity indexζGw of a PWRGGw=V1∪V2,E with V1=wa=p,V2=wb=q for the word w=an1ban2b,…,anqb,n1≥1,ni≥0 for 2≤i≤q, is bounded above by 3p+3q−2 and below by 2p+2q. This upper bound is attained on Gw, for any word w=abuab, where ua=p−2,ub=q−2. In particular, it is achieved on Gabq−1ap−1b. The lower bound is achieved on Gapbq.Proof.
Ifk is the number of b’s following the last a in w, it is clear that the maximum value of ζGw is attained when n1=1,k=1 and the minimum is attained when n1=p,k=q. Hence the result.
Yet another topological index, called eccentricity connectivity coindex [36, 37] of a connected graph, is defined as the eccentricity sum of all nonadjacent vertex pairs in the graph. We consider this index here for PWRGs.Definition 5.
[36, 37] The eccentric connectivity coindex ζc¯G of a connected graph G with edge set EG is defined as(16)ζc¯G=∑uv∉EGϵu+ϵv,where ϵx is the eccentricity of the vertex x of G.Theorem 6.
The eccentric connectivity coindexζc¯Gw of the PWRGGw, for w=an1ban2b,…,anlb,n1≥1,nk≥0 for 2≤k≤l is given by(17)ζc¯Gw=w−13w−n1−k−6wab+kwa+n1wb,ifwa>1,l>12wbwb−1,ifn1=1,ni=0,1<i≤l,l>1,2wawa−1,ifn1>1,l=1,0,ifn1=1,l=1,where k is the number of b’s succeeding the last a in w.Proof.
It has been shown [36, 37] that ζc¯G=∑u∈VGϵun−1−degu which can be written as ζc¯G=n−1∑u∈VGϵu−ζcG, where n is the number of vertices in the graph G and ϵu is the eccentricity of the vertex u. If wa>1 and l>1, then the vertices corresponding to the first block a’s and kb’s succeeding the last a are of eccentricity two, and the remaining vertices are of eccentricity three.
Therefore,(18)ζc¯Gw=w−13w−n1−k−6wab+kwa+n1wb.
Now, ifn1=1,ni=0 for 1<i≤l and l>1, then the vertex corresponding to a is of eccentricity one and the remaining vertices are of eccentricity two.
Therefore,ζc¯Gw=2wbwb−1.
Now, ifn1>1andl=1, then the vertex corresponding to b is of eccentricity one and the remaining vertices are of eccentricity two. Then, ζc¯Gw=2wawa−1.
Ifn1=1,l=1, then. ζc¯Gw=0.


## 4. An Illustration

Bipartite graphs have been used in investigating structural features in the areas of molecular biology and chemistry (for example, [38, 39]). We consider here a complete bipartite graph Km,n,m,n>1, with the bipartition V1∪V2 of the vertices such that V1=u1,…,um and V2=v1,…,nn. The graph Km,n is a PWRGGw corresponding to the word w=ambn over the alphabet a<b.First, we observe the following facts relating toKm,n.(i)
For1≤i,j≤m,1≤r,s≤n, ui,uj∈V1,i≠j, and vr,vs∈V2,r≠s, we have dui,uj=dvr,vs=2,dui,vr=1, ϵui=ϵvr=2(ii)
In the graphKm,n,m,n>1, there are 1/2mm−1 unordered pairs of vertices ui,uj,i≠j, 1/2nn−1 unordered pairs of vertices vr,vs,r≠s, and mn unordered pairs of vertices ui,vr(iii)
The degree of each vertexui,1≤i≤m is degui=n, and the degree of each vertex vr,1≤r≤n is degvr=m.We now illustrate the computation of the topological indices considered in the earlier sections, both directly from the definition and from the formulae in Theorems1, 3, and Remark 1.The Harary index ofKm,n, by direct computation from the definition, is(19)HKm,n=12mm−1×12+12nn−1×12+mn=14m2+n2+−m−n+4mn.The same value is obtained from the formula for the Harary index, namely,HGw=1/123wawa−1+3wbwb−1+8wab+4wawb, since wa=m,wb=n,wab=mn.The eccentric connectivity index ofKm,n, by direct computation from the definition, is(20)ζcKm,n=m×2n+n×2m=4mn.The same value is obtained from the formula for the eccentric connectivity index, namely,ζcGw=6wab−kwa−n1wb where k is the number of b’s succeeding the last a and n1 is the number of a’s prior to the first b in Gw, so that k=n,n1=m.The total eccentricity index ofKm,n, by direct computation from the definition, is(21)ζKm,n=m×2+n×2=2m+2n.The same value is obtained from the formula for the total eccentricity index, namely,ζGw=3w−k−n1, where w=wa+wb=m+n.The eccentric connectivity coindex ofKm,n, by direct computation (using the modified expression for the eccentric connectivity coindex given in the proof of Theorem 6), is(22)ζc¯Km,n=N−1∑u∈VKm,nϵu−ζcKm,n,where N is the number of vertices in the graph Km,n, so that(23)ζc¯Km,n=m+n−1m+n×2−4mn=2m2+n2−m−n.The same value is obtained from the formula for the eccentric connectivity coindex, namely,(24)ζc¯Gw=w−13w−n1−k−6wab+kwa+n1wb=m+n−13m+n−m−n−6mn+nm+mn=2m2+n2−m−n.


## 5. Conclusion

The distance-based topological indices considered in this study have been extensively investigated by researchers for different classes of graphs, and so we were motivated to study these indices for a recently introduced special class of graphs, called PWRGs. An advantage of this study is that this provides a link between two different areas of research, namely, word combinatorics and graph theory. Specifically, we have obtained expressions for evaluating certain distance-based topological indices for PWRGs [14] of binary core words and established bounds on their values when the vertex set is fixed. It will be of interest to study bounds on these indices when the number of edges is fixed.



---

*Source: 5567663-2021-05-25.xml*