ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 20 (2021) 243–260
https://doi.org/10.26493/1855-3974.2359.a7b
(Also available at http://amc-journal.eu)
Wiener-type indices of Parikh word
representable graphs*
Nobin Thomas
Research scholar, APJ Abdul Kalam Technological University,
Thiruvananthapuram, Kerala 695 016 India, and
Amal Jyothi College of Engineering, Kanjirappally, Kerala 686 518 India
Lisa Mathew
Amal Jyothi College of Engineering, Kanjirappally, Kerala 686 518 India
Sastha Sriram
Department of Mathematics, School of Arts, Science and Humanities,
SASTRA Deemed University, Tanjore, Tamil Nadu 613 401 India
K. G. Subramanian †
School of Mathematics, Computer Science and Engineering,
Liverpool Hope University, Liverpool L16 9JD, United Kingdom
Received 10 June 2020, accepted 14 February 2021, published online 9 November 2021
Abstract
A new class of graphs G(w), called Parikh word representable graphs (PWRG), corre-
sponding to words w that are finite sequence of symbols, was considered in the recent past.
Several properties of these graphs have been established. In this paper, we consider these
graphs corresponding to binary core words of the form aub over a binary alphabet {a, b}.
We derive formulas for computing the Wiener index of the PWRG of a binary core word.
Sharp bounds are established on the value of this index in terms of different parameters
related to binary words over {a, b} and the corresponding PWRGs. Certain other Wiener-
type indices that are variants of Wiener index are also considered. Formulas for computing
these indices in the case of PWRG of a binary core word are obtained.
Keywords: Graphs, words, Parikh matrix, Parikh word representable graphs.
Math. Subj. Class. (2020): 68R10, 68R15
*The authors would like to thank the reviewers for their very useful comments which enabled them to revise
the paper improving the presentation of the paper.
†Honorary Visiting Professor.
E-mail addresses: nobinvazhayil@gmail.com (Nobin Thomas), lisamathew@amaljyothi.ac.in (Lisa
Mathew), sriram.discrete@gmail.com (Sastha Sriram), kgsmani1948@gmail.com (K. G. Subramanian)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
244 Ars Math. Contemp. 20 (2021) 243–260
1 Introduction
While words that are finite sequences of symbols are the fundamental and central objects in
computing models developed in theoretical studies of computer science, graphs are mathe-
matical models of pairwise relations between objects found useful for analyzing and solv-
ing different kinds of problems. An interesting area of investigation is relating graphs and
words and there are many studies in this direction (see, for example, [7, 10, 15, 18, 19, 24]).
On the other hand, in the study of numerical quantities related to subwords (also called
scattered subwords) of a word, the notion of Parikh matrix of a word over an ordered
alphabet was introduced in [26]. This has opened up a new direction of research in the area
of combinatorics on words [23] and many problems on words and subwords have been
investigated (see, for example, [1, 2, 4, 25, 33, 34, 36, 37, 38] and references therein),
resulting in a number of interesting results. Parikh word representable graph (PWRG) is
one such notion introduced in [3] linking the two areas of study on properties of words and
of graphs. Based on the notions of subwords of a word and the Parikh matrix of a word
[26] with entries of the matrix giving the counts of certain subwords in the word, PWRG
related to a word was introduced in [3]. Relationship of these graphs with corresponding
words and partitions was recently studied in [27].
In the field of chemical graph theory [14], undirected graphs, referred to as molecular
graphs are considered providing graph representations of organic compounds or equiva-
lently their molecular structures with atoms other than hydrogen often represented by ver-
tices 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 has been a great interest in various topological indices associ-
ated with graphs due to their application in the area of chemical graph theory [8]. There are
a number of studies (see, for example, [14]) of various topological indices of graphs estab-
lishing formulae for computing the indices and also providing upper and lower bounds on
the values of such indices. The Wiener index (also called Wiener number) [40] is the first
topological index introduced by Harold Wiener. Knor et al. [22] provide an excellent sum-
mary of results relating to Wiener index besides providing conjectures and problems on this
index. Wiener index and its variants for different classes of graphs are widely investigated
indices (see, for example, [9, 12, 14, 21, 28, 29, 39] and references therein).
In this paper we study the Wiener index of a PWRG of a binary core word and derive
formulas for computing this index besides establishing sharp bounds on their values, given
different parameters related to the graphs. We also obtain formulas for evaluating certain
other indices that are variants of Wiener index, such as multiplicative Wiener index [13],
terminal Wiener index [11], peripheral Wiener index [16], hyper-Wiener index [20, 30] in
the case of a PWRG of a binary core word.
2 Preliminaries
The basic notions and notations relating to words and subwords can be found in [23,
31]. We recall some essential concepts and results. An ordered alphabet Σ which is
a set of symbols {a1, a2, . . . , as} with an ordering < on its symbols is written as Σ =
{a1 < a2 < · · · < as} . A word v is a subword of a word w over Σ if and only if we can
find words x1, x2, . . . , xn, y0, y1, . . . , yn over Σ, some of them possibly empty, such that
w = y0x1y1x2y2 · · · yn−1xnyn and v = x1x2 · · ·xn. The number of occurrences of a
word u as a subword of w is denoted by |w|u. For example, in the word w = aababaaab =
N. Thomas et al.: Wiener-type indices of Parikh word representable graphs 245
a2baba3b over the ordered binary alphabet Σ = {a < b}, the number of distinct occur-
rences of the subword ab is 11 so that |w|ab = 11. The set of all words over an alphabet Σ,
including the empty word λ with no symbols, is denoted by Σ∗.
Definition 2.1 ([6]). A binary word w over an alphabet {a, b} is said to be fair if
|w|ab = |w|ba.
Example 2.2. The binary word abbbaab is a fair word since |w|ab = |w|ba = 6.
Definition 2.3 ([38]). Consider the binary word w ∈ Σ∗ where Σ = {a < b}. The core of
w, denoted by core(w), is the unique word w0 of w with the smallest possible length such
that w ∈ b∗w0a∗. A word w ∈ Σ∗ is said to be a core word if and only if core(w) = w.
Clearly, a non empty word w over Σ = {a < b} is a core word if and only if w starts
with a and ends with b.
We now recall the relationship between binary core words and partitions following the
discussion in [38, pages 62–63].
Lemma 2.4 ([38]). Every nonempty binary core word can be identified with a partition of
a positive integer.
Proof. Suppose w ∈ Σ∗ is a nonempty core word and has the form an1ban2b · · · an|w|b b
where n1 ≥ 1 and nk is nonnegative for each k, 2 ≤ k ≤ |w|b. Thus w can be identified
with the partition
|w|ab = (n1 + n2 + · · ·+ n|w|b) + · · ·+ (n2 + n1) + n1.
Clearly, distinct core words are identified with distinct partitions.
Conversely, suppose that m1 +m2 + · · · +ml is a partition of some positive integer,
where m1 ≥ m2 ≥ · · · ≥ ml ≥ 1. It is clear that the word
w = amlbaml−1−mlbaml−2−ml−1b · · · am1−m2b
can be identified with the given partition.
We shall use the notation p(w) = (n1+n2+ · · ·+nl)+(n1+n2+ · · ·+nl−1)+ · · ·+
(n1 +n2 + · · ·+nl−i+1) + · · ·+ (n1 +n2) + (n1) to indicate the partition corresponding
to the word w = an1ban2b · · · anlb.
We now recall the notion of Parikh word representable graph (PWRG) [3]. For basic
concepts pertaining to graphs we refer to [5].
Definition 2.5 ([3]). For a word w = a1a2 · · · an of length n where for 1 ≤ i ≤ n,
ai ∈ Σ = {a < b}, we associate a simple graph G = G(w) with n vertices {1, 2, . . . , n}.
Each vertex i has the label ai and represents the position of the letter ai, 1 ≤ i ≤ n, in w.
For each occurrence of the subword ab in w, there is an edge in G(w) joining the vertices
corresponding to the positions of a and b in w. We say that the graph G is Parikh binary
word representable by the binary word w. In other words, we say that a graph G is Parikh
binary word representable if there exists a binary word w such that G is Parikh binary word
representable by the binary word w.
246 Ars Math. Contemp. 20 (2021) 243–260
Since every connected Parikh binary word representable graph corresponds to a core
word, we deal with only core words and the corresponding graphs in the rest of this paper.
As an illustration, if the core word is w = aabab, then in the Parikh word representable
graph as shown in Figure 1, the vertices 1, 2 and 4 have label a while the vertices 3 and 5
have the label b. The number of edges in the graph is |w|ab = 5. For example there is a
subword ab in w formed by the symbol a in position 1 and the symbol b in position 3 and
so in the graph there is an edge joining the vertex 1 with the vertex 3.
3
1 42
5
G(aabab)
Figure 1: The Parikh word representable graph of the word aabab.
3 Wiener index of Parikh word representable graphs
Let G = (V,E) be a connected graph with vertex set V (G) and edge set E(G). The
distance between the vertices u and v of G is denoted by d(u, v) and is defined as the
length of a shortest path between u and v in G.
Definition 3.1. The Wiener index W (G) of a connected graph G = (V,E), is the sum of
distances d(u, v) between all the vertices u and v of G. In other words
W (G) =
∑
{u,v}⊆V (G)
d(u, v).
We now obtain a formula for computing the Wiener index of Parikh word representable
graph of a binary word.
Theorem 3.2. The Wiener index of a Parikh word representable graph G(w) for w =
an1ban2b · · · anlb, n1 ≥ 1, nk ≥ 0 for 2 ≤ k ≤ l, is
W (G(w)) =
(
l∑
i=1
ni
)2
+
l∑
i=1
(l + 2i− 3)ni + l(l − 1).
Proof. In the Parikh word representable graph G(w) corresponding to the word w =
an1ban2b · · · anlb, we consider pairs of vertices (u, v), 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:
(i) u and v are both labeled a;
(ii) u is labeled a and v is labeled b;
(iii) u is labeled b and v is labeled a;
N. Thomas et al.: Wiener-type indices of Parikh word representable graphs 247
(iv) u and v are both labeled b.
The contribution to the Wiener index of the Parikh word representable graph from each of
these four cases may be calculated as follows:
(i) The distance between any two vertices labeled a is 2 and there are n1+n2+ · · ·+nl
vertices labeled a. Hence the total contribution from these pairs of vertices is
(n1 + n2 + · · ·+ nl)C2 × 2 = (n1 + n2 + · · ·+ nl)2 − (n1 + n2 + · · ·+ nl).
(ii) The distance between u labeled a and v labeled b is 1 and there are n1+(n1+n2)+
· · ·+ (n1 + n2 + · · ·+ nl) such pairs. Hence the total contribution is
n1 + (n1 + n2) + · · ·+ (n1 + n2 + · · ·+ nl) = ln1 + (l − 1)n2 + · · ·+ nl.
(iii) The distance between u labeled b and v labeled a is 3 and there are (n2 +n3 + · · ·+
nl) + (n3 + · · · + nl) + · · · + nl = n2 + 2n3 + · · · + (l − 1)nl such pairs. Hence
the total contribution is
3(n2 + 2n3 + · · ·+ (l − 1)nl).
(iv) The distance between any two vertices labeled b is 2 and there are l vertices labeled
b. Hence the total contribution from these pairs of vertices is
lC2 × 2 = l(l − 1).
Hence the Wiener index of G(w) is given by
W (G(w)) = (n1 + n2 + · · ·+ nl)2 + (l − 1)n1 + (l + 1)n2 + · · ·
+ 3(l − 1)nl + l(l − 1)
=
(
l∑
i=1
ni
)2
+
l∑
i=1
(l + 2i− 3)ni + l(l − 1).
Example 3.3. For the PWRG in Figure 1 corresponding to the word w = a2bab, we have
l = 2, n1 = 2, n2 = 1 and so W (G(w)) = 16 which can also be verified from the formula
in the Definition 3.1 by actually computing the distances d(u, v) for all unordered pairs
(u, v) of vertices.
We now derive an alternate form of the expression for the Wiener index of the Parikh
word representable graph G(w) for w = an1ban2b · · · anlb, n1 ≥ 1, nk ≥ 0 for 2 ≤ k ≤ l.
An interesting aspect of this alternate form is that the expression in the formula is elegant
involving only the parameters related to the word.
Theorem 3.4. The Wiener index of a Parikh word representable graph G(w), for w =
an1ban2b · · · anlb, n1 ≥ 1, nk ≥ 0 for 2 ≤ k ≤ l, is
W (G(w)) = |w|2 − |w|+ |w|a|w|b − 2|w|ab.
248 Ars Math. Contemp. 20 (2021) 243–260
Proof. Since w = an1ban2b · · · anlb, we have
∑l
i=1 ni = |w|a, l = |w|b. Also
|w|a|w|b − |w|ab = l
(
l∑
i=1
ni
)
− [(n1 + n2 + · · ·+ nl) + · · ·+ (n1 + n2) + n1]
=
l∑
i=1
ini − |w|a
so that
l∑
i=1
ini = |w|a|w|b + |w|a − |w|ab.
Hence from Theorem 3.2, the Wiener index
W (G(w)) = |w|2a + (|w|b − 3)|w|a + |w|b(|w|b − 1) + 2
l∑
i=1
ini
= |w|2a + |w|2b + 3|w|a|w|b − |w|a − |w|b − 2|w|ab
= |w|2 − |w|+ |w|a|w|b − 2|w|ab
using |w| = |w|a + |w|b.
Corollary 3.5. The Wiener index of a Parikh word representable graph G(w) for a fair
word w = an1ban2b · · · anlb, n1 ≥ 1, nk ≥ 0 for 2 ≤ k ≤ l, is
W (G(w)) = |w|2 − |w|.
Proof. For a binary word w, we have |w|ab + |w|ba = |w|a|w|b. Since w is a fair word,
|w|ab = |w|ba so that |w|a|w|b − 2|w|ab = |w|ba − |w|ab = 0. Hence from Theorem 3.4,
W (G(w)) = |w|2 − |w|.
Theorem 3.6. The Wiener index W (G(w)) of a Parikh word representable graph G(w) =
(V1 ∪ V2, E) with |V1| = |w|a = p, |V2| = |w|b = q for the word w = an1ban2b · · · anqb,
n1 ≥ 1, nk ≥ 0 for 2 ≤ k ≤ l, is bounded above by p2 + q2 + 3pq − 3p − 3q + 2 and
below by p2 + q2 + pq − p− q. The bounds are attained on G(abq−1ap−1b) and G(apbq)
respectively.
Proof. Since G(w) is connected, |w|ab = |E| ≥ p + q − 1 [5]. Also |w|ab ≤ pq [26].
Hence from Theorem 3.4, the Wiener index of G(w) is
W (G(w)) = p2 + q2 + 3pq − p− q − 2|w|ab
≤ p2 + q2 + 3pq − p− q − 2(p+ q − 1) = p2 + q2 + 3pq − 3p− 3q + 2
which is the Wiener index of the Parikh word representable graph G(abq−1ap−1b) and
W (G(w)) ≥ p2 + q2 + 3pq − p− q − 2pq = p2 + q2 + pq − p− q
which is the Wiener index of the Parikh word representable graph G(apbq).
N. Thomas et al.: Wiener-type indices of Parikh word representable graphs 249
Remark 3.7. One of the conjectures listed in [22, page 333], states that for a graph G
with diameter d and order 2d + 1, the Wiener index W (G) ≤ W (C2d+1) where C2d+1
denotes a cycle of length 2d+ 1. Since the diameter of any PWRG G(w) corresponding to
the binary core word w is 3, this conjecture holds good for G(w), if the order of G(w) is 7,
which also equals |w|. In fact, if the binary core word w with |w| = 7, is over the ordered
alphabet {a < b}, the maximum Wiener index of G(w) equals W (C7) which is 42 and this
is attained, by Theorem 3.6, on G(ab3a2b) or G(ab2a3b).
We shall now find an expression for an upper bound on the Wiener index of Parikh
word representable graph with a fixed number of edges. We use the following lemma.
Lemma 3.8. Given a fixed value of e and of l, the maximum value of W (G(w)) over all
Parikh word representable graphs of the form G(w) for w = an1ban2b · · · anlb, n1 ≥ 1,
nk ≥ 0 for 2 ≤ k ≤ l, with e edges, is attained on G(abl−1ae−lb).
Proof. Since the number of edges in G(w) is e = |w|ab, |w|b = l and e ≥ |w|a + |w|b − 1
as G(w) is a connected graph with |w|a + |w|b vertices, we have |w|a ≤ e− l + 1. Hence
from Theorem 3.4, the Wiener index of G(w) is
W (G(w)) = |w|a(|w|a − 1) + l2 + 3|w|al − l − 2e
≤ (e− l + 1)(e− l) + l2 + 3|w|al − l − 2e
≤ (e− l + 1)(e− l) + l2 + 3(e− l + 1)l − l − 2e = e2 − l2 + el + l − e
which is the Wiener index of the Parikh word representable graph G(abl−1ae−lb).
Theorem 3.9. An upper bound of the Wiener index W (G(w)) of a Parikh word repre-
sentable graph G(w), w = an1ban2b · · · anlb, n1 ≥ 1, nk ≥ 0 for 2 ≤ k ≤ l, with e edges
is given by
W (G(w)) ≤
{
5m2 − 6m+ 2(m ≥ 1), if e = 2m− 1;
5m2 −m(m ≥ 1), if e = 2m.
The bound is sharp and is attained on G(abm−1am−1b) when e = 2m − 1 and on
G(abm−1amb) when e = 2m.
Proof. From Lemma 3.8, the Wiener index of the Parikh word representable graph G(w),
w = an1ban2b · · · anlb, n1 ≥ 1, has a maximum for G(abl−1ae−lb) and is given by
W (G(w)) = e2 − l2 + el + l − e. We now use the fact that a quadratic expression
ax2 + bx + c, a < 0, has a maximum when x = − b2a . When e = 2m − 1,m ≥ 1,
we have
W (G(w)) = −l2 + 2ml + (4m2 − 6m+ 2).
If e = 2m− 1 has a fixed value, this quadratic expression in l has a maximum when l = m
and the maximum is 5m2 − 6m+ 2. When e = 2m,m ≥ 1, we have
W (G(w)) = −l2 + l(1 + 2m) + (4m2 − 2m).
Again if e = 2m has a fixed value, this quadratic expression has a maximum when l =
[m+ 12 ] = m where [x] is the integral part of x and the maximum is 5m
2 + 2m.
We shall now evaluate the Wiener index of a Parikh word representable graph corre-
sponding to a specific partition of a given integer.
250 Ars Math. Contemp. 20 (2021) 243–260
Theorem 3.10. Suppose m1+m2+ · · ·+ml is a partition of some positive integer, where
m1 ≥ m2 ≥ · · · ≥ ml ≥ 1. Then the Wiener index of the Parikh word representable graph
G corresponding to this partition is given by
W (G) = m21 − 2e+ (3l − 1)m1 + l(l − 1)
where e is the number of edges of G.
Proof. From Lemma 2.4, the word w = amlbaml−1−mlbaml−2−ml−1b · · · am1−m2b corre-
sponds to the given partition. Now |w| = m1 + l, |w|a = m1, |w|b = l, so that using the
formula in Theorem 3.4, we have
W (G) = W (G(w)) = |w|2 − |w|+ |w|a|w|b − 2|w|ab
= (m1 + l)
2 − (m1 + l) + lm1 − 2e = m21 − 2e+ (3l − 1)m1 + l(l − 1)
since |w|ab = e.
4 Multiplicative Wiener index
Definition 4.1 ([32]). The Wiener polynomial of a graph G is
W (G;x) =
∑
{u,v}⊆V (G)
xd(u,v).
Theorem 4.2. The Wiener polynomial of a Parikh word representable graph G(w), for
w = an1ban2b · · · anlb, n1 ≥ 1, nk ≥ 0 for 2 ≤ k ≤ l, is
W (G(w);x) = (|w|a|w|b−|w|ab)x3+
1
2
(
|w|a(|w|a−1)+ |w|b(|w|b−1)
)
x2+(|w|ab)x.
Proof. We consider pairs of vertices (u, v) in the Parikh word representable graph 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. As discussed in the proof of Theorem 3.2, the
vertex pairs are of four types, namely, types 1, 2, 3 and 4. Also, as discussed in the proof
of Theorem 3.4, there are 12 |w|a(|w|a − 1) pairs of vertices of type 1 and
1
2 |w|b(|w|b − 1)
of type 4 and the distance between each such pair is 2. Likewise, there are |w|ab pairs of
vertices of type 2 with distance 1 and |w|a|w|b − |w|ab pairs of vertices of type 3 with
distance 3. Hence the Wiener polynomial is
(|w|a|w|b − |w|ab)x3 +
1
2
(
|w|a(|w|a − 1) + |w|b(|w|b − 1)
)
x2 + (s|w|ab)x.
Definition 4.3 ([40]). The Wiener polarity index of G, denoted by Wp(G), is defined as
Wp(G) = |{(u, v) ⊆ V (G) : d(u, v) = 3}|.
Theorem 4.4. The Wiener polarity index of a Parikh word representable graph G(w), for
w = an1ban2b · · · anlb, n1 ≥ 1, nk ≥ 0 for 2 ≤ k ≤ l, is given by
Wp(G(w)) = |w|a|w|b − |w|ab.
N. Thomas et al.: Wiener-type indices of Parikh word representable graphs 251
Proof. In the Parikh word representable graph G(w), for the word w = an1ban2b · · · anlb
as in the hypothesis, the pairs of vertices (u, v) of type 3 as mentioned in the proof of
Theorem 4.2, are at a distance 3 and these pairs contribute to the Wiener polarity index of
G(w). In fact there are n2 + n3 + · · ·+ nl vertices with label a that are at distance 3 from
the vertex with label, the first b in w. Likewise for other vertices corresponding to the other
b′s in w. Hence
Wp(G(w)) = (n2 + n3 + · · ·+ nl) + (n3 + n4 + · · ·+ nl) + · · ·+ nl
=
l∑
i=1
ini −
l∑
i=1
ni = w|a|w|b − |w|ab.
Definition 4.5 ([13]). The multiplicative version of the Wiener index of a graph G is
π(G) =
∏
{u,v}⊆V (G)
d(u, v).
Theorem 4.6. The multiplicative Wiener index of a Parikh word representable graph G(w),
for w = an1ban2b · · · anlb, n1 ≥ 1, nk ≥ 0 for 2 ≤ k ≤ l, is
π(G(w)) = 2
|w|a(|w|a−1)+|w|b(|w|b−1)
2 3|w|a|w|b−|w|ab .
Proof. Considering pairs of vertices as in Theorem 4.2, we obtain the required result, since
there are |w|a(|w|a−1)+|w|b(|w|b−1)2 pairs of vertices at distance 2 in G(w) while there are
|w|a|w|b − |w|ab pairs of vertices at distance 3. It is to be noted that pairs of vertices at
distance 1 contribute value 1 to the product defining π(G(w)).
Corollary 4.7. The multiplicative Wiener index of a Parikh word representable graph
G(w) for a fair word w = an1ban2b · · · anlb, n1 ≥ 1, nk ≥ 0 for 2 ≤ k ≤ l, is
π(G(w)) = 2
|w|2−|w|
2
(
3
2
)|w|ab .
Proof. For a binary word w, we have |w|ab + |w|ba = |w|a|w|b. Since w is a fair word,
|w|ab = |w|ba so that |w|a|w|b − 2|w|ab = |w|ba − |w|ab = 0. Also |w| = |w|a + |w|b.
Hence from Theorem 4.6, π(G(w)) = 2
|w|2−|w|
2
(
3
2
)|w|ab .
Lemma 4.8. Given a fixed value of e and of l, the maximum value of π(G(w)) over all
Parikh word representable graphs of the form G(w) for w = an1ban2b · · · anlb, n1 ≥ 1,
nk ≥ 0 for 2 ≤ k ≤ l, with e edges, is attained on G(abl−1ae−lb).
Proof. Since |w|b = l and the number of edges in G(w) is e = |w|ab, we have |w|a ≤
e− l+1 as G(w) is a connected graph with |w|a+ |w|b vertices so that e ≥ |w|a+ |w|b−1.
Note that in a connected graph G with n vertices and e edges, e ≥ n− 1 [5]. Hence from
Theorem 4.6, the multiplicative Wiener index of G(w) is
π(G(w)) = 2
|w|a(|w|a−1)+|w|b(|w|b−1)
2 3|w|a|w|b−|w|ab
≤ 2
(e−l+1)(e−l)+l(l−1)
2 3(e−l+1)l−e
which is the multiplicative Wiener index of the Parikh word representable graph
G(abl−1 ae−lb).
252 Ars Math. Contemp. 20 (2021) 243–260
Theorem 4.9. An upper bound of the multiplicative Wiener index π(G(w)) of a Parikh
word representable graph G(w), w = an1ban2b · · · anlb, n1 ≥ 1, nk ≥ 0 for 2 ≤ k ≤ l,
with e edges is given by
π(G(w)) ≤
{
2m
2−m3m
2−2m+1(m ≥ 1), if e = 2m− 1;
2m
2
3m
2−m(m ≥ 1), if e = 2m.
The bound is sharp and is attained on G(abm−1am−1b) when e = 2m − 1 and on
G(abm−1amb) when e = 2m.
Proof. From Lemma 4.8, the multiplicative Wiener index of the Parikh word representable
graph G(w), w = an1ban2b · · · anlb, n1 ≥ 1, has a maximum for G(abl−1ae−lb) and is
given by
π(G(w)) = 2
(e−l+1)(e−l)+l(l−1)
2 3(e−l+1)l−e.
On taking logarithms we get,
ln(π(G(w))) = [(e− l + 1)(e− l) + l2 − l] ln 2
2
+ [(e− l + 1)l − e] ln 3
= l2(ln 2− ln 3)− l((e+ 1)(ln 2− ln 3) + e
(
(e+ 1)
2
ln 2− ln 3
)
.
We now use the fact that a quadratic expression ax2+ bx+ c, a < 0, has a maximum when
x = − b2a . Let F (l) = l
2(ln 2− ln 3)− l((e+1)(ln 2− ln 3)+ e( (e+1)2 ln 2− ln 3). When
e = 2m− 1,m ≥ 1, F (l) has a maximum when l = m and so π(G(w)) has the maximum
2m
2−m3m
2−2m+1. When e = 2m,m ≥ 1, F (l) has a maximum when l = [m + 12 ] = m
where [x] is the integral part of x and π(G(w)) has the maximum 2m
2
3m
2−m.
Theorem 4.10. The multiplicative Wiener index π(G(w)) of a Parikh word representable
graph G(w) = (V1 ∪ V2, E) with |V1| = |w|a = p, |V2| = |w|b = q for the word
w = an1ban2b · · · anqb, n1 ≥ 1, nk ≥ 0 for 2 ≤ k ≤ l, is bounded above by
2
p(p−1)+q(q−1)
2 3pq−p−q+1
and below by
2
p(p−1)+q(q−1)
2 .
The bounds are attained on G(abq−1ap−1b) and G(apbq) respectively.
Proof. Since G(w) is connected, |w|ab = |E| ≥ p + q − 1 [5]. Also |w|ab ≤ pq [26].
Hence from Theorem 4.6, the multiplicative Wiener index of G(w) is
π(G(w)) ≥ 2
p(p−1)+q(q−1)
2
which is the multiplicative Wiener index of the Parikh word representable graph G(apbq)
and
π(G(w)) ≤ 2
p(p−1)+q(q−1)
2 3pq−p−q+1
which is the multiplicative Wiener index of the Parikh word representable graph
G(abq−1 ap−1b).
N. Thomas et al.: Wiener-type indices of Parikh word representable graphs 253
5 Hyper-Wiener index of Parikh word representable graphs
We now derive formuas for computing hyper-Wiener index of Parikh word representable
graphs of binary words.
Definition 5.1 ([20, 30]). The hyper-Wiener index of a connected graph G is given by
WW (G) =
∑
{u,v}⊆V (G)
d(u, v) + d2(u, v)
where d(u, v) is the distance between the vertices u and v of G.
Theorem 5.2. The hyper-Wiener index WW (G(w)) of a Parikh word representable graph
G(w) for w = an1ban2b · · · anlb, n1 ≥ 1, nk ≥ 0 for 2 ≤ k ≤ l, is
WW (G(w)) = 3
(
l∑
i=1
ni
)2
+
l∑
i=1
(2l + 10i− 13)ni + 3l(l − 1).
Proof. As in the proof of Theorem 3.2, there are four cases for the vertex pairs (u, v). The
contribution to the hyper-Wiener index of the Parikh word representable graph from each
of these cases may be calculated as follows:
(i) The contribution from pairs of vertices labeled a is
(n1+n2+ · · ·+nl)C2× (2+4) = 3(n1+n2+ . . .+nl)2−3(n1+n2+ · · ·+nl).
(ii) The contribution from pairs of vertices (u, v) where u is labeled a and v is labeled
b is
2(n1 + (n1 + n2) + . . .+ (n1 + n2 + . . .+ nl)) = 2(ln1 + (l − 1)n2 + · · ·+ nl).
(iii) The contribution from pairs of vertices (u, v) where u is labeled b and v is labeled
a is
12(n2 + 2n3 + · · ·+ (l − 1)nl)).
(iv) The contribution from pairs of vertices labeled b is
lC2 × 6 = 3l(l − 1).
Hence the hyper-Wiener index of G(w) is given by
WW (G(w) = 3
(
l∑
i=1
ni
)2
+
l∑
i=1
(2l + 10i− 13)ni + 3l(l − 1).
We now derive an alternate form of the expression for the hyper-Wiener index of the
Parikh word representable graph G(w) for w = an1ban2b · · · anlb, n1 ≥ 1, nk ≥ 0 for
2 ≤ k ≤ l.
254 Ars Math. Contemp. 20 (2021) 243–260
Theorem 5.3. The hyper-Wiener index of a Parikh word representable graph G(w) for
w = an1ban2b · · · anlb, n1 ≥ 1, nk ≥ 0 for 2 ≤ k ≤ l, is
WW (G(w)) = 3|w|2a + 3|w|2b + 12|w|a|w|b − 3|w|a − 3|w|b − 10|w|ab
= 3|w|2 − 3|w|+ 6|w|a|w|b − 10|w|ab.
Proof. Since w = an1ban2b · · · anlb, we have
∑l
i=1 ni = |w|a, l = |w|b. Also, as in the
proof of Theorem 3.4,
l∑
i=1
ini = |w|a|w|b + |w|a − |w|ab.
Hence from Theorem 5.2, the hyper-Wiener index
WW (G(w)) = 3|w|2a + (2|w|b − 13)|w|a + 3|w|b(|w|b − 1) + 10
l∑
i=1
ini
= 3|w|2a + 3|w|2b + 12|w|a|w|b − 3|w|a − 3|w|b − 10|w|ab
= 3|w|2 − 3|w|+ 6|w|a|w|b − 10|w|ab
using |w| = |w|a + |w|b.
Theorem 5.4. The hyper-Wiener index of a Parikh word representable graph G(w) =
(V1 ∪ V2, E) with |V1| = |w|a = p, |V2| = |w|b = q for the word w = an1ban2b · · · anqb,
n1 ≥ 1, nk ≥ 0 for 2 ≤ k ≤ l, is bounded above and below by
3(p2 + q2) + 12pq − 13p− 13q + 10
and
3(p2 + q2) + 2pq − 3p− 3q.
The bounds are attained on G(abq−1ap−1b) and G(apbq) respectively.
Proof. As done in the proof of Theorem 3.6, using the inequalities |w|ab ≥ p+ q − 1 [5],
|w|ab ≤ pq [26], we have from Theorem 5.3, the hyper-Wiener index of G(w) is
WW (G(w)) = 3p2 + 3q2 + 12pq − 3p− 3q − 10|w|ab
≤ 3(p2 + q2) + 12pq − 13p− 13q + 10
which is the hyper-Wiener index of the Parikh word representable graph G(abq−1ap−1b)
and
W (G(w)) ≥ 3(p2 + q2) + 2pq − 3p− 3q
which is the Wiener index of the Parikh word representable graph G(apbq).
The hyper-Wiener index of a Parikh word representable graph corresponding to a spe-
cific partition of a given integer can be evaluated proceeding as in the proof of Theorem 3.10
and is given in the following theorem.
N. Thomas et al.: Wiener-type indices of Parikh word representable graphs 255
Theorem 5.5. Suppose m1 +m2 + · · ·+ml is a partition of some positive integer, where
m1 ≥ m2 ≥ · · · ≥ ml ≥ 1. Then the hyper-Wiener index of the Parikh word representable
graph G corresponding to this partition is given by
WW (G) = 3(m21 + (4l − 1)m1 + l(l − 1))− 10e
where e is the number of edges of G.
We shall now find an expression for an upper bound on the hyper-Wiener index of
Parikh word representable graph with a fixed number of edges. We use the following
lemma.
Lemma 5.6. Given a fixed value of e and of l, the maximum value of WW (G(w)) over all
Parikh word representable graphs of the form G(w) for w = an1ban2b · · · anlb, n1 ≥ 1,
nk ≥ 0 for 2 ≤ k ≤ l, with e edges, is attained on G(abl−1ae−lb).
Proof. Proceeding as done in the proof of Lemma 3.8, the number of edges in G(w) is
e = |w|ab, |w|b = l and e ≥ |w|a+ |w|b−1 as G(w) is a connected graph with |w|a+ |w|b
vertices, we have |w|a ≤ e − l + 1. Hence from Theorem 5.3, the hyper-Wiener index of
G(w) is
WW (G(w)) = 3|w|a(|w|a − 1) + 3l2 + 12l|w|a − 3l − 10e
≤ 3(e− l + 1)(e− l) + 3l2 + 12l(e− l + 1)− 3l − 10e
= 3e2 − 6l2 + 6el + 6l − 7e
which is the hyper-Wiener index of the Parikh word representable graph G(abl−1ae−lb).
Theorem 5.7. An upper bound of the Wiener index W (G(w)) of a Parikh word repre-
sentable graph G(w) for w = an1ban2b · · · anlb, n1 ≥ 1, nk ≥ 0 for 2 ≤ k ≤ l, with e
edges is given by
WW (G) ≤
{
18m2 − 26m+ 10(m ≥ 1), if e = 2m− 1;
18m2 − 8m(m ≥ 1), if e = 2m.
The bound is sharp and is attained on G(abm−1am−1b) when e = 2m − 1 and on
G(abm−1amb) when e = 2m.
Proof. From Lemma 5.6, the hyper-Wiener index of the Parikh word representable graph
G(w), w = an1ban2b · · · anlb, n1 ≥ 1, has a maximum for G(w) for w = abl−1ae−lb and
is given by WW (G(w)) = 3e2 − 6l2 + 6el + 6l − 7e. We use the fact that a quadratic
expression ax2+bx+c, a < 0, has a maximum when x = − b2a . When e = 2m−1,m ≥ 1,
we have WW (G(w)) = −6l2 + 12ml + (12m2 − 26m+ 10). If e = 2m− 1 has a fixed
value, this quadratic expression in l has a maximum when l = m and the maximum is
18m2 − 26m + 10. When e = 2m,m ≥ 1, we have WW (G(w)) = −6l2 + l(6 +
12m) + (12m2 − 14m). Again if e = 2m has a fixed value, this quadratic expression has
a maximum when l = [m+ 12 ] = m where [x] is the integral part of x and the maximum is
18m2 − 8m.
256 Ars Math. Contemp. 20 (2021) 243–260
6 Terminal and peripheral Wiener indices
By considering only pendant vertices in a graph, a special kind of Wiener index, called
terminal Wiener index, has been introduced and studied [11]. Here we consider this notion
in the context of Parikh word representable graphs.
Definition 6.1 ([11]). The terminal Wiener index TW (G) of a connected graph G is the
sum of distances between all pairs of pendant vertices of G.
Theorem 6.2. The terminal Wiener index of a Parikh word representable graph G =
G(an1ban2b · · · anlb), n1 ≥ 1, nk ≥ 0 for 2 ≤ k ≤ l, is given by
TW (G) =
{
nl(nl − 1), if n1 ̸= 1;
nl(nl − 1) + k(k − 1) + 3knl, if n1 = 1, for 2 ≤ j ≤ k ≤ l, nj = 0.
Proof. If n1 ̸= 1, the only possible pendant vertices are the a’s in the last block and the
distance between any two of them is 2 so that
TW (G) = 2× nlC2 = nl(nl − 1).
Note that if nl = 0, then TW (G) = 0.
If n1 = 1, n2 = n3 = · · · = nk = 0 and nk+1 ̸= 0, 2 ≤ k < l, l > 1, then the first
k b’s are also a pendant vertices and the distance between any one of these b’s and any one
of the a’s in the last block is 3 while that between any two b’s is 2 as well as the distance
between any two a′s in the last block is 2. Hence
TW (G) = nl(nl − 1) + k(k − 1) + 3knl.
When k = l, then n1 = 1 and ni = 0, 2 ≤ i ≤ l so that all the b′s are the only pendant
vertices and hence
TW (G) = l(l − 1).
If n1 = 1, l = 1, clearly TW (G) = 1 as the corresponding graph G(ab) has only one edge
with the end labels a and b.
Another special kind of Wiener index, called peripheral Wiener index, has also been
studied [16].
Definition 6.3 ([16]). The peripheral Wiener index of a connected graph G is given by
Wp(G) =
∑
{u,v}⊆P (G) d(u, v) where P (G) is the set of all peripheral vertices which are
the vertices of G with their eccentricities equal to diameter of G.
Theorem 6.4. The peripheral Wiener index of the Parikh word representable graph G(w)
for w = an1ban2ban3b · · · anrbl−r+1, n1 ≥ 1, nk ≥ 0 for 2 ≤ k ≤ r − 1, and nr > 0
with r at least 2 and at the most l, is
PW (G(w)) =
(
r∑
i=2
ni
)2
+
r∑
i=2
(r + 2i− 4)ni + (r − 1)(r − 2).
Furthermore PW (G(w)) = W (G(w)) if w = anbl, where W (G(w)) is the Wiener index
of G(w).
N. Thomas et al.: Wiener-type indices of Parikh word representable graphs 257
Proof. From the definition of G(w), the Parikh word representable graph corresponding
to the word w = an1ban2ban3b · · · anrbl−r+1, it is clear that G(w) is a bipartite graph of
diameter 3 and radius 2. Also,the vertices corresponding to all a′s in ani , 2 ≤ i ≤ r and to
all b′s except the last l − r + 1 b′s are of eccentricity 3 and hence they are the peripheral
vertices of G(w). We consider pairs of peripheral vertices (u, v), where the label of u
appears before the label of v in w. As in Theorem 3.2, the vertex pairs of (u, v) can be
divided into four cases as given below:
1. u and v are both labeled a;
2. u is labeled a and v is labeled b;
3. u is labeled b and v is labeled a;
4. u and v are both labeled b.
The contribution to the peripheral Wiener index of the Parikh word representable graph
from each of these cases may be calculated as follows:
1. The contribution from the pairs of peripheral vertices labeled a is
(n2+n3+n4+· · ·+nr)C2×2 = (n2+n3+n4+· · ·+nr)2−(n2+n3+n4+· · ·+nr).
2. The contribution from the pairs of peripheral vertices (u, v) where u is labeled a and
v is labeled b is
n2 + (n2 + n3) + (n2 + n3 + n4) + · · ·+ (n2 + n3 + · · ·+ nr−1)
= (r − 2)n2 + (r − 3)n3 + · · ·+ nr−1.
3. The contribution from the pairs of peripheral vertices (u, v) where u is labeled b and
v is labeled a is
3[(n2 + n3 + · · ·+ nr) + (n3 + n4 + · · ·+ nr) + · · ·+ nr]
= 3[(r − 1)nr + (r − 2)nr−1 + · · ·+ n2].
4. The contribution from the pairs of peripheral vertices labeled b is
(r − 1)C2 × 2 = (r − 1)(r − 2).
Hence the peripheral Wiener index of G(w) is given by
PW (G(w)) =
(
r∑
i=2
ni
)2
+
r∑
i=2
(r + 2i− 4)ni + (r − 1)(r − 2).
Furthermore, if w = anbl then all the vertices of G(w) labeled a as well as b are peripheral
vertices of G(w). Thus PW (G(w)) = W (G(w)) where W (G(w)) is the Wiener index
of G(w).
258 Ars Math. Contemp. 20 (2021) 243–260
7 Conclusion
We have derived formulas for evaluating the Wiener index and certain other variants of
Wiener topological indices for Parikh word representable graphs [3] of binary core words.
There are problems that remain to be investigated. For example, the lower bound of Wiener
index of a Parikh word representable graph G(w) of a binary core word w when the number
of edges of G(w) is a given fixed value, needs to be examined. Bipartite graphs have been
utilized in studies of structural features in the areas of molecular biology and chemistry
(see, for example, [17, 35]). Parikh word representable graphs (PWRG) corresponding to
binary core words are bipartite graphs. It will be of interest to examine the role of PWRG
in such studies of structural features and relationships. Also, it will also be of interest to
study other kinds of topological indices for this class of graphs.
ORCID iDs
Nobin Thomas https://orcid.org/0000-0002-4057-3220
Lisa Mathew https://orcid.org/0000-0002-3722-3326
Sastha Sriram https://orcid.org/0000-0003-0604-2159
K. G. Subramanian https://orcid.org/0000-0001-8726-5850
References
[1] A. Atanasiu, Binary amiable words, Internat. J. Found. Comput. Sci. 18 (2007), 387–400, doi:
10.1142/s0129054107004735.
[2] A. Atanasiu, R. Atanasiu and I. Petre, Parikh matrices and amiable words, Theoret. Comput.
Sci. 390 (2008), 102–109, doi:10.1016/j.tcs.2007.10.022.
[3] S. Bera and K. Mahalingam, Structural properties of word representable graphs, Math. Comput.
Sci. 10 (2016), 209–222, doi:10.1007/s11786-016-0257-1.
[4] S. Bera, K. Mahalingam and K. G. Subramanian, Properties of Parikh matrices of binary words
obtained by an extension of a restricted shuffle operator, Internat. J. Found. Comput. Sci. 29
(2018), 403–413, doi:10.1142/s0129054118500119.
[5] G. Bondy and U. Murty, Graph Theory with Applications, North-Hollans, 1982.
[6] A. Černý, On fair words, J. Autom. Lang. Comb. 14 (2009), 163–174, doi:10.25596/
jalc-2009-163.
[7] A. Collins, S. Kitaev and V. V. Lozin, New results on word-representable graphs, Discrete Appl.
Math. 216 (2017), 136–141, doi:10.1016/j.dam.2014.10.024.
[8] M. V. Diudea, Basic Chemical Graph Theory, in: Multi-shell Polyhedral Clusters, Springer,
Cham, volume 10 of Carbon Materials: Chemistry and Physics, 2018 pp. 1–21, doi:10.1007/
978-3-319-64123-2 1.
[9] M. Eliasi, G. Raeisi and B. Taeri, Wiener index of some graph operations, Discrete Appl. Math.
160 (2012), 1333–1344, doi:10.1016/j.dam.2012.01.014.
[10] A. L. L. Gao, S. Kitaev and P. B. Zhang, On 132-representable graphs, Australas. J. Combin.
69 (2017), 105–118, https://ajc.maths.uq.edu.au/pdf/69/ajc_v69_p105.
pdf.
[11] I. Gutman, B. Furtula and M. Petrović, Terminal Wiener index, J. Math. Chem. 46 (2009),
522–531, doi:10.1007/s10910-008-9476-2.
N. Thomas et al.: Wiener-type indices of Parikh word representable graphs 259
[12] I. Gutman, S. Li and W. Wei, Cacti with n-vertices and t cycles having extremal Wiener index,
Discrete Appl. Math. 232 (2017), 189–200, doi:10.1016/j.dam.2017.07.023.
[13] I. Gutman, W. Linert, I. Lukovits and Ž. Tomović, The multiplicative version of the Wiener
index, J. Chem. Inf. Comput. Sci. 40 (2000), 113–116, doi:10.1021/ci990060s.
[14] I. Gutman and O. E. Polansky, Mathematical Concepts in Organic Chemistry, Springer-Verlag,
Berlin, 1986, doi:10.1007/978-3-642-70982-1.
[15] M. M. Halldórsson, S. Kitaev and A. Pyatkin, Graphs capturing alternations in words, in:
Y. Gao, H. Lu, S. Seki and S. Yu (eds.), Developments in Language Theory, Springer, Berlin,
Heidelberg, volume 6224 of Lecture Notes in Computer Science, 2010 pp. 436–437, doi:
10.1007/978-3-642-14455-4 41, proceedings of the 14th International Conference (DLT 2010)
held at the University of Western Ontario, London, ON, August 17 – 20, 2010.
[16] H. Hua, On the peripheral Wiener index of graphs, Discrete Appl. Math. 258 (2019), 135–142,
doi:10.1016/j.dam.2018.11.031.
[17] P. Iyer and J. Bajorath, Mechanism-based bipartite matching molecular series graphs to iden-
tify structural modifications of receptor ligands that lead to mechanism hopping, Med. Chem.
Commun. 3 (2012), 441–448, doi:10.1039/c2md00281g.
[18] S. Kitaev and V. Lozin, Words and Graphs, Monographs in Theoretical Computer Science, An
EATCS Series, Springer, Cham, 2015, doi:10.1007/978-3-319-25859-1.
[19] S. Kitaev, P. Salimov, C. Severs and H. Ulfarsson, Word-representability of line graphs, Open
J. Discrete Math. 1 (2011), 96–101, doi:10.4236/ojdm.2011.12012.
[20] D. J. Klein, I. Lukovits and I. Gutman, On the definition of the hyper-Wiener index for cycle-
containing structures, J. Chem. Inf. Comput. Sci. 35 (1995), 50–52, doi:10.1021/ci00023a007.
[21] M. Knor and R. Škrekovski, Wiener index of generalized 4-stars and of their quadratic line
graphs, Australas. J. Combin. 58 (2014), 119–126, https://ajc.maths.uq.edu.au/
pdf/58/ajc_v58_p119.pdf.
[22] M. Knor, R. Škrekovski and A. Tepeh, Mathematical aspects of Wiener index, Ars Math. Con-
temp. 11 (2016), 327–352, doi:10.26493/1855-3974.795.ebf.
[23] M. Lothaire, Combinatorics on Words, Cambridge Mathematical Library, Cambridge Univer-
sity Press, Cambridge, 1997, doi:10.1017/cbo9780511566097.
[24] Y. Mandelshtam, On graphs representable by pattern-avoiding words, Discuss. Math. Graph
Theory 39 (2019), 375–389, doi:10.7151/dmgt.2128.
[25] A. Mateescu and A. Salomaa, Matrix indicators for subword occurrences and ambiguity, Inter-
nat. J. Found. Comput. Sci. 15 (2004), 277–292, doi:10.1142/s0129054104002418.
[26] A. Mateescu, A. Salomaa, K. Salomaa and S. Yu, A sharpening of the Parikh mapping, Theor.
Inform. Appl. 35 (2001), 551–564, doi:10.1051/ita:2001131.
[27] L. Mathew, N. Thomas, S. Bera and K. G. Subramanian, Some results on Parikh word repre-
sentable graphs and partitions, Adv. Appl. Math. 107 (2019), 102–115, doi:10.1016/j.aam.2019.
02.009.
[28] K. Pattabiraman and P. Paulraja, Wiener index of the tensor product of a path and a cycle,
Discuss. Math. Graph Theory 31 (2011), 737–751, doi:10.7151/dmgt.1576.
[29] K. Pattabiraman and P. Paulraja, Wiener and vertex PI indices of the strong product of graphs,
Discuss. Math. Graph Theory 32 (2012), 749–769, doi:10.7151/dmgt.1647.
[30] M. Randić, Novel molecular descriptor for structure—property studies, Chem. Phys. Lett. 211
(1993), 478–483, doi:10.1016/0009-2614(93)87094-j.
260 Ars Math. Contemp. 20 (2021) 243–260
[31] G. Rozenberg and A. Salomaa (eds.), Handbook of Formal Languages, Volume 1: Word, Lan-
guage, Grammar, Springer-Verlag, Berlin, 1997, doi:10.1007/978-3-642-59136-5.
[32] B. E. Sagan, Y.-N. Yeh and P. Zhang, The Wiener polynomial of a graph, Int. J. Quantum Chem.
60 (1996), 959–969, doi:10.1002/(sici)1097-461x(1996)60:5⟨959::aid-qua2⟩3.0.co;2-w.
[33] A. Salomaa, Parikh matrices: subword indicators and degrees of ambiguity, in: H.-J.
Böckenhauer, D. Komm and W. Unger (eds.), Adventures Between Lower Bounds and Higher
Altitudes, Springer, Cham, volume 11011 of Lecture Notes in Computer Science, pp. 100–112,
2018, doi:10.1007/978-3-319-98355-4 7.
[34] K. G. Subramanian, A. M. Huey and A. K. Nagar, On Parikh matrices, Internat. J. Found.
Comput. Sci. 20 (2009), 211–219, doi:10.1142/s0129054109006528.
[35] W. R. Taylor, Protein structure comparison using bipartite graph matching and its application
to protein structure classification, Mol. Cell. Proteom. 1 (2002), 334–339, doi:10.1074/mcp.
t200001-mcp200.
[36] W. C. Teh, On core words and the Parikh matrix mapping, Internat. J. Found. Comput. Sci. 26
(2015), 123–142, doi:10.1142/s0129054115500069.
[37] W. C. Teh, Parikh-friendly permutations and uniformly Parikh-friendly words, Australas. J.
Combin. 76 (2020), 208–219, https://ajc.maths.uq.edu.au/pdf/76/ajc_v76_
p208.pdf.
[38] W. C. Teh and K. H. Kwa, Core words and Parikh matrices, Theoret. Comput. Sci. 582 (2015),
60–69, doi:10.1016/j.tcs.2015.03.037.
[39] H. Wang, The extremal values of the Wiener index of a tree with given degree sequence, Dis-
crete Appl. Math. 156 (2008), 2647–2654, doi:10.1016/j.dam.2007.11.005.
[40] H. Wiener, Structural determination of paraffin boiling points, J. Am. Chem. Soc. 69 (1947),
17–20, doi:10.1021/ja01193a005.