/^creative ^commor
ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 17 (2019) 455-466 https://doi.org/10.26493/1855-3974.1925.57a
(Also available at http://amc-journal.eu)
Unicyclic graphs with the maximal value of Graovac-Pisanski index*
Martin Knor
Slovak University of Technology in Bratislava, Faculty of Civil Engineering, Department of Mathematics, Bratislava, Slovakia
Jozef Komornik
Faculty ofManagement, Comenius University, Odbojárov 10, P.O. Box 95, Bratislava, Slovakia
Riste Skrekovski
Faculty of Information Studies, Novo mesto and FMF, University of Ljubljana, Slovenia
Aleksandra Tepeh
Faculty of Information Studies, Novo mesto and Faculty of Electrical Engineering and Computer Science, University ofMaribor, Slovenia
Received 31 January 2019, accepted 13 May 2019, published online 8 November 2019 Abstract
Let G be a graph and let r be its group of automorphisms. Graovac-Pisanski index of G is GP(G) = ^(ffl ^ueV(g) Saer d(u, a(u)), where d(u, v) is the distance from u to v in G. One can observe that GP(G) = 0 if G has no nontrivial automorphisms, but it is not known which graphs attain the maximum value of Graovac-Pisanski index. In this paper we show that among unicyclic graphs on n vertices the n-cycle attains the maximum value of Graovac-Pisanski index.
Keywords: Graovac-Pisanski index, modified Wiener index, unicyclic graphs. Math. Subj. Class.: 05C25
*The first author acknowledges partial support by Slovak research grants VEGA 1/0142/17, VEGA 1/0238/19, APVV-15-0220 and APVV-17-0428. The research was partially supported also by Slovenian research agency ARRS, program no. P1-00383, projects no. L1-4291 and J1-1692.
E-mail addresses: knor@math.sk (Martin Knor), jozef.komornik@fm.uniba.sk (Jozef Komornik), skrekovski@gmail.com (Riste Skrekovski), aleksandra.tepeh@gmail.com (Aleksandra Tepeh)
©® This work is licensed under https://creativecommons.Org/licenses/by/4.0/
456
Ars Math. Contemp. 17(2019)455-466
1 Introduction
Wiener index, the sum of distances in a graph, is an important molecular descriptor. It was introduced by Wiener in 1949, see [18], and since then many other molecular descriptor have appeared. One of them is the Graovac-Pisanski index [8], originally known as the modified Wiener index. With this index an algebraic approach for generalizing the Wiener index was presented. Namely, as the Wiener index also the Graovac-Pisanski index is based on distances but its advantage is in considering also the symmetries of a graph, and it is known that symmetries of a molecule have an influence on its properties [14].
In his pioneering paper, Wiener showed a correlation of the Wiener index of alkanes with their boiling points [18]. It turns out that the Graovac-Pisanski index combines the symmetry and topology of molecules to obtain a good correlation with some physico-chemical properties of molecules. Recently, Crepnjak et al. showed that the Graovac-Pisanski index of some hydrocarbon molecules is correlated with their melting points [6].
This index also drew attention from theoretical point of view. Researchers are interested in the difference between the Wiener and Graovac-Pisanski index. This difference was computed in [9] for some families of polyhedral graphs. The Graovac-Pisanski index of nanostructures was studied in [1, 2, 15, 16, 17] and for some classes of fullerenes and fullerene-like molecules in [3, 11, 12]. In [13] the symmetry groups and Graovac-Pisanski index of some linear polymers were computed. Upper and lower bounds for Graovac-Pisanski index were considered in [11]. In [7] and [16] Graovac-Pisanski index was further considered from computational point of view. Exact formulae for the Graovac-Pisanski index for some graph operations are presented in [4]. Recently it was proved that for any connected bipartite graph, as well as for any connected graph on even number of vertices, the Graovac-Pisanski index is an integer number [5].
Let G be a connected graph. The Graovac-Pisanski index of G is defined as
where Aut(G) is the group of automorphisms of G and distG(u, v) denotes the distance from u to v in G. However, in the paper we will use a result from [5] to compute this index. To explain the method we need some additional definitions. Let G be a graph, u g V(G) and S C V(G). The distance of u in S, wS(u), is defined as
The group of automorphisms of G partitions V(G) into orbits. We say that u, v g V(G) belong to the same orbit if there is an automorphism a g Aut(G) such that a(u) = v. Let V1, V2,..., Vt be all the orbits of Aut(G) in G. Moreover, for every i, 1 < i < t, let vi g Vj. That is, vj's are the representatives of Vj's. It was shown in [5] that
By (1.1), if a graph has no nontrivial automorphisms, that is if all its orbits consist of single vertices, then its Graovac-Pisanski index is 0. Hence, all graphs with no nontrivial automorphisms achieve the minimum value of Graovac-Pisanski index. More interesting is the opposite problem.
(1.1)
i=1
M. Knor et al.: Unicyclic graphs with the maximal value of Graovac-Pisanski index
457
Problem 1.1. Find all graphs on n vertices with the maximum value of Graovac-Pisanski index.
This problem was solved for trees in [10]. By a long H on n vertices we denote a tree obtained from a path on n - 4 vertices by attaching two pendent vertices to each endvertex of the path.
Theorem 1.2. Let T be a tree on n > 8 vertices with the maximum value of Graovac-Pisanski index. Then T is either a path or a long H. Moreover,
GP(T)= {if n isodd In" if n is even.
For n < 7 there are also three other trees with the maximum value of Graovac-Pisanski index. However, they have the value of Graovac-Pisanski index as stated in Theorem 1.2. In this paper we prove the following statement.
Theorem 1.3. Let G be a unicyclic graph on n vertices with the maximum value of Graovac-Pisanski index. Then G is the n-cycle and
GP(C„) = ("r ifn isodd I IT lf n is even.
Observe that Graovac-Pisanski index for extremal trees and for extremal unicyclic graphs has the same value. We believe the following holds.
Conjecture 1.4. Let G be a graph on n vertices, n > 8, with the maximum value of Graovac-Pisanski index. Then G is either a path, or a long H, or a cycle.
To support this conjecture we performed some computer experiments. They showed the validity of the conjecture for n = 8 and n = 9. We believe that the maximal degree of extremal graphs is small (at most 3), thus for the cases n = 10 and n =11 we limited our computer search to maximal degrees 5 and 4, respectively, and in these cases the conjecture was confirmed as well. The graphs from the conjecture are extremal also for n G {5, 6,7}, however when n equals 7 there exists an additional extremal graph.
2 Proof
In this section we prove several claims which imply Theorem 1.3. Obviously, if we consider graphs of order n, we do not need to consider the multiplicative term " in (1.1). Therefore we define
t
GPa(G) = ^ wVi (v.),	(2.1)
i=i
where Vi, V2,..., Vt are all the orbits of Aut(G) in G and vi, v2,..., vt are their representatives, respectively. Then for given n, graphs on n vertices with the maximum value of GPa are the solutions of Problem 1.1.
For a cycle on n vertices, GPa(Cn) = wV(v) where v is an arbitrary vertex of Cn and V = V (Cn). This implies the following statement.
458	Ars Math. Contemp. 17 (2019) 349-368
Proposition 2.1. We have
GPa(C„) = TP" f n -odd, I — if n is even.
In what follows we generalize the GPa-parameter. Let Z = {Z",..., Ztz } be a partition of V(G) and let z G Z,, 1 < i < tZ. Then
tz
GPaZ (G) = ^ wZi (zi).
i=l
In our proofs, sets Z, will usually be unions of orbits of Aut(G). Nevertheless, GPaZ(G) will depend on the choice of the representatives z,.
To prove Theorem 1.3 we start with GPa(G), where G is an extremal unicyclic graph on n vertices different from the n-cycle. Then in a sequence of steps we modify either the graph or the partition and in each step we obtain a larger value of GPaZ. Since we terminate this process with Cn and GPa, we get the result.
Hence, let G be a unicyclic graph on n vertices with the maximum value of Graovac-Pisanski index and such that G is not the n-cycle. Then G consists of a single cycle C and trees rooted at the vertices of the cycle. In what follows, orbits of vertices of C will be important.
We start with modifying the partition by merging together some orbits of vertices which have the same distance from C. We denote by X the new partition of V(G), while the original partition into orbits is denoted by V. Let v be a vertex of C. If {v} is a trivial orbit of Aut(G), then orbits in the v-rooted tree form sets of the partition X. But if {v} is not a trivial orbit of Aut(G), we do the following. Let Ov be the orbit of Aut(G) containig v and let Ov (G) be the set of vertices of u-rooted trees where u G Ov. We partition the vertices of Ov(G) according to their distance from C. Hence, Ov alone is one set of X, another set of X contains those vertices of Ov (G) which are adjacent to a vertex of C, etc. We have the following statement.
Lemma 2.2. For arbitrary choice of the representatives of sets in X we have
GPa(G) < GPaX(G).
Proof. Let X, be a set from X and let x, be an abitrary vertex of X,. Observe that X, is a union of several orbits of Aut(G). Let V0 be an orbit of Aut(G) such that V0 C X,. Then wVo (u) is the same for every u g V0. So let v0 be a vertex of V0 at the shortest distance from xj. Then both x, and v0 are in the same tree rooted at a vertex of C. Assume that they are in a v-rooted tree T.
Let u be a vertex of V0. If u is not in T then distG(xj,u) = distG(v0,u) since distG(xj, v) = distG(v0, v). So let u be a vertex in T. Let z be a vertex on the (unique) (v0, u)-path at the shortest distance from v. Since v0 is a vertex of V0 at the shortest distance from x,, the shortest (x,, u)-path must contain z. Thus distG(v0, u) < distG(x,, u) and so wVo (v0) < wVo (x,). Consequently, GPa(G) < GPaX(G) as required.	□
Now we modify the graph G, and we consider a partition Y of the vertex set of the modified graph inherited from the partition X of G. So let v be a vertex of C. If {v} is a
M. Knor et al.: Unicyclic graphs with the maximal value of Graovac-Pisanski index
459
trivial orbit of Aut(G) then we do not change the v-rooted tree, and its orbits form sets of the partition Y. Hence, in this case the sets of Y coincide with the sets of X (and also with the orbits of V). But if {v} is not a trivial orbit of Aut(G) then we change the v-rooted tree. If the v-rooted tree has p vertices in G then we replace it by a path on p vertices rooted at the endvertex, which we again denote by v. Denote by F the graph which results when all these replacements are made. Since we did not change the cycle, we denote the cycle of F again by C. Let Ov be the orbit of Aut(G) containing v. By our assumption |Ov | > 2. Analogously as above, let Ov (F) be the set of vertices of u-rooted trees where u e Ov. Partition Ov (F) into p disjoint sets of Y according to their distance from C.
Observe that for every Y e Y and for every two vertices y1, y? e Y we have wYi(y1) = (y2). Hence when computing GPaY(F), we can choose the representatives yi in Y arbitrarily. However, orbits of F may be strictly larger than the sets Y. This is caused by the fact that two non-isomorphic rooted trees may have the same numbers of vertices. Our next statement follows.
Lemma 2.3. For arbitrary choice of representatives of sets in Y we have
GPaX (G) < GPaY (F).
Proof. Let H be a graph. A ray in H is a subgraph of H which is isomorphic to a path, its first vertex has degree at least 3 in H, its last vertex has degree 1 in H and all the other vertices have degree 2 in H.
We do not prove the inequality directly. Instead, we construct a sequence of graphs G = G0, G1,..., Gq = F, each Gi with a partition Xi, such that
GPaXi (Gi) < GPaXi+i (Gi+1)
for a special choice of representatives in Xi+1, where 0 < i < q—1, X0 = X and Xq = Y. We remark that for every i, Gi will be a unicyclic graph with the cycle C such that if O = {v1,..., vt} is an orbit of vertices of C in G, then all vj -rooted trees in Gi are mutually isomorphic, 1 < j < t. If t =1 then the v1-rooted trees in G, G1,..., F are mutually isomorphic and all X, X1,..., Y coincide on the vertex sets of these trees. However if t > 2, then the vertex set Ovi (Gi) of the vj -rooted trees, 1 < j < t, is partitioned in Xi according to the distance from C, and we assume that all the representatives of these sets are in the v1 -rooted tree. This assupmtion is possible since O is an orbit in G, and although O does not need to be an orbit of Gi, the vertices of O are nicely distributed along the cycle C in Gi.
So consider i, 0 < i < q. We assume that Gi is already known and we construct Gi+1. For this, let O = {v1,..., vt} be an orbit of vertices of C in G, where t > 2. If the v1-rooted tree (and so also vj -rooted trees for 2 < j < t) is a path rooted at the endvertex, then we are done with this orbit of G. So suppose that the v1-rooted tree has at least two endvertices different from v1, and consequently, at least two distinct rays starting at a common vertex. Let R1 and R2 be two rays starting at a vertex c such that distGi (v1, c) is maximum possible. We assume that R1 is not shorter than R2. If there is a representative xj of Xj which is in R2, then replace it by a vertex of Xj in R1. Observe that this replacement
does not change GPaX (Gi). Now delete R2 from the v1-rooted tree and attach it to the second vertex of R1. Moreover, repeat the same procedure in all the other vj -rooted trees, 2 < j < t, and denote by Gi+1 the resulting graph. Denote by Ti and Ti+1 the v1-rooted
460
Ars Math. Contemp. 17 (2019) 349-368
tree in G® and G®+1, respectively. If R and R2 have the same length, then this operation may create a new set in X®+1, because T® may have smaller depth than T®+1. (As is the custom, by depth we denote the largest distance from the root.) In such a case choose a representative of this new set in R2. This is the unique case when a representative will be
in R2 in T®+1.
Let d = distGi (v1, c) and let £ be the length of R2. Assume that the indices of sets in X® and X®+1 are chosen so that XJ+1 in G®+1 was obtained from XJ in G® and the
representatives of X® and XJ+1 coincide whenever possible. Then wXi (xj) in G® may
j j j j
differ from wXi+1 (xj+1) in G®+1 only if XJ+1 contains vertices of vk-rooted trees, 1 <
j j j
k < t, which are at distance d +1, d + 2,..., d +£ +1 from C. We distinguish three cases.
Case 1: XJ+1 contains vertices at distance d +1 from C. Then in the v1-rooted tree, XJ+1 is smaller than XJ by exactly one vertex. Consequently |XJ | — |XJ+11 = t. Comparing to
yi	yi+i ' 1	-
GPaX (G®), GPaX (Gi+1) is decreased by 2 due to a missing vertex in Ti+1 and it is decreased by (t — 1)2(d +1) + c due to missing vertices in vk-rooted trees 2 < k < t. Here c represents the distances using the edges of C, that is c = J2k=2 distG(v1, vk). Hence,
wXi+i (xj+1) — Wxi (xj) = —2 — (t — 1)2(d + 1) — c.	(2.2)
Xj j
Case 2: XJ+1 contains vertices at distance d + a from C, where 2 < a < £ Then |XJ+1| = |XJ| and comparing to GPaXi(G®), GPaXi+1 (Gi+1), is decreased by 2 due to a shorter distance to a vertex of XJ+1 in R2. Hence,
Case 3: X®+1 contains vertices at distance d + I + 1 from C. Then in the v1-rooted tree,
-i+i (xf1) — wxi (x® ) = —2.	(2.3)
j 1 contains vertices
XJ+1 is larger than XJ by exactly one vertex. Consequently |XJ+11 — |XJ | = t. Comparing
to GPaXi (G®), GPaXi+1 (G®+1) is increased by (t — 1)2(d +1 +1) + c due to new vertices in vk -rooted trees, 2 < k < t. Here c is the very same constant as in Case 1, that is c = J2k=2 distG(v1, vk). In some cases, namely if XJ is not empty, GPaX is increased by at least 2 due to a new vertex in T®+1, but we do not need to consider this contribution in our calculations. Hence,
wxi+i (x!+1) — wxi (x®) > (t — 1)2(d + £ +1) + c.	(2.4)
Xj j
Since wxi+i (x®+1) = wXi (x®) when X^ % OVi(G®), summing the expressions (2.2), (2.3) and (2.4j) we get	j
GPaXi+i (G®+1) — GPaXi(G®) > (—2 — (t — 1)2(d + 1) — c) — (£ — 1)2
+ ((t — 1)2(d + £ +1)+ c) = (t — 2)2£ > 0
since t > 2.	□
Let Y® € Y. Observe that if Y® n V(C) = 0, then Y® C V(C). Let Y' be those sets of Y which contain vertices of V(C). We define a new partition Z of F as follows:
Z = Y\Y' u V(C).
M. Knor et al.: Unicyclic graphs with the maximal value of Graovac-Pisanski index
461
That is, we merge together all sets Y containing vertices of V(C). All the other sets of Z coincide with the sets of Y. We have the following statement.
Lemma 2.4. For arbitrary choice of representatives of sets in Z we have
GPaY (F) < GPaZ (F).
Proof. Observe that there are three types of sets in Z. First, if vi G V(C) is a trivial orbit in G, then orbits of vertices of the vi-rooted tree are sets of Z. Second, if jvi,..., vt} C V(C) is a non-trivial orbit in G, that is if t > 2, then the vj-rooted trees are paths with endvertices vj, and sets of vertices of OVl (F) in Z contain vertices of these t rooted trees which are at the same distance from C. Finally, Z contains V(C). If Zj is a set of Z of the first type or of the second type and u, v G Zj, then wZi (u) = wZi (v). Hence, to prove the statement it suffices to show that
WY (yj) < wV (C)(z) = wY(z)
where z is an arbitrary vertex of V(C) and Y' is defined before Lemma 2.4. (Recall that yj is a representative of Y in Y.)
Thus, let z G V(C) and let Y G Y'. In what follows we show that wYi (yj) < wYi (z). We distinguish four cases.
Case 1: |Yj| = 1. Since wYi(yj) = 0 < distF(z, yj) = wYi(z), we have wYi(yj) < wy. (z).
Case 2: |Yj| = 2. let Yj = {yj, y}. Then by triangle inequality
WYi(yj) = distF(yj, y) < distF(z,yj) + distF(z,y) = w^(z).
Hence, in the sequel we assume that | Y | > 3. Since Yj is an orbit of vertices of C in G, there is a nontrivial rotational automorphism
a in Aut(G) such that {ak(yj) | k G N} C Yj. Let r be the biggest order of a rotational automorphism of this type and let a be the corresponding automorphism. Observe that r > 2. Since wYi (u) = wYi (v) for u, v G Yj, we assume that yj is chosen so that distF (z, yj) is smallest possible.
Case 3: r is even. Let Y/ = {ak(yj) | 0 < k < r}. We rename vertices of Y/ as {y0, y1,..., yr-1} so that distF(yj,yk) < distF(yj,yfc+1) whenever 0 < k < r — 1. Observe that y0 = yj, the vertices y2£-i and y2£ have the same distance from yj if 1 < I < r/2 and yr-i is the unique vertex of Y/ with the largest distance from yj. Since yj is the vertex of Yi with the smallest distance from z, we have
distF (y2£-i, yj) + distF (yj, y2£) = distF (y2£-i, z) + distF (z, y2£)
for 1 < I < r/2 and also
distF (yj, yr-i) = distF (yj, z) + distF (z, yr-i) = 2 |V (C )|.
Hence, wY/(yj) = wY/(z). If Yj = Y/, we are done. Therefore, in the sequel assume that there is also a reflexion p such that P(Y') C Y andP(Y')n Yj = 0. Then Y = Y'uP(Y/) and |Y| = 2r. Observe that all the vertices of P(Y') are obtained from arbitrary one of
462
Ars Math. Contemp. 17 (2019) 349-368
them using a. Thus, let yf be a vertex of ft(Y/) with the smallest distance from y. Then using the same arguments as above we get
Wf(Y!)(Vf) = wf(Yf)(Vi).
Since Wf(Y!) (yf) = wY! (yi), we get
WYi (yi) = 2wyi (yi). Analogously, if yfz is a vertex of ft(Y/) at the smallest distance from z, we get
wf(Y')(yfz) = wf(Yi)(z). Since Wf(Yf) (yfz) = wY!(yi), we obtain wy,(yi) = »y,(z).
Case 4: r is odd. Let Yi' = {ak(yi) | 0 < k < r}. Then proceeding analogously as in Case 3 one gets
wY! (z) = wy; (yi) +distF (yi ,z),
and so wYi (yi) < wYi (z) if Yi = Y/. Hence, assume that there is a reflexion ft such that ft(Y/) C Yi and ft(Y/) n Y/ = 0. Again, Yi = Y/ U ft(Y/) and |Yi| = 2r, and all the vertices of ft(Y/) are obtained from arbitrary one of them using a. Thus, let yf be a vertex of ft (Y/) with the shortest distance from yi. Then analogously as in Case 3 one gets
WY'(yi) = wf(Y')(yf) = wf{YD(yi) - distF(yf,yi)
and so
»Yi (yi) = 2wy,' (yi) + distF (yf ,yi).
Also, let yfz be a vertex of ft(Y/) with the shortest distance from z. Then analogously as above we get
WY' (yi) = Wf(Y!)(yfZ ) = Wf(Y')(z) - distF (yfz, z)
and so
WY, (z) = 2»y' (yi) + distF(yfz, z) + distF(yi,z).
Since
distF(yf ,yi) < distF(yfz,yi) < distF(yfz,z) + distF(yi,z), we get »y(yi) < »y, (z).	□
Finally, we are in a position to prove the last lemma which implies Theorem 1.3. Observe that there is a strict inequality in Lemma 2.5.
Lemma 2.5. We have
GPaZ(F) < GPa(Cn).
Proof. Analogously as in Lemma 2.3, we prove the statement by a sequence of steps. Let O1,..., Oq be all orbits of vertices of C in G, such that for every v G Oi the v -rooted tree is nontrivial (i.e., it has more than one vertex). Observe that if the v-rooted tree is nontrivial in G, then the v-rooted tree in F is also nontrivial. Assume that IO11 > |O2 | > • • • > |Oq|.
M. Knor et al.: Unicyclic graphs with the maximal value of Graovac-Pisanski index
463
We consecutively create unicyclic graphs F = F0, F1,..., Fq = Cn with partitions Z = Z0, Z1,..., Zq, respectively, and for every i, 0 < i < q, we show that GPaZ (F®) < GPaZ (F®+1). The graph F®+1 is obtained from F® by moving the vertices of v -rooted trees, where v G O®+1, into the unique cycle C® of F®. Now we describe the process in detail.
Choose i, 0 < i < q. For v G O®+1, let p + 1 be the number of vertices of v-rooted tree in F® (or in G, since the numbers of vertices of v-rooted trees in G and F are the same). By our assumption p > 1. Orient the cycle C® of F® and for every vertex u G V(C®) let uf be the vertex following u on C®. Let v G O®+1. Delete the p non-root vertices of the v-rooted tree from F® and subdivide the edge vvf exactly p times. Repeat this procedure for all vertices of O®+1 and denote by F®+1 the resulting unicyclic graph. The partition Z®+1 is exactly the same as Z®, the only exception is that instead of the set V(C®) and various sets partitioning Ov (F®) for v G O®+1 we have just the set V(C®+1) in Z®+1. We assume that if a set of Z® is identical with a set of Z®+1, then they have the same representatives.
Let Z ' g Z ® and Z * g Z ®+1 such that Z ' = Z *. Then Z ' is a collection of vertices of Ou(F®), i.e., of u-rooted trees for u g Oj, where j > i + 1. Since the distances between these vertices cannot be shorter in F®+1 than in F® (they can be only larger due to the extension of C® to C®+1), we have (z') < (z*) where z' is a representative of Z' in F® and z* is a representative of Z* in F®+1. Hence, it suffices to check the contribution of V(C®+1) in GPaZ+1 (F®+1) and in GPaZ (F®) the contribution of V(C®) and of the sets of non-root vertices of v-rooted trees for v g O®+1. Let t = |O®+1|. Analogously as in the proof of Lemma 2.4 we distinguish four cases. In these cases, we set c = | V(C®) |. Moreover, by ¿a we denote the parity of a. That is ¿a = 1 if a is odd and ¿a = 0 if a is even.
Case 1: t = 1. By Proposition 2.1, V(C®) contributes 4(c2 - ¿c) to GPaZ(F®) and V(C®+1) contributes 1 ((c + p)2 - ¿c+p) to GPaZ'+1 (F®+1). Let O®+1 = {v1}. Denote by T the v1 -rooted tree in F®. Since T is a tree on p + 1 vertices, the orbits of T contribute to GPaZ (F®) at most 1 ((p + 1)2 - ¿^+1) by Theorem 1.2. So
4(GPaZi+1 (F®+1) - GPaZ(F®)) > (c + p)2 - ¿c+p - c2 + ¿c - (p + 1)2 + ¿p+1
> (c + p)2 - c2 - (p +1)2 - 1 = 2p(c - 1) - 2 > 0
since c > 3 and p > 1.
Case 2: t = 2. In this case the v-rooted trees are paths whenever v g O®+1. Since the contribution to GPaZ (F®) of j-th vertices of these paths (i.e., of vertices at distance j from the roots) is at most j + c/2 + j, the total contribution of non-root vertices of v-rooted trees, v G O®+1, is at most 2(p+1) + 1 cp. Since the contribution of V(C®) is 4(c2 - ¿c) and the contribution of V(C®+1) is 4 ((c + 2p)2 - ¿c+2p), where ¿c+2p = ¿c, we get
4(GPaZ'+1 (F®+1) - GPaZ(F®)) > (c + 2p)2 - ¿c - c2 + ¿c - 8(p+1) - 2cp
2 2 2
> (c + 2p)2 - c2 - 4p2 - 4p - 2cp = 2p(c - 2) > 0
since c > 3 and p > 1 .
464
Ars Math. Contemp. 17 (2019) 349-368
In the remaining cases we may assume that there is a nontrivial rotational automorphism a of F® such that when v G Oi+1 then also a(v) G Oi+1. Let r be the biggest order of such a rotational automorphism a, and moreover, let a be such that the distance s between v and a(v) is the smallest possible. Then c = r • s.
Case 3: r is even. Then r > 2. Let v0 G Oi+1. Denote O' = {ak(v0) | 0 < k < r}. First assume that |Oi+1| = 2r. Hence there is also a reflexion P such that P(O') Ç Oi+1 and P(O') n O' = 0. Let v1 g Oi+1 such that the distance t between v0 and v1 is the smallest possible. Then t < s/2 and v1 G P(O'). Observe that now t > 1 and s > 2. Since c = rs is even, the contribution of V (C®) to GPaZ (F®) is 4r2s2. The contribution of V(Ci+1) to GPaZ + ( Fi+1 ) is 1 r2 ( s + 2p)2. Now we calculate the contribution of non-root vertices of v-rooted trees when v g Oi+1. These trees are paths and the contribution of j-th vertices is
2(s + 2j) + 2(2s + 2j ) + • • • + 2(( § - 1)s + 2j) + (§ s + 2j)
+ (t + 2j ) + (s + t + 2j) + ••• + (( 2 - 1)s+1 + 2j) +(s - t + 2j) + (2s - t + 2j) + • • • + ((2 - 1)s - t + 2j) + (2s - t + 2j)
= 4(s + 2j) + 4(2s + 2j) + • • • + 4((f - 1)s + 2j) + 2(2s + 2j) + 2j
= 2r2s + 2j(2r - 1).
So the contribution of non-root vertices of v-rooted trees, v G Oi+1, is
r2s + 2j(2r - 1)) = 2r2sp + (p2 + p)(2r - 1).
j=1
Hence
GPaZ (Fi+1) - GPaZ(F®) > 1 r2s2 + r2sp + r2p2 - 1 r2s2
- 2r2sp - 2rp2 - 2rp + p2 + p = p2(r-1)2 + p(r(2rs-2) + 1) > 0
since r > 2, s > 2 and p > 1.
In the case when |Oi+1| = r, the contribution of V(Ci+1) is 4r2(s + p)2 and the contribution of j-th vertices in v-rooted trees, v G Oi+1, is
2(s + 2j) + 2(2s + 2j) + • • • + 2((2 - 1)s + 2j) + (2s + 2j) = 1 r2s + 2j(r - 1).
So the contribution of non-root vertices of v-rooted trees, v G Oi+1, is
r2s + 2j(r - 1)) = 4r2sp + (p2 + p)(r - 1).
j=1
Hence
GPaZi+1 (Fi+1) - GPaZ(F®) > 4r2s2 + 1 r2sp + 4r2p2 - 4r2s2
12 2 i 2 i - 4 r sp - rp - rp + p + p
^ r n2 , „,r
= p2(2 - 1)2 + p(r(4rs - 1) + 1) > 0
M. Knor et al.: Unicyclic graphs with the maximal value of Graovac-Pisanski index
465
since in this case r > 4, s > 1 and p > 1.
Case 4: r is odd. Then r > 3. Let v0 G Oi+1 and O' = {ak(v0) | 0 < k < r}. First assume that |Oi+1| = 2r. Hence there is also a reflexion P such that P(O') Ç Oi+1 and P(O') n O' = 0. Let v1 g Oi+1 such that the distance t between v0 and v1 is the smallest possible. Then t < s/2 and v1 G P(O'). The contribution of V(C4) to GPaZ(F®) is 4(r2s2 - Jrs). The contribution of V(Ci+1) to GPaZ(Fi+1) is 4(r2(s + 2p)2 -¿r(s+2p)). Now we calculate the contribution of non-root vertices of v-rooted trees when v g Oi+1. These trees are paths and the contribution of j-th vertices is
2(s + 2j) + 2(2s + 2j) + • • • + 2( ^ s + 2j )
+ (t + 2j) + (s + t + 2j) + • • • +2 (^s + t + 2j) + (s - t + 2j) + (2s - t + 2j) + • • • + (^s - t + 2j)
= 4(s + 2j) + 4(2s + 2j) + • • • + 4( ^ s + 2j) + (t + 2j) = 1 (r2 - 1)s + 2j(2r - 1) + t.
So the contribution of non-root vertices of v-rooted trees, v G Oi+1, is
E (2(r2 - 1)s + 2j(2r - 1) +t) = 1 (r2 -3=1	< 1 r2sp +(p2 + p)(2r - 1)
(r2 - 1)s + 2j(2r - 1) + t) = ±(r2 - 1)sp + (p2 + p)(2r - 1) + pt
since -1 sp + pt < 0. Hence
GPaZi+1 (Fi+1) - GPaZ (F®) > 1 r2s2 + r2sp + r2p2 - 1 Jrs - 4r2s2 + 1 J,
- 2r2sp - 2rp2 - 2rp + p2 + p = p2(r - 1)2 + p(r(2rs - 2) + 1) > 0
since r > 3, s > 2 and p > 1.
In the case when |Oi+1| = r, the contribution of V(Ci+1 ) to GPaZ'+1 (Fi+1) is 4 (r2 (s + p)2 - ¿r(s+p)) and the contribution of j-th vertices in v-rooted trees, v G Oi+1, is
2(s + 2j) + 2(2s + 2j) + • • • + 2(^s + 2j) = 4(r2 - 1)s + 2j(r - 1).
So the contribution of non-root vertices of v-rooted trees, v G Oi+1, is p
E (4(r2 - 1)s + 2j(r - 1)) = 1 (r2 - 1)sp + (p2 + p)(r - 1). j=1
Hence
GPaZi+1 (Fi+1) - GPaZ(F®) > 4r2s2 + 2r2sp + 4r2p2 - 4 - 4r2s2
- 4 (r2 - 1)sp - rp2 - rp + p2 + p = p2(§ - 1)2 + p(r( 1 rs - 1) + 4s + 1) - 1 > 0
since in this case r > 3, s > 1 and p > 1. (Observe that the second bracket is at least | if
r = 3 and s = 1.)	□
466
Ars Math. Contemp. 17(2019)455-466
References
[1]	A. R. Ashrafi and M. V. Diudea (eds.), Distance, Symmetry, and Topology in Carbon Nano-materials, volume 9 of Carbon Materials: Chemistry and Physics, Springer, Cham, 2016, doi:10.1007/978-3-319-31584-3.
[2]	A. R. Ashrafi, F. Koorepazan-Moftakhar and M. V. Diudea, Topological symmetry of nanos-tructures, Fuller. Nanotub. Car. N. 23 (2015), 989-1000, doi:10.1080/1536383x.2015.1057818.
[3]	A. R. Ashrafi, F. Koorepazan-Moftakhar, M. V. Diudea and O. Ori, Graovac-Pisanski index of fullerenes and fullerene-like molecules, Fuller. Nanotub. Car. N. 24 (2016), 779-785, doi: 10.1080/1536383x.2016.1242483.
[4]	A. R. Ashrafi and H. Shabani, The modified Wiener index of some graph operations, Ars Math. Contemp. 11 (2016), 277-284, doi:10.26493/1855-3974.801.968.
[5]	M. Crepnjak, M. Knor, N. Tratnik and P. Zigert Pletersek, The Graovac-Pisanski index of a connected bipartite graph is an integer number, submitted, arXiv:1709.04189 [math.CO].
[6]	M. Crepnjak, N. Tratnik and P. Zigert Pletersek, Predicting melting points of hydrocarbons by the Graovac-Pisanski index, Fuller. Nanotub. Car. N. 26 (2018), 239-245, doi:10.1080/ 1536383x.2017.1386657.
[7]	M. Ghorbani and S. Klavzsar, Modified Wiener index via canonical metric representation, and some fullerene patches, Ars Math. Contemp. 11 (2016), 247-254, doi:10.26493/1855-3974. 918.0b2.
[8]	A. Graovac and T. Pisanski, On the Wiener index of a graph, J. Math. Chem. 8 (1991), 53-62, doi:10.1007/bf01166923.
[9]	M. Hakimi-Nezhaad and M. Ghorbani, On the Graovac-Pisanski index, Kragujevac J. Sci. 39 (2017), 91-98, doi:10.5937/kgjsci1739091h.
[10]	M. Knor, R. Skrekovski and A. Tepeh, Trees with the maximal value of Graovac-Pisanski index, Appl. Math. Comput. 358 (2019), 287-292, doi:10.1016/j.amc.2019.04.034.
[11]	F. Koorepazan-Moftakhar and A. R. Ashrafi, Distance under symmetry, MATCH Commun. Math. Comput. Chem. 74 (2015), 259-272, http://match.pmf.kg.ac.rs/ electronic_versions/Match7 4/n2/match74n2_25 9-272.pdf.
[12]	F. Koorepazan-Moftakhar and A. R. Ashrafi, Combination of distance and symmetry in some molecular graphs, Appl. Math. Comput. 281 (2016), 223-232, doi:10.1016/j.amc.2016.01.065.
[13]	F. Koorepazan-Moftakhar, A. R. Ashrafi and O. Ori, Symmetry groups and Graovac-Pisanski index of some linear polymers, Quasigroups Related Systems 26 (2018), 87-102, http:// www.quasigroups.eu/contents/download/2 018/2 6_10.pdf.
[14]	R. Pinal, Effect of molecular symmetry on melting temperature and solubility, Org. Biomol. Chem. 2 (2004), 2692-2699, doi:10.1039/b407105k.
[15]	H. Shabani and A. R. Ashrafi, Symmetry-moderated Wiener index, MATCH Commun. Math. Comput. Chem. 76 (2016), 3-18, http://match.pmf.kg.ac.rs/electronic_ versions/Match7 6/n1/match7 6n1_3-18.pdf.
[16]	N. Tratnik, The Graovac-Pisanski index of zig-zag tubulenes and the generalized cut method, J.Math. Chem. 55 (2017), 1622-1637, doi:10.1007/s10910-017-0749-5.
[17]	N. Tratnik and P. Zigert Pletersek, The Graovac-Pisanski index of armchair tubulenes, J. Math. Chem. 56 (2018), 1103-1116, doi:10.1007/s10910-017-0846-5.
[18]	H. Wiener, Structural determination of paraffin boiling points, J. Am. Chem. Soc. 69 (1947), 17-20, doi:10.1021/ja01193a005.