ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 21 (2021) #P2.05 / 243–257
https://doi.org/10.26493/1855-3974.2351.07b
(Also available at http://amc-journal.eu)
Density results for Graovac-Pisanski’s
distance number
Lowell Abrams
University Writing Program and Department of Mathematics,
The George Washington University, Washington, DC 20052, USA
Lindsey-Kay Lauderdale *
Department of Mathematics, Towson University, Towson, MD 21252, USA
Received 2 June 2020, accepted 13 May 2021, published online 30 October 2021
Abstract
The sum of distances between every pair of vertices in a graph G is called the Wiener
index of G. This graph invariant was initially utilized to predict certain physico-chemical
properties of organic compounds. However, the Wiener index of G does not account for
any of its symmetries, which are also known to effect these physico-chemical properties.
Graovac and Pisanski modified the Wiener index of G to measure the average distance
each vertex is displaced under the elements of the symmetry group of G; we call this the
Graovac-Pisanski (GP) distance number of G. In this article, we prove that the set of all
GP distance numbers of graphs with isomorphic symmetry groups is dense in a half-line.
Moreover, for each finite group Γ and each rational number q within this half-line, we
present a construction for a graph whose GP distance number is q and whose symmetry
group is isomorphic to Γ. This construction results in graphs whose vertex orbits are not
connected; we also consider an analogous construction which ensures that all vertex orbits
are connected.
Keywords: Wiener index, distance number, Graovac-Pisanski index, graph automorphism group,
chemical graph theory.
Math. Subj. Class. (2020): 05C12, 05C25, 05C35, 05C92
*Corresponding author. The author is the Jess and Mildred Fisher Endowed Professor of Mathematics in the
Fisher College of Science and Mathematics at Towson University and is partially supported by this endowment.
E-mail addresses: labrams@gwu.edu (Lowell Abrams), llauderdale@towson.edu (Lindsey-Kay Lauderdale)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
244 Ars Math. Contemp. 21 (2021) #P2.05 / 243–257
1 Introduction
Throughout this article, all graphs considered are simple and finite, and all groups consid-
ered are finite. We let V (G) and E(G) denote the vertex set and edge set of a graph G,
respectively. The Wiener index of G is the sum of all distances between pairs of vertices in
G, namely
W (G) :=
1
2
∑
u∈V (G)
∑
v∈V (G)
d(u, v),
where d(u, v) is the length of a shortest path between u and v in G. This graph invariant
was original defined by Wiener [14], where he considered graphical representations of
molecules. In particular, each vertex in V (G) represents an atom of a molecule and each
edge in E(G) represents a bond between atoms. Wiener [14] used this graph invariant to
establish an equation that predicts the boiling points of paraffin molecules.
Other physico-chemical properties of organic molecules, including refractive index,
heat of isomerization, heat of vaporization, density, surface tension, viscosity, and chro-
matographic retention time, were later linked to the Wiener index [5]. Consequently, the
Wiener index of classes of compounds, including benzenoids [6], chains [13], and trees [2],
were calculated; Mohar and Pisanski [11] described numerous algorithms that compute the
Wiener index of a graph in general. An interested reader can see [10] and the references
within for more results on this graph invariant.
The symmetries of molecules are known to effect certain physico-chemical properties
of organic compounds [12]. In this article, we are interested in a modification ofW (G) that
accounts for these symmetries of G. Recall the set of adjacency-preserving permutations
of V (G) is called the automorphism group of G and is denoted by AutG. Graovac and
Pisanski [4] defined the distance number of G to be the average
δ(G) :=
1
|AutG||V (G)|
∑
u∈V (G)
∑
σ∈AutG
d
(
u, σ(u)
)
.
We call this invariant the Graovac and Pisanski (GP) distance number. Graovac and Pisan-
ski [4] established some basic properties of δ(G) and computed δ(G) provided G is a path,
cube, cycle graph, complete bipartite graph, or lattice graph. Note that the results in this
article only hold for the GP distance number and not what is currently referred to in the
literature as the Graovac-Pisanski index, namely Ŵ (G) := 12 |V (G)|
2δ(G).
The GP distance number and the GP index were the subject of prior research by a num-
ber of authors. For example, Ashrafi and Shabani [1] computed the GP index of graphs that
resulted via standard graph operations on trees. The GP index of truncation graphs, Thorn
graphs, and caterpillars were calculated by Iranmanesh and Shabani [7]. Additionally, Knor
et al. [8] considered the maximum GP index among all graphs of a fixed order. Note that
these results on the GP index have direct implications for the GP distance number.
In this article, we consider a dual problem to that of computing the maximum GP dis-
tance number among all graphs of a fixed order; this approach better represents how the GP
distance numbers of classes of compounds can predict their physico-chemical properties.
Specifically, for a given group Γ, we establish the possible values of δ(G) among all graphs
G with AutG ∼= Γ. When AutG ∼= Γ, we call G a Γ -graph. Our main result is stated
below.
L. Abrams and L.-K. Lauderdale: Density results for Graovac-Pisanski’s distance number 245
Theorem 1.1. Given a group Γ, define
DΓ := {δ(G) : G is a Γ-graph}.
The setDΓ is dense in (inf(DΓ),∞). Moreover, for each rational number q ∈(inf(DΓ),∞),
there exists a Γ-graph G with δ(G) = q.
Our results will establish the exact value of inf(DΓ), as well as give two infinite families
of Γ-graphs whose GP distance numbers equal this infimum.
We prove Theorem 1.1 by constructing a family of Γ-graphs whose vertex orbits under
the Γ-action are not necessarily connected. Consideration of Γ-graphs whose vertex orbits
are all connected yields a more restricted result, Theorem 6.3, in which the interval of
potential GP distance numbers is finite and, moreover, not every rational number in the
interval can be obtained as a GP distance number of a graph in the constructed family.
This article is organized as follows. In Section 2, we describe an alternative formula
to compute δ(G) for a given graph G, and then use it to state bounds on this invariant in
terms of W (G). Next, for a given group Γ, we construct an infinite family of Γ-graphs
in Section 3. The results of Section 4 establish their associated GP distance numbers, and
in Section 5, we present a proof of our main result, Theorem 1.1. Finally, we conclude in
Section 6 with a discussion leading to Theorem 6.3.
2 Preliminaries
The definition of δ(G) for a graphG can be reformulated by considering the orbits of V (G)
under the action of AutG. For ease of notation, define
d(v, V ) :=
∑
u∈V
d(v, u),
where v ∈ V ⊆ V (G). Graovac and Pisanski connected this alternative expression for
δ(G) to the Wiener index of the vertex orbits of G; we state their results below.
Theorem 2.1 (Graovac and Pisanski [4]). If V0, V1, . . . , Vp−1 are the orbits of V (G) de-
termined by AutG and vi ∈ Vi for each i ∈ {0, 1, . . . , p− 1}, then
δ(G) =
1
|V (G)|
p−1∑
i=0
d(vi, Vi) =
2
|V (G)|
p−1∑
i=0
W (Vi)
|Vi|
. (2.1)
For the remainder of this article, we will use Equation (2.1) to compute the GP distance
number of a given graph. As simple examples, we calculate the GP distance numbers of
both complete graphs and paths below.
Example 2.2. Let Kn denote the complete graph with n vertices. If v ∈ V (Kn), then
δ(Kn) =
1
n
d
(
v, V (Kn)
)
=
n− 1
n
,
where the first equality holds because Kn is vertex-transitive (i.e., p = 1) and the second
equality holds because v is adjacent to all vertices in V (Kn) except itself.
246 Ars Math. Contemp. 21 (2021) #P2.05 / 243–257
Example 2.3. Let Pn denote the path of order n ≥ 2, and label this graph so that uiui+1 ∈
E(Pn) for each i ∈ {0, 1, . . . , n−2}. Since Pn is a Z2-graph, there are
⌊
n+1
2
⌋
vertex orbits
under the action of Aut(Pn). Set p =
⌊
n+1
2
⌋
and label these orbits by V0, V1, . . . , Vp−1
so that ui ∈ Vi for each i ∈ {0, 1, . . . , p − 1}. Under these assumptions, ui and un−1−i
comprise the orbit Vi and
d(ui, Vi) = d(ui, ui) + d(ui, un−1−i) = 0 + (n− 1− 2i) = n− 1− 2i
for all i ∈ {0, 1, . . . , p− 1}. Therefore,
δ(Pn) =
1
n
p−1∑
i=0
(n− 1− 2i︸ ︷︷ ︸
d(ui,Vi)
) =
1
n
[
p(n− 1)− 2
(
1
2
(p− 1)p
)]
=
{
n
4 if n is even
n2−1
4n if n is odd,
where the first equality holds by Equation (2.1) and the last equality holds because p =⌊
n+1
2
⌋
.
Paths and complete graphs represent important families of graphs in the context of
the Wiener index. In particular, Knor, Škrekovski, and Tepeh [9] observed that if G is a
connected graph of order n, then(
n
2
)
=W (Kn) ≤W (G) ≤W (Pn) =
(
n+ 1
3
)
. (2.2)
For a given graph G, this observation allows us to place simple bounds on δ(G) in terms of
W (G).
Lemma 2.4. Let G be a graph. If the induced subgraph on each vertex orbit of G under
the action of AutG is connected with order k, then
k − 1
k
≤ δ(G) ≤ k
2 − 1
3k
.
Proof. Let V0, V1, . . . , Vp−1 denote the vertex orbits of G under the action of AutG. Be-
cause each orbit has size k and |V (G)| = kp, Equation (2.1) implies
δ(G) =
2
k2p
p−1∑
i=0
W (Vi).
Combining the equation above with Equation (2.2), we obtain
k − 1
k
=
2
k2p
· p
(
k
2
)
≤ δ(G) ≤ 2
k2p
· p
(
k + 1
3
)
=
k2 − 1
3k
,
as desired.
The lower bound stated in Lemma 2.4 is realized by G = Kn (see Example 2.2). As
demonstrated by Example 2.3, the upper bound in Lemma 2.4 is not realized by G = Pn.
Moreover, we conjecture this upper bound is not sharp under the stated assumptions.
For a given group Γ, Theorem 1.1 implies that there is no maximum value of δ(G)
among all Γ-graphs. In fact, the values of GP distance numbers of graphs in general are not
bounded; Lemma 2.4 foreshadows how these graphs must be built. To construct a family of
graphs with arbitrarily large GP distance numbers, the induced subgraphs on some of the
vertex orbits must be disconnected. We continue by constructing such graphs in the next
section.
L. Abrams and L.-K. Lauderdale: Density results for Graovac-Pisanski’s distance number 247
3 Graph construction
To investigate the set DΓ, we will construct an infinite family of Γ-graphs, parameterized
by non-negative integers a and c, from a given Γ-graph G. Specifically, each graph φac (G)
in this family will be constructed by appending to G, in a special way, a anti-cliques of
order |V (G)| and c cliques of order |V (G)| (see Definition 3.1 below). Every vertex in
φac (G) will have two labels; the superscript of a vertex indicates its distance to G and the
subscript label represents the vertex in G it is closest to. The parameters a and c are used
in Section 5 to increase and decrease the value of δ
(
φac (G)
)
, respectively.
Definition 3.1. Let Γ be a group, and suppose G is a Γ-graph with V (G) = {u00, u01, . . . ,
u0n−1}. Given a, c ∈ N, construct a new graph from G, denoted φac (G), with n(1 + a+ c)
vertices and
E(G) + an+ c
(
n+
1
2
n(n− 1)
)
edges as follows:
1. For each i ∈ {0, 1, . . . , n−1}, attach a path of length a to vertex u0i and sequentially
label the vertices on that path by u0i , u
1
i , u
2
i , . . . , u
a
i .
2. For each i ∈ {0, 1, . . . , n − 1}, attach a path of length c to u0i and sequentially
label the vertices w0i , w
1
i , w
2
i , . . . , w
c
i , where w
0
i := u
0
i ; thereupon, provided c ̸= 0,
include the edgeswki w
k
j for all k ∈ {1, 2, . . . , c} and distinct i, j ∈ {0, 1, . . . , n−1}.
Observe that G and φac (G) are equal when a = 0 = c. The graph φ
a
0(Cn) is depicted
in Figure 1, where Cn denotes the cycle graph of order n. We discuss the structure of the
vertex orbits of φac (G) under the action of Aut
(
φac (G)
)
in the following remark.
Remark 3.2. Let Γ be a group. IfG and φac (G) are both Γ-graphs, then the vertex orbits of
φac (G) under its Γ-action depend on the vertex orbits of G under its Γ-action. In particular,
let V0, V1, . . . , Vp−1 denote the vertex orbits of G under its Γ-action. By construction, we
obtain a + c vertex orbits of φac (G) under its Γ-action for each Vi, so, in total, φ
a
c (G) has
(1 + a+ c)p vertex orbits under its Γ-action.
We continue with an example in which we compute the value of δ
(
φa0(Cn)
)
for all
a, n ∈ N with n ≥ 3.
Example 3.3. Let us compute the GP distance number of the graph φa0(Cn), which is
illustrated in Figure 1. Recall that Cn is vertex-transitive. If Aj is the orbit of u
j
0 under
the dihedral action of Aut
(
φa0(Cn)
) ∼= D2n for all j ∈ {0, 1, . . . , a}, then A0, A1, . . . , Aa
form a partition of V
(
φa0(Cn)
)
. We claim the value of d(uj0, A
j) depends on the parity of
n.
Consider the vertices uj0, u
j
i ∈ Aj , where i ∈ {1, 2, . . . , n− 1} and j ∈ {0, 1, . . . , a}.
A shortest path between these vertices is constructed by concatenating the uj0, u
0
0-path of
length j, a u00, u
0
i -path of minimum length inCn, and the u
0
i , u
j
i -path of length j. Therefore,
if n = 2ℓ+ 1 is odd, then
d(uj0, A
j) =
n−1∑
i=1
d(uj0, u
j
i ) = 2
ℓ∑
k=1
(2j + k) = 4jℓ+ ℓ(ℓ+ 1) = 2(n− 1)j + n
2 − 1
4
,
248 Ars Math. Contemp. 21 (2021) #P2.05 / 243–257
u03
u02
u01
u00 u0n−1
u13
u12
u11
u10
u1n−1
ua−13
ua−12
ua−11
ua−10
ua−1n−1
ua3
ua2
ua1
ua0
uan−1
Figure 1: Depiction of the graph φa0(Cn).
and, if n = 2ℓ is even, then
d(uj0, A
j) =
n−1∑
i=1
d(uj0, u
j
i ) = (2j+ ℓ)+2
ℓ−1∑
k=1
(2j+k) = 4jℓ−2j+ ℓ2 = 2(n−1)j+ n
2
4
.
Since |V
(
φa0(Cn)
)
| = n(1 + a), we have that
δ
(
φa0(Cn)
)
=
1
n(1 + a)
a∑
j=0
d(uj0, A
j) =

4(n− 1)a+ n2 − 1
4n
if n = 2ℓ+ 1
4(n− 1)a+ n2
4n
if n = 2ℓ.
The statements in Remark 3.2 are based on the assumption that G and φac (G) have
isomorphic automorphism groups. The following proposition proves that this is almost
always the case.
Proposition 3.4. Let Γ be a group. IfG is a nontrivial connected Γ-graph and either a ̸= 0
or G is not a complete graph, then φac (G) is also a Γ-graph.
Proof. To prove that Γ is isomorphic to a subgroup of Aut
(
φac (G)
)
, we note that each
element of AutG induces a (subscript) label-preserving automorphism of φac (G). In
particular, if σ ∈ AutG, then σ induces a permutation on {0, 1, . . . , n − 1}, denoted
ρσ , such that ρσ(i) is the subscript of σ(u0i ) for all i ∈ {0, 1, . . . , n − 1}. Define the
map πσ : V
(
φac (G)
)
→ V
(
φac (G)
)
by πσ(u
j
i ) = u
j
ρσ(i)
and πσ(wki ) = w
k
ρσ(i)
for all
j ∈ {0, 1, . . . , a} and k ∈ {0, 1, . . . , c}. Since πσ preserves the adjacency relations in
φac (G) and Γ ∼= {πσ : σ ∈ AutG}, Γ is isomorphic to a subgroup of Aut
(
φac (G)
)
.
L. Abrams and L.-K. Lauderdale: Density results for Graovac-Pisanski’s distance number 249
It remains to prove that any element of Aut
(
φac (G)
)
is equal to πσ for some σ ∈
AutG. Clearly if a = 0 = c, then φac (G) = G and the proposition holds. Thus, in what
follows we assume that at least one of a or c is nonzero.
Suppose a ̸= 0, and consider the image of the degree-1 vertex uai under ψ ∈
Aut
(
φac (G)
)
, where i ∈ {0, 1, . . . , n − 1}. Since the only vertices in φac (G) that have
degree 1 are of the form uaℓ , it follows that ψ(u
a
i ) = u
a
ℓ for some ℓ ∈ {0, 1, . . . , n − 1}.
In turn, ψ
(
ua−1i
)
= ua−1ℓ because u
a−1
i and u
a−1
ℓ are the only neighbors of u
a
i and
uaℓ in φ
a
c (G), respectively. Proceeding by induction, assume that ψ
(
uj
′
i
)
= uj
′
ℓ for all
j′ ∈ {j, j+1, . . . , a}. If j ≥ 1, then uji has exactly two neighbors, namely u
j+1
i and u
j−1
i ,
while uj+1ℓ and u
j−1
ℓ are the only neighbors of vertex u
j
ℓ . In this case, ψ
(
uj−1i
)
= uj−1ℓ as
ψ
(
uj+1i
)
= uj+1ℓ by induction. Therefore, ψ
(
uji
)
= ujℓ for all j ∈ {0, 1, . . . , a}.
Now define W k := {wk0 , wk1 , . . . , wkn−1} for each k ∈ {0, 1, . . . , c}. If c ̸= 0, then
each vertex in W c has degree n, and thus ψ(wci ) is also a vertex of degree n in φ
a
c (G).
The only vertices in φac (G) that have degree n are in W
0 ∪W c. However, each element
in W c is adjacent to at least n − 1 vertices of degree n, and because G is not a complete
graph or a ̸= 0, each vertex in W 0 = V (G) is adjacent to at most n − 2 vertices of
degree n. Consequently, W c is ψ-invariant; assume that ψ(wci ) = w
c
m for some m ∈
{0, 1, . . . , n − 1}. Both wci and wcm have exactly one neighbor that is not an element of
W c; hence, ψ
(
wc−1i
)
= wc−1m and we claim that ψ
(
wki
)
= wkm for all k ∈ {0, 1, . . . , c}.
Since this claim holds for k ∈ {c − 1, c}, we again proceed by induction. Assume that
ψ
(
wk
′
i
)
= wk
′
m for all k
′ ∈ {k, k + 1, . . . , c}. When k ≥ 1, the only neighbors of wki not
in W k are wk+1i and w
k−1
i ; moreover, w
k+1
m and w
k−1
m are the only neighbors of w
k
m not
in W k. Since ψ
(
wk+1i
)
= wk+1m by induction, it follows that ψ
(
wk−1i
)
= wk−1m and the
claim holds.
Our work above proves that ψ
(
uji
)
= ujℓ for all j ∈ {0, 1, . . . , a} and that ψ
(
wki
)
=
wkm for all k ∈ {0, 1, . . . , c}. Since u0i = w0i by definition of φac (G), we have ℓ =
m. Consequently, there exists σ ∈ Aut(G) such that ψ = πσ , and φac (G) is also a Γ-
graph.
We are now ready to compute the GP distance number of φac (G) when the graphs G
and φac (G) have isomorphic automorphism groups.
4 GP distance number of φac(G)
If G and φac (G) have isomorphic automorphism groups, then the value of δ
(
φac (G)
)
nat-
urally depends on the value δ(G); however, it also depends on the value of c in a special
way. In particular, if c ̸= 0, then the distance between any two vertices of G is at most 3.
Recalling that V0, V1, . . . , Vp−1 are the vertex orbits of G under the action of AutG, we
define
δ′(c,G) :=
{
δ(G) if c = 0
δ3(G) if c ̸= 0,
where
δ3(G) :=
1
|V (G)|
p−1∑
i=0
d3(ui, Vi) and d3(ui, Vi) :=
∑
u∈Vi
min{d(ui, u), 3}.
With this notation in hand, we compute the value of δ
(
φac (G)
)
below.
250 Ars Math. Contemp. 21 (2021) #P2.05 / 243–257
Proposition 4.1. Let Γ be a group, and assume that G and φac (G) are both Γ-graphs. If G
has order n and p vertex orbits under the action of AutG, then
δ
(
φac (G)
)
=
(n− p)(a2 + a+ c) + n(a+ 1)δ′(c,G)
n(1 + a+ c)
.
Proof. Let V0, V1, . . . , Vp−1 denote the p vertex orbits of G under the action of AutG.
After a possible relabelling of V (G), assume that u0i ∈ Vi for all i ∈ {0, 1, . . . , p− 1}. For
each Vi, there are a+ c associated vertex orbits of φac (G) under the action of Aut
(
φac (G)
)
by Remark 3.2; label these orbits by A1i , A
2
i , . . . , A
a
i and C
1
i , C
2
i , . . . , C
c
i , where u
j
i ∈ A
j
i
for j ∈ {1, 2, . . . , a} and wki ∈ Cki for k ∈ {1, 2, . . . , c}. Under these assumptions
δ
(
φac (G)
)
=
1∣∣V (φac (G))∣∣
 a∑
j=0
p−1∑
i=0
d(uji , A
j
i ) +
c∑
k=1
p−1∑
i=0
d(wki , C
k
i )
 , (4.1)
where A0i = Vi for i ∈ {0, 1, . . . , p − 1}. We evaluate each of these sums in one of the
following cases.
First, observe that d(wki , C
k
i ) = |Cki | − 1 for all k ∈ {1, 2, . . . , c} as the induced
subgraph on Cki is a clique. Since
c∑
k=1
|Cki | = c|Vi| and
p−1∑
i=0
|Vi| = |V (G)| = n,
it follows that
c∑
k=1
p−1∑
i=0
d(wki , C
k
i ) =
p−1∑
i=0
c∑
k=1
(|Cki | − 1) =
p−1∑
i=0
c(|Vi| − 1) = c(n− p). (4.2)
For the second case, if u0ℓ ∈ A0i , then a shortest path between vertices u
j
i ∈ A
j
i and
ujℓ ∈ A
j
i is constructed by concatenating the following three paths:
1. the uji , u
0
i -path in φ
a
c (G) of length j;
2. a u0i , u
0
ℓ -path of minimum length in G if c = 0 or in φ
0
1(G) provided c ̸= 0; and
3. the u0ℓ , u
j
ℓ-path in φ
a
c (G) of length j.
It follows that
d(uji , A
j
i ) = 2j(|A
j
i | − 1) + d
′(c, u0i , A
0
i ),
where
d′(c, u0i , A
0
i ) :=
{
d(u0i , A
0
i ) if c = 0
d3(u
0
i , A
0
i ) if c ̸= 0.
Since |Aji | = |Vi| for all j ∈ {0, 1, . . . , a}, we have
a∑
j=0
p−1∑
i=0
d(uji , A
j
i ) =
p−1∑
i=0
a∑
j=0
(
2j(|Aji | − 1) + d
′(c, u0i , A
0
i )︸ ︷︷ ︸
d(uji ,A
j
i )
)
=
p−1∑
i=0
(
2
1
2
a(a+ 1)(|Vi| − 1) + (a+ 1)d′(c, u0i , A0i )
)
= a(a+ 1)(n− p) + n(a+ 1)δ′(c,G).
(4.3)
L. Abrams and L.-K. Lauderdale: Density results for Graovac-Pisanski’s distance number 251
Since
∣∣V (φac (G))∣∣ = n(1 + a + c), combining Equations (4.2) and (4.3) with Equa-
tion (4.1) yields
δ
(
φac (G)
)
=
(n− p)(a2 + a+ c) + n(a+ 1)δ′(c,G)
n(1 + a+ c)
,
as desired.
Consider the value of δ
(
φac (G)
)
given in Proposition 4.1 for a fixed graph G. The pa-
rameters a and c can be used to increase and decrease the value of δ
(
φac (G)
)
, respectively;
that is,
lim
a→∞
δ
(
φac (G)
)
= ∞ and lim
c→∞
δ
(
φac (G)
)
=
n− p
n
,
provided c and a are fixed, respectively. There are several infinite families of order-n
graphs whose GP distance numbers are equal to n−pn , where p is the number of vertex
orbits under the action of their respective automorphism groups. These families arise when
the induced subgraph on every vertex orbit is a clique; Example 2.2 demonstrates that
the complete graphs Kn comprise one such family. The following example establishes a
second such family of graphs that, in contrast, are not vertex-transitive under the action of
their respective automorphism groups.
Example 4.2. Let Zk denote the cyclic group of order k, where k ≥ 3. In this example, we
construct an infinite family of Zk-graphs, denoted by Gn; each graph Gn has order n = 6k
and p = 6 edge orbits under the action of Aut(Gn). We will prove that δ(Gn) = n−pn .
Define the order-7 gadget graph H with edge set
E(H) =
{
h0h1, h1h2, h1h4, h2h3, h2h5, h5h6
}
,
which is depicted in Figure 2(A). Let Ck denote the cycle graph of order k, and label its
edges so that vivi+1 ∈ E(Ck) for all i ∈ {0, 1, . . . , k − 2}. Replace each edge in Ck with
a copy of H , where the vertices vi and vi+1 are identified with h0 and h3, respectively; we
call the resulting graph H(k). The graph H(4) is illustrated in Figure 2(B). Observe that
H(k) is a Zk-graph with order n = 6k, which has six size-k vertex orbits under the action
of Aut
(
H(k)
)
.
Finally, we construct the graph Gn by including the 3(k − 1)k edges necessary to turn
each vertex orbit of H(k) into a clique. By design Gn is also a Zk-graph, where each of its
six edge orbits under the action of Aut(Gn) is a clique of order k. Its GP distance number
is
δ(Gn) =
n− 6
n
=
k − 1
k
,
as desired.
5 Proof of Theorem 1.1
In this section, we will prove our main result, Theorem 1.1. To do so, we make use of the
following proposition.
Proposition 5.1. Let Γ be a group, and suppose G is a nontrivial connected Γ-graph
with order n and p vertex orbits under the action of AutG. For any rational number
q ∈ (n−pn ,∞), there exist a, c ∈ N such that δ
(
φac (G)
)
= q.
252 Ars Math. Contemp. 21 (2021) #P2.05 / 243–257
h0
h1
h2
h3
h4
h5
h6
(a) The gadget graph H (b) The Z4-graph H(4)
Figure 2: Depictions of the graphs H and H(4), which were defined in Example 4.2.
Proof. Choose r, s ∈ N such that q = rs , and define
b := 2max
{
1,
⌈
nr − nsδ3(G)
(n− p)s
⌉}
.
Let
a :=
(
nr − (n− p)s
)
b− 1, (5.1)
and notice that a ≥ 0 because n−pn < q =
r
s . Now define
c := −
(
nr − (n− p)as− nsδ3(G)
)
b. (5.2)
Since G has order n, nδ3(G) is an integer, and thus c is as well. In fact, c ∈ N because the
inequality
a =
(
nr − (n− p)s
)
b− 1 ≥ b− 1 ≥ 1
2
b ≥ nr − nsδ3(G)
(n− p)s
implies that
nr − (n− p)as− nsδ3(G)
is nonpositive. Consequently, our choices of a and c are valid when considering the graph
φac (G), and since a ̸= 0, φac (G) is also a Γ-graph by Proposition 3.4. Proposition 4.1 then
implies that the GP distance number of φac (G) is
δ
(
φac (G)
)
=
(n− p)(a2 + a+ c) + n(a+ 1)δ′(c,G)
n(1 + a+ c)
.
A tedious algebraic computation shows that combining our choices of a and c
(
stated in
Equations (5.1) and (5.2)
)
with the equation above yields δ
(
φac (G)
)
= rs , as desired.
The equation δ
(
φac (G)
)
= q that appears in Proposition 5.1 does not have a unique
solution. In fact, taking any integer value of b greater than the one specified in the proof
will also yield a choice of a and c which satisfies the theorem. We now provide an example
showing that it is also possible to obtain smaller values of a and c which work.
L. Abrams and L.-K. Lauderdale: Density results for Graovac-Pisanski’s distance number 253
Example 5.2. Let G be K4 − e for any edge e of K4, in which case AutG ∼= Z2 × Z2
and δ(G) = 34 . Applying the proof of Proposition 5.1 with q =
4
5 , we obtain b = 2 and
then a = 11 and c = 218. However, we can in fact take b = 1 and still obtain a solution to
δ
(
φac (G)
)
= q, namely a = 5 and c = 49. The solution with the smallest possible values
of both a and c, not obtainable through the construction in that proof, is a = 1 and c = 3.
We conclude this section with a proof of our main result.
Proof of Theorem 1.1. Let the group Γ be given, and recall that
DΓ := {δ(G) : G is a Γ-graph}.
Frucht [3] proved that there exists a graph whose automorphism group is isomorphic to Γ;
among all such Γ-graphs G with order nG and with pG vertex orbits under the action of
AutG, choose G so that nG−pGnG is minimal. Under these assumptions, if G has order n
and p vertex orbits under the action of AutG, then
inf(DΓ) =
n− p
n
.
For each rational number q ∈ (inf(DΓ),∞), there exists a Γ-graph with GP distance num-
ber equal to q by Proposition 5.1. Consequently, DΓ is dense in (inf(DΓ),∞), as the
rational numbers are dense in this interval. The result now follows.
6 Graphs with connected vertex orbits
For a given group Γ, Theorem 1.1 proved that there was no maximum value of δ(G) among
all Γ-graphs; such arbitrarily large values of δ(G) were obtained from graphs with discon-
nected induced subgraphs on the vertex orbits of G under the action of AutG. If we
assume that the induced subgraph on every vertex orbit of G under the action of AutG
is connected, then we obtain a bounded interval of potential GP distance numbers. While
these stricter assumptions preserve density, we no longer can produce a graph with a given
GP distance number using a similar construction. We will conclude this article with a
result analogous to that of Theorem 1.1 which makes the aforementioned connectedness
assumption.
Let the group Γ be given. If a Γ-set V has size n, let GΓ,n denote any choice of a
connected graph on the Γ-set V which has a Γ-action compatible with the Γ-action on V
and has the maximum possible GP distance number among all such graphs. Note thatGΓ,n
need not be a Γ-graph. We use δΓ(GΓ,n) to denote the GP distance number obtained by
considering the Γ-action on GΓ,n rather than the action of Aut(GΓ,n).
Suppose now that G is a Γ-graph with p orbits V0, V1, . . . , Vp−1 of sizes n0, n1, . . . ,
np−1, respectively. Each orbit itself has a Γ-action, so we consider the graphs GΓ,n0 , . . . ,
GΓ,np−1 ; let ĜΓ denote GΓ,n0 ⊔ · · · ⊔GΓ,np−1 , where ⊔ denotes disjoint union. Define
δ̂(G) :=
1
n0 + · · ·+ np−1
p−1∑
i=0
niδΓ(GΓ,ni);
δ̂(G) is the maximum possible GP distance number relative to Γ for all graphs with a
Γ-action and vertex set the Γ-set V (G). Note, however, that Aut(ĜΓ) may contain an
isomorphic copy of Γ as a proper subgroup.
254 Ars Math. Contemp. 21 (2021) #P2.05 / 243–257
Definition 6.1. Let Γ be a group, and supposeG is a Γ-graph with vertices u00, u01, . . . , u0n−1
and vertex orbits V0, V1, . . . , Vp−1. Without loss of generality, we assume that u0i ∈ Vi for
each i ∈ {0, 1, . . . , p − 1}. We define a new graph φ̂ac (G) iteratively with respect to the
natural numbers c and a as follows. Given φ̂ac (G), define φ̂
a+1
c (G) to be the graph obtained
by carrying out the following steps:
1. introduce new vertices ua+10 , u
a+1
1 , . . . , u
a+1
n−1; we refer to these vertices as being in
“level a+ 1”;
2. connect these new vertices with new edges uai u
a+1
i for each i ∈ {0, 1, . . . , n − 1};
and
3. for each orbit Vi, add new edges to build a copy of the Γ-graph GΓ,|Vi| on the orbit
of vertices in level a+ 1 corresponding to the Γ-set Vi.
Given φ̂ac (G), let w
0
i := u
0
i for each i ∈ {0, 1, . . . , n− 1}. Define φ̂ac+1(G) by connecting
an n-clique on new vertices wc+1i with new edges w
c
iw
c+1
i for each i ∈ {0, 1, . . . , n− 1}.
Note that, under the Γ-action, we have enhanced G with cp orbits whose induced sub-
graphs are cliques and with ap orbits whose induced subgraphs are disjoint unions of con-
nected GP-distance-number-maximizing graphs.
Let G be a Γ-graph for a given group Γ. The following proposition shows that φ̂ac (G)
is also a Γ-graph in most cases. We omit its proof, which is similar to the proof of Propo-
sition 3.4.
Proposition 6.2. Let Γ be a group, and suppose G is a nontrivial connected Γ-graph that
is not complete. If either c ̸= 0 or G ̸∼= ĜΓ, then φ̂ac (G) is also a Γ-graph.
We now present our result analogous to Theorem 1.1 that makes an assumption on the
connectedness of graphs.
Theorem 6.3. Let Γ be a group. If G is a connected Γ-graph of order n having p vertex
orbits, each of which induces a connected subgraph of G, then{
δ
(
φ̂ac (G)
)
| a, c ∈ N and φ̂ac (G) is a Γ-graph
}
is dense in
(
n−p
n , δ̂(G)
)
.
Proof. Given any ϵ > 0 and any q ∈
(
n−p
n , δ̂(G)
)
, it suffices to find a′, c′ ∈ N such that∣∣∣q − δ (φ̂a′c′ (G))∣∣∣ < ϵ. We first determine an expression for δ (φ̂ac (G)), and then explain
how to choose a′ and c′.
Let V0, V1, . . . , Vp−1 be the Γ-orbits in V (G). For each Vi, there are a + c associated
vertex orbits of φ̂ac (G) under the action of Aut
(
φ̂ac (G)
)
; for i ∈ {0, 1, . . . , p − 1}, label
these orbits by A1i , A
2
i , . . . , A
a
i and C
1
i , C
2
i , . . . , C
c
i , where u
j
i ∈ A
j
i for j ∈ {1, 2, . . . , a}
and wki ∈ Cki for k ∈ {1, 2, . . . , c}. For X ∈ {G, ĜΓ}, let dX denote the distance function
inX , and let dX,3 denote the function given by min(dX(u, v), 3) for vertices u, v ∈ V (X).
Write d′G = dG for c = 0 and d
′
G = dG,3 for c ≥ 1.
For each i ∈ {0, 1, . . . , p−1} and any k, any two distinct vertices in Cki are at distance
1 from each other. Choosing a representative in each orbit Ck1 , C
k
2 , . . . , C
k
p−1, we find that
the total distance over all the orbits in level k is
p−1∑
i=0
(|Cki | − 1) = n− p.
L. Abrams and L.-K. Lauderdale: Density results for Graovac-Pisanski’s distance number 255
For i ∈ {0, 1, . . . , p − 1} and any j, a shortest path between any two vertices ujℓ , ujm
in Aji is either a shortest path in layer j, or is a path obtained by concatenating a shortest
ujℓ , u
0
ℓ -path and a shortest u
0
m, u
j
m-path with a shortest u
0
ℓ , u
0
m-path in G if c = 0 and with
a shortest u0ℓ , u
0
m-path in φ̂
0
1(G) if c > 0. Thus, the length of a shortest u
j
ℓ , u
j
m-path is
min
{
dĜΓ
(
ujℓ , u
j
m
)
, 2j + d′G
(
u0ℓ , u
0
m
)}
.
Writing diam(X) for the length of a longest path in graph X , if j ≥ diam(ĜΓ)/2 then we
have
min
{
dĜΓ
(
u0ℓ , u
0
m
)
, 2j + d′G
(
u0ℓ , u
0
m
)}
= dĜΓ
(
u0ℓ , u
0
m
)
.
Note that, to prove the result, it suffices to presume that a > diam(ĜΓ)/2. Choosing a rep-
resentative in each orbit, we can calculate the total distance for levels 0 to
⌈
diam(ĜΓ)/2
⌉
;
write D for this value. Also, for each j >
⌈
diam(ĜΓ)/2
⌉
, the total distance in level j is
nδ̂(G). Thus, we have
δ
(
φ̂ac (G)
)
=
(n− p)c+D +
(
a−
⌈
diam(ĜΓ)/2
⌉)
nδ̂(G)
(1 + a+ c)n
.
In order to choose appropriate a and c, observe first that, for any positive a, c ∈ N, we
have
δ
(
φ̂ac−1(G)
)
− δ
(
φ̂ac (G)
)
=
D +
(
a−
⌈
diam(ĜΓ)/2
⌉)
nδ̂(G)− (n− p)(a+ 1)
(a+ c)(1 + a+ c)n
<
D + anδ̂(G)
(a+ c)2n
.
Let ∆(a, c) denote this upper bound, and note that ∆(a, c) has negative derivative with
respect to both a and to c.
We now choose a′ and c′. Since
lim
a→∞
δ(φ̂a0(G)) = δ̂(G) > q,
we can choose a′ ∈ N so that a′ >
⌈
diam(ĜΓ)/2
⌉
, ∆(a′, 0) < ϵ, and δ
(
φ̂a
′
0 (G)
)
> q.
Because
lim
c→∞
δ
(
φ̂a
′
c (G)
)
=
n− p
n
< q
we can then choose
c′ := min
{
c ∈ N
∣∣δ(φ̂a′c (G)) ≤ q} .
Observe that c′ > 0 because we have chosen a′ to ensure that δ
(
φ̂a
′
0 (G)
)
> q. Since
δ
(
φ̂a
′
c′ (G)
)
< q ≤ δ
(
φ̂a
′
c′−1(G)
)
,
we have
q − δ
(
φ̂a
′
c′ (G)
)
< ∆(a′, c′) < ∆(a′, 0) < ϵ,
as desired. Furthermore, since c′ > 0, Proposition 6.2 guarantees that φ̂a
′
c′ (G) is a Γ-
graph.
256 Ars Math. Contemp. 21 (2021) #P2.05 / 243–257
Let Γ be a group, and suppose G is a connected Γ-graph of order n with p vertex orbits
under the action of AutG. If the induced subgraph on each vertex orbit of G is connected,
then we claim that there exists infinitely many rational numbers in
(
n−p
n , δ̂(G)
)
that are
not the GP distance numbers of graphs of the form φ̂ac (G). We demonstrate our claim with
the following example.
Example 6.4. LetG be the graph constructed from an 8-cycle on vertices u00, u01, u02, . . . , u07
and a 4-cycle on vertices u08, u
0
9, u
0
10, u
0
11, by including edges
u00u
0
8, u
0
1u
0
8, u
0
2u
0
9, u
0
3u
0
9, u
0
4u
0
10, u
0
5u
0
10, u
0
6u
0
11, and u
0
7u
0
11.
The graph G, which is illustrated in Figure 3, is a D8-graph with two vertex orbits under
the action of AutG (here D8 denotes the dihedral group of order 8).
u00
u01u
0
2
u03
u04
u05 u
0
6
u07
u08u
0
9
u010 u
0
11
Figure 3: The D8-graph G constructed in Example 6.4.
Observe that ĜD8 is equal to C8 ⊔ C4. Moreover, δ(G) = 2012 = δ̂(G), and thus The-
orem 6.3 established that
{
δ
(
φ̂ac (G)
)
| a, c ∈ N
}
is dense in the interval
(
5
6 ,
5
3
)
. Observe
that
δ
(
φ̂ac (G)
)
=

20
12
if c = 0
19 + 20a+ 10c
12(1 + a+ c)
if c ̸= 0,
and suppose δ
(
φ̂ac (G)
)
= rs for some
r
s ∈
(
5
6 ,
5
3
)
. Solving for c in the case when c > 0 we
obtain
c =
(20s− 12r)a+ 19s− 12r
12r − 10s
.
Notice that if s is odd, then the numerator of this expression for c is odd whereas the
denominator is even, and thus this value of c is not an integer. It follows that s is even, so
no rational number in reduced form with an odd denominator is δ
(
φ̂ac (G)
)
for any values
of a and c. Finally, the reader may be entertained by the observation that both the set of GP
distance numbers and non-GP distance numbers in
(
5
6 ,
5
3
)
are dense.
ORCID iDs
Lowell Abrams https://orcid.org/0000-0002-8174-5957
L. Abrams and L.-K. Lauderdale: Density results for Graovac-Pisanski’s distance number 257
References
[1] 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.
[2] D. Bonchev and N. Trinajstić, Information theory, distance matrix, and molecular branching, J.
Chem. Phys. 67 (1977), 4517–4533, doi:10.1063/1.434593.
[3] R. Frucht, Herstellung von Graphen mit vorgegebener abstrakter Gruppe, Compositio Math. 6
(1939), 239–250, http://www.numdam.org/item?id=CM_1939__6__239_0.
[4] A. Graovac and T. Pisanski, On the Wiener index of a graph, J. Math. Chem. 8 (1991), 53–62,
doi:10.1007/bf01166923, mathematical chemistry and computation (Dubrovnik, 1990).
[5] I. Gutman and T. Körtvélyesi, Wiener indices and molecular surfaces, Z. Naturforsch. 50
(1995), 669–671, doi:10.1515/zna-1995-0707.
[6] I. Gutman and O. E. Polansky, Wiener numbers of polyacenes and related benzenoid molecules,
Match 20 (1986), 115–123, https://match.pmf.kg.ac.rs/content20.htm.
[7] M. A. Iranmanesh and H. Shabani, The symmetry-moderated Wiener index of truncation graph,
Thorn graph and caterpillars, Discrete Appl. Math. 269 (2019), 41–51, doi:10.1016/j.dam.2018.
05.040.
[8] M. Knor, J. Komornı́k, R. Škrekovski and A. Tepeh, Unicyclic graphs with the maximal value
of Graovac-Pisanski index, Ars Math. Contemp. 17 (2019), 455–466, doi:10.26493/1855-3974.
1925.57a.
[9] M. Knor, R. Škrekovski and A. Tepeh, Chemical graphs with the minimum value of Wiener
index, Match Commun. Math. Comput. Chem. 81 (2019), 119–132, https://match.pmf.
kg.ac.rs/content81n1.htm.
[10] 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.
[11] B. Mohar and T. Pisanski, How to compute the Wiener index of a graph, J. Math. Chem. 2
(1988), 267–277, doi:10.1007/bf01167206.
[12] R. Pinal, Effect of molecular symmetry on melting temperature and solubility, Org. Biomol.
Chem. 2 (2004), 2692–2699, doi:10.1039/b407105k.
[13] H. Wiener, Correlation of heats of isomerization, and differences in heats of vaporization of
isomers, among the paraffin hydrocarbons, J. Am. Chem. Soc. 69 (1947), 2636–2638, doi:
10.1021/ja01203a022.
[14] H. Wiener, Structural determination of paraffin boiling points, J. Am. Chem. Soc. 69 (1947),
17–20, doi:doi.org/10.1021/ja01193a005.