ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 25 (2025) #P2.01
https://doi.org/10.26493/1855-3974.3085.3ea
(Also available at http://amc-journal.eu)
On regular graphs with Šoltés vertices*
Nino Bašić †
FAMNIT, University of Primorska, Koper, Slovenia and
IAM, University of Primorska, Koper, Slovenia and
Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia
Martin Knor ‡
Slovak University of Technology in Bratislava, Slovakia
Riste Škrekovski
FAMNIT, University of Primorska, Koper, Slovenia and
Faculty of Mathematics and Physics, University of Ljubljana, Slovenia and
Faculty of Information Studies, Novo mesto, Slovenia and
Rudolfovo - Science and Technology Centre Novo Mesto, Slovenia
Received 13 March 2023, accepted 4 March 2024, published online 10 March 2025
Abstract
Let W (G) be the Wiener index of a graph G. We say that a vertex v ∈ V (G) is a Šoltés
vertex in G if W (G − v) = W (G), i.e. the Wiener index does not change if the vertex
v is removed. In 1991, Šoltés posed the problem of identifying all connected graphs G
with the property that all vertices of G are Šoltés vertices. The only such graph known to
this day is C11. As the original problem appears to be too challenging, several relaxations
were studied: one may look for graphs with at least k Šoltes vertices; or one may look
for α-Šoltés graphs, i.e. graphs where the ratio between the number of Šoltés vertices and
the order of the graph is at least α. Note that the original problem is, in fact, to find all
1-Šoltés graphs. We intuitively believe that every 1-Šoltés graph has to be regular and has
to possess a high degree of symmetry. Therefore, we are interested in regular graphs that
contain one or more Šoltés vertices. In this paper, we present several partial results. For
every r ≥ 1 we describe a construction of an infinite family of cubic 2-connected graphs
with at least 2r Šoltés vertices. Moreover, we report that a computer search on publicly
*The second and third authors acknowledge partial support of the Slovenian research agency ARRS; program
P1-0383 and ARRS project J1-3002, and the annual work program of Rudolfovo.
†Corresponding author. The author is supported in part by the Slovenian Research Agency (research program
P1-0294 and research projects J1-1691, N1-0140, and J1-2481).
‡The author acknowledges partial support by Slovak research grants VEGA 1/0069/23, VEGA 1/0011/25,
APVV-23-0076 and APVV-22-0005.
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
2 Ars Math. Contemp. 25 (2025) #P2.01
available collections of vertex-transitive graphs did not reveal any 1-Šoltés graph. We are
only able to provide examples of large 13 -Šoltés graphs that are obtained by truncating
certain cubic vertex-transitive graphs. This leads us to believe that no 1-Šoltés graph other
than C11 exists.
Keywords: Šoltés problem, Wiener index, regular graph, cubic graph, Cayley graph, Šoltés vertex.
Math. Subj. Class. (2020): 05C12, 05C90, 20B25
1 Introduction
All graphs under consideration in this paper are simple and undirected. The Wiener index
of a graph G, denoted by W (G), is defined as
W (G) =
1
2
∑
u∈V (G)
∑
v∈V (G)
dG(u, v) =
∑
{u,v}⊆V (G)
dG(u, v), (1.1)
where dG(u, v) is the distance between vertices u and v (i.e. the length of a shortest path
between u and v). If the graph G is disconnected, we may take W (G) = ∞. The Wiener
index was introduced in 1947 [16] and has been extensively studied ever since. For a recent
survey on the Wiener index see [9]. The transmission of a vertex v in a graph G, denoted by
wG(v), is defined as wG(v) =
∑
u∈V (G) dG(u, v). Note that (1.1) can also be expressed
as W (G) = 12
∑
u∈V (G) wG(u).
Let v ∈ V (G). The graph obtaned from G by removing a vertex v is denoted by G−v.
If we remove a vertex v from a graph G, any of the following scenarios may occur:
(a) the Wiener index decreases (e.g. W (K7) = 21 and W (K7 − v) = W (K6) = 15);
(b) the Wiener index increases (e.g. W (Wh9) = 56 and W (Wh9−v0) = W (C8) = 64,
where Whn denotes the wheel graph on n vertices and v0 is the central vertex of the
wheel);
(c) the Wiener index does not change (e.g. W (Wh8) = 42 and W (Wh8 − v0) =
W (C7) = 42, where v0 is the central vertex of Wh8).
We say that a vertex v ∈ V (G) is a Šoltés vertex of G if W (G) = W (G − v), i.e. the
Wiener index of G does not change if the vertex v is removed. If G is disconnected, with
two non-trivial components or with at least three components, then every vertex is a Šoltés
vertex. Therefore, it is natural to require that G is connected. Let
S(G) = {v ∈ V (G) | W (G) = W (G− v)}
and let 0 ≤ α ≤ 1. We say that a graph G is an α-Šoltés graph if |S(G)| ≥ α|V (G)|,
i.e. the ratio between the number of Šoltés vertices of G and the order of G is at least α.
For example, the graph in Figure 1 is the smallest cubic 13 -Šoltés graph. Note that G is an
1-Šoltés graph if every vertex in G is a Šoltés vertex. The only 1-Šoltés graph known to
this day is the cycle on 11 vertices, C11. In this paper, Šoltés graph is simply the synonym
for 1-Šoltés graph.
E-mail addresses: nino.basic@famnit.upr.si (Nino Bašić), martin.knor@stuba.sk (Martin Knor),
riste.skrekovski@fmf.uni-lj.si (Riste Škrekovski)
N. Bašić et al.: On regular graphs with Šoltés vertices 3
The Šoltés problem [15] was forgotten for nearly three decades. It was revived and
popularised in 2018 by Knor et al. [7]. They considered a relaxation of the original prob-
lem: one may look for graphs with a prescribed number of Šoltés vertices. They showed
that there exists a unicyclic graph on n vertices with at least one Šoltés vertex for every
n ≥ 9. They also showed that there exists a unicyclic graph with a cycle of length c and
at least one Šoltés vertex for every c ≥ 5, and that every graph is an induced subgraph of
some larger graph with a Šoltés vertex. They have further shown that a Šoltés vertex in
a graph may have a prescribed degree [8]. Namely, they proved that for any d ≥ 3 there
exist infinitely many graphs with a Šoltés vertex of degree d. Necessary conditions for the
existence of Šoltés vertices in Cartesian products of graphs were also considered [8]. In
2021, Bok et al. [3] showed that for every k ≥ 1 there exist infinitely many cactus graphs
with exactly k distinct Šoltés vertices. In 2021, Hu et al. [6] studied a variation of the prob-
lem and showed that there exist infinitely many graphs where the Wiener index remains the
same even if r ≥ 2 distinct vertices are removed from the graph.
Akhmejanova et al. [1] considered another possible relaxation of the problem: Do there
exist graphs with a given percentage of Šoltés vertices? They constructed two infinite
families of graphs with a relatively high proportion of Šoltés vertices. Their first family
comprises graphs B(k), k ≥ 2, where B(k) is a 2k5k+6 -Šoltés graph on 5k + 6 vertices.
Two vertices of B(k) are of degree k + 1, while the remaining vertices are of degree 2.
The percentage of Šoltés vertices is below 25 , but tends to
2
5 as k goes to infinity. They
also introduced a two-parametric infinite family L(k,m), m ≥ 7 and k ≥ m−3m−6 . Here,
the percentage of Šoltés vertices is below 12 , but tends to
1
2 as k goes to infinity for a fixed
m. These graphs contain at least one leaf, at least km vertices of degree 2, and a vertex of
degree km+ 1.
In the present paper we focus on regular graphs. Our intuition lead us to believe that
the solutions to the original Šoltés problem should be graphs having all vertices of the same
degree.
Conjecture 1.1. If G is a Šoltés graph, then G is regular.
For a general regular graph G, the values W (G − u) and W (G − v) might be signifi-
cantly different for two different vertices u, v ∈ V (G); it may happen that removal of one
vertex increases the Wiener index, while removal of the other vertex descreases the Wiener
index. However, W (G−u) and W (G−v) are equal if vertices u and v belong to the same
vertex orbit. Therefore, we believe that a Šoltés graph is likely to be vertex transitive.
Conjecture 1.2. If G is a Šoltés graph, then G is vertex transitive.
Figure 1: The smallest cubic 13 -Šoltés graph has 24 vertices. Its Šoltés vertices are coloured
red.
4 Ars Math. Contemp. 25 (2025) #P2.01
Among truncations of cubic vertex-transitive graphs we found several 13 -Šoltés graphs;
see Section 4. Interestingly, all our examples are in fact Cayley graphs and this leads us to
pose the following conjecture.
Conjecture 1.3. If G is a Šoltés graph, then G is a Cayley graph.
It is not hard to obtain small examples of regular graphs with Šoltés vertices. We used
the geng [11] software to generate small k-regular graphs (for k = 3, 4 and 5). Let Rr
denote the class of all r-regular graphs and let Rrn denote the set of r-regular graphs on n
vertices. Let N(G, k) be the number of graphs in the class G that contain exactly k Šoltés
vertices.
Table 1 shows the numbers of (non-isomorphic) cubic graphs of orders n ≤ 24 that
contain Šoltés vertices. We can see that cubic graphs of order 12 or less do not contain
Šoltés vertices. There are plenty of examples with one Šoltés vertex. Cubic graphs with two
Šoltés vertices first appear at order n = 14; there are three such graphs (see Figure 2(a)–
(c)). Examples with three and four Šoltés vertices appear at order n = 16; there is one
cubic graph with three and two cubic graphs with four Šoltés vertices (see Figure 2(d)–
(f)). At order n = 18, there are no graphs with three Šoltés vertices, however there is
only one graph with four Šoltés vertices (see Figure 2(g)). Numbers of 4-regular and 5-
regular graphs with respect to their number of Šoltés vertices are given in Tables 2 and 3,
respectively.
N(R3n, k)
n |R3n| k = 1 k = 2 k = 3 k = 4 k = 5 k = 6 k = 7 k = 8
≤ 12 112 - - - - - - - -
14 509 4 3 - - - - - -
16 4060 108 37 1 2 - - - -
18 41301 1014 200 - 1 - - - -
20 510489 13460 1076 6 13 - - - -
22 7319447 194432 9610 151 52 - 1 - -
24 117940535 3161124 130087 2596 333 2 3 - 1
Table 1: The numbers of (non-isomorphic) cubic graphs with Šoltés vertices. There are no
graphs with Šoltés vertices for orders up to 12. The column labeled |R3n| gives the total
number of cubic graphs of order n. Symbol ‘-’ is a replacement for 0 (i.e. no such graph
exists). Each of the next columns gives the numbers of graphs with k Šoltés vertices for
k = 1, 2, . . . , 8. A blue-coloured number means that we have provided drawings of these
graphs (see Figures 1 and 2).
In the next two sections we construct an infinite family of cubic 2-connected graphs
with at least 2r, r ≥ 1, Šoltés vertices. It recently came to our attention that Dobrynin in-
dependently found an infinite family of cubic graphs with four Šoltés vertices [4]. However,
our method is more general.
N. Bašić et al.: On regular graphs with Šoltés vertices 5
N(R4n, k)
n |R4n| k = 1 k = 2 k = 3 k = 4
≤ 12 1894 - - - -
13 10778 - 1 - -
14 88168 30 6 - -
15 805491 265 85 - 5
16 8037418 2191 472 - -
17 86221634 14430 2097 4 1
Table 2: The numbers of (non-isomorphic) quartic graphs of orders up to 17 with Šoltés
vertices. Naming conventions used in Table 1 also apply here.
N(R5n, k)
n |R5n| k = 1 k = 2 k = 3 k = 4
≤ 12 7912 - - - -
14 3459383 8 3 - -
Table 3: The numbers of (non-isomorphic) quintic graphs of order up to 14 with Šoltés
vertices. Naming conventions used in Table 1 also apply here.
(a) (b) (c) (d) (e)
(f) (g) (h)
Figure 2: Examples of small regular graphs with two or more Šoltés vertices: (a) to (c) are
the three cubic graphs of order 14 with two Šoltés vertices; (d) and (e) are the two cubic
graphs of order 16 with four Šoltés vertices; (f) is the only cubic graph of order 16 with
three Šoltés vertices; (g) is the only cubic graph of order 18 with four Šoltés vertices; (h)
is the only quartic graph of order 13 with two Šoltés vertices. Šoltés vertices are coloured
red.
6 Ars Math. Contemp. 25 (2025) #P2.01
2 Cubic 2-connected graphs with two Šoltés vertices
In the present section we prove the following result.
Theorem 2.1. There exist infinitely many cubic 2-connected graphs G which contain at
least two Šoltés vertices.
We prove Theorem 2.1 by a sequence of lemmas. We start by giving several definitions.
First, we define a graph Gt on 8t+ 8 vertices, where t ≥ 1. Take 2t copies of the diamond
graph (i.e. K4 − e) and connect their degree-2 vertices, so that a ring of 2t copies of
K4 − e is formed. Add a disjoint 4-cycle to that graph. Then subdivide one of the edges
that connects two consecutive diamonds by two vertices, denote them by z1 and z2, and
connect z1 and z2 with two opposite vertices of the 4-cycle. Add a leaf to each remaning
degree-2 vertex of the 4-cycle. Denote the resulting graph by Gt. For an illustration,
see G3 in Figure 3. Note that Gt has exactly two leaves, denote them by v1 and v2, and
all the remaining vertices have degree 3. Denote by u1 and u2 the two vertices at the
longest distance from v1. This distance is dG(v1, u1) = dG(v1, u2) = 3t + 3 and also
dG(v2, u1) = dG(v2, u2) = 3t + 3. Observe that Gt has an automorphism (a symmetry)
fixing both v1 and v2, while interchanging u1 with u2.
u1
u2
z1
z2
v1
v2
Figure 3: The graph G3.
Now, we determine f(t) = W (Gt − u1)−W (Gt). We compute f(t) by summing the
contributions of all vertices (first the contribution of quadruples of vertices of all copies of
K4 − e, and then the contribution of the vertices which are not in any copy of K4 − e). As
the calculation is long and tedious, we present just the result
f(t) = 16t3 − 8t2 − 26t− 14, (2.1)
which was checked by a computer. Actually, the exact value of f(t) is not important here.
The crucial property is that for t big enough, f(t) is positive. In fact, limt→∞ f(t) = ∞;
see also Section 3, where a lower bound for f(t) is given.
To motivate the above definition, we briefly describe the main idea of the proof. We
attach trees T1 and T2 to vertices v1 and v2 of Gt, and then we add edges to them so that
the resulting graph H will be cubic and 2-connected. See Figure 4 for an example. This
will be done in three phases.
N. Bašić et al.: On regular graphs with Šoltés vertices 7
P1) In the first phase, we will construct trees T1 and T2 to guarantee that vertices u1
and u2 are indeed Šoltés vertices. The vertices of T1 and T2 can be partitioned into
several layers based on their distance to v1 and v2, respectively. The resulting graph
will be denoted by Q.
P2) In the second phase, we will add the ‘red’ edges, whose endpoints are in two consec-
utive layers, to graph Q. The resulting graph will be denoted by R. The purpose of
the second phase is to make sure that the sum of free valencies is even within each
layer, making the next phase possible. Note that although the final graph H is cubic,
the intermediate graphs, Q and R, are subcubic. The free valency of a vertex v in a
subcubic graph G is 3− degG(v).
P3) In the last phase, we will add blue edges to R in order to to obtain cycles and paths,
so that the resulting graph H will be cubic and 2-connected. The endpoints of ‘blue’
edges will reside in the same layer of the forest T1 ∪ T2. Adding ‘red’ and ‘blue’
edges has no influence on Šoltésness of u1 and u2.
u1
u2
v1
v2
Figure 4: A graph H with two Šoltés vertices, namely u1 and u2, that contains G3.
Let us consider the resulting graph H . Observe that if x ∈ V (H) \ V (Gt), then we
have wH(x) − wH−u1(x) = dH(u1, x). Clearly, every (u1, x)-path contains one of the
vertices from {v1, v2}. Hence, for calculating W (H) −W (H − u1), only the distance of
the new vertices x to {v1, v2} matters.
We need to find suitable trees T1 and T2 rooted at v1 and v2, respectively. Each of
these trees will have q vertices and their depth, say d, will be determined later. What next
properties do T1 and T2 need to have? Let ℓi be the number of vertices of the forest T1∪T2
at distance i, 1 ≤ i ≤ d, from {v1, v2}. Since the resulting graph will be cubic and 2-
connected, we have 2 ≤ ℓ1 ≤ 4, 2 ≤ ℓ2 ≤ 8, 2 ≤ ℓ3 ≤ 24, . . . and for the last value ℓd
we have 1 ≤ ℓd ≤ 2d+1. The trees attached to v1 and v2 may be paths in which case we
get ℓ1 = ℓ2 = · · · = ℓq = 2 (since each of T1 and T2 have exactly q vertices). In this case
the transmission of vj in Tj is biggest possible, 1 ≤ j ≤ 2. In the other extremal situation
the transmission of vj in Tj is smallest possible, 1 ≤ j ≤ 2, which results in ℓi = 2i+1,
1 ≤ i < d. If x ∈ V (H)\V (Gt) is at distance i from {v1, v2}, then dH(u1, x) = 3t+3+i.
8 Ars Math. Contemp. 25 (2025) #P2.01
Denote by D the sum of distances from all vertices of V (H) \ V (Gt) to u1. Then
D =
d∑
i=1
(3t+ 3 + i)ℓi. (2.2)
Observe that we need to find a finite sequence (ℓ1, ℓ2, . . . , ℓd) so that f(t) = D. As the
resulting graph H has to be cubic, we need to add an even number of vertices, 2q, to the
graph Gt. What are the bounds for D?
First, we determine the lower bound; let us denote it by Dm. This bound will be
obtained when ℓi attains the maximum possible value of 2i+1 for every 1 ≤ i ≤ d− 1. In
other words, we are attaching complete binary trees to v1 and v2. Let a = ⌊log2(2q + 3)⌋.
Recall that the depth of a complete binary tree with n vertices is ⌊log2(n)⌋ and note that in
our case a− 1 = d. Then
ℓ1 = 4,
ℓ2 = 8,
...
ℓa−2 = 2
a−1,
ℓa−1 = 2q −
a−2∑
i=1
ℓi = 2q − 2a + 4.
The above sequence will be called the short sequence and denoted by Lm. Using the
formula
∑a
i=1 ix
i−1 = (axa+1 − (a+ 1)xa + 1)/(x− 1)2, we get
Dm =
a−2∑
i=1
(3t+ 3 + i)2i+1 + (3t+ a+ 2)(2q − 2a + 4)
= (3t+ 1)2q +
a−2∑
i=1
(i+ 2)2i+1 + (a+ 1)(2q − 2a + 4) + 2 · 21 + 1 · 20 − 5
= (3t+ 1)2q +
a∑
i=1
i2i−1 + (a+ 1)(2q − 2a + 4)− 5
= (3t+ 1)2q + a2a+1 − (a+ 1)2a + 1 + (a+ 1)2q − (a+ 1)2a + 4(a+ 1)− 5
= (3t+ 1)2q + a2a+1 − (a+ 1)2a+1 + (a+ 1)2q + 4a
= (3t+ 1)2q − 2a+1 + (a+ 1)2q + 4a.
(2.3)
Now we find the upper bound Dm for D. In this case ℓ1 = ℓ2 = · · · = ℓq = 2; this
sequence will be called the long sequence and denoted by Lm. Therefore,
Dm = 2(3t+ 4) + 2(3t+ 5) + · · ·+ 2(3t+ 3 + q)
= (3t+ 3)2q + 2
q∑
i=1
i
= (3t+ 1)2q + q2 + 5q.
(2.4)
Note that Dm and Dm are functions of q and t.
N. Bašić et al.: On regular graphs with Šoltés vertices 9
t 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
qmin 9 17 27 38 50 64 78 94 110 128 146 165 185 205 227 249
qmax 9 21 38 59 85 116 152 192 238 288 344 405 471 542 617 698
t 19 20 21 22 23 24 25 26 27 28 29 30 31
qmin 272 295 319 344 370 396 422 450 478 506 535 565 595
qmax 785 876 973 1075 1182 1294 1411 1533 1661 1795 1933 2077 2225
Table 4: The minimum and maximum value of q which satisfy the condition of Lemma 2.2.
Lemma 2.2. Let t ≥ 3. Then there exists q, such that Dm ≤ f(t) ≤ Dm.
Proof. Observe that if q ∼ 4t
√
t then we have Dm ≤ f(t) ≤ Dm for large enough t.
For small values of t we computed the minimum and maximum value of q that satisfies the
condition of the lemma; see Table 4.
Note that the value q in Lemma 2.2 is uniquely determined only for t = 3. For larger
values of t we get a range of options. Any q between qmin and qmax can be used. Moreover,
different values of q lead to non-isomorphic graphs H .
Now, we show that for every integer D, Dm ≤ D ≤ Dm, there exists a finite sequence
(ℓ1, ℓ2, . . . , ℓd) which realises D. Moreover, the graph Gt can be extended to H by at-
taching trees T1 and T2 that have ℓi vertices at distance i from {v1, v2}, such that H is a
2-connected cubic graph.
Let us define an operation M that modifies one such sequence L = (ℓ1, ℓ2, . . . , ℓd).
Definition 2.3. Let L = (ℓ1, ℓ2, . . . , ℓd). Set ℓd+1 = 0. Let i be the smallest value such
that ℓi ≥ 3 and either
(i) 2(ℓi − 1) > ℓi+1 + 1 or
(ii) ℓi = ℓi+1 = 3.
We say that M(L) = (ℓ′1, ℓ′2, . . . , ℓ′d) is a modification of sequence L if ℓ′j = ℓj for all j,
1 ≤ j ≤ d+ 1, except for j ∈ {i, i+ 1}, for which ℓ′i = ℓi − 1 and ℓ′i+1 = ℓi+1 + 1.
Lemma 2.4. Let t ≥ 1 and q ≥ 0. For every D, Dm ≤ D ≤ Dm, there exists a finite
sequence L = (ℓ1, ℓ2, . . . , ℓd), such that
(i)
∑d
i=1 ℓi = 2q;
(ii) 2 ≤ ℓi ≤ 2i+1 for i < d and 1 ≤ ℓd ≤ 2d+1;
(iii) ℓi+1 ≤ 2ℓi.
Namely, L = MD−Dm(Lm).
Proof. We start with the short sequence Lm = (4, 8, 16, . . . ). It clearly satisfies condi-
tions (i) to (iii). We have already seen that Lm realises Dm. This established the base of
induction.
Every other D can be realised by a sequence that is obtained from Lm by iteratively
applying operation M. Assume that after (D − 1) −Dm steps we obtained the sequence
L = (ℓ1, ℓ2, . . . , ℓd) which realises D−1. Obviously, M(L) realises D. It is easy to check
that conditions (i) to (iii) are satisfied for M(L).
10 Ars Math. Contemp. 25 (2025) #P2.01
Next, we prove two additional properties that hold when operation M is iteratively
applied on Lm.
Lemma 2.5. Let t ≥ 1 and q ≥ 0. Let L = (ℓ1, ℓ2, . . . , ℓd) be obtained from Lm by
iteratively applying operation M. Then the following holds:
(i) If (ii) of Definition 2.3 applies, then ℓj = 2 for all j < i.
(ii) If index i in Definition 2.3 is such that ℓi+1 = 0, then ℓi ≥ 4.
Proof. (i): Observe that if part (ii) of Definition 2.3 applies and i ≥ 2, then ℓi−1 = 2, since
otherwise i − 1 satisfies the assumption of the definition, thus i is not the smallest such
value. Moreover, if there is k, k < i, with ℓk ≥ 3, then choose the largest possible k with
this property. Then ℓk+1 = ℓk+2 = · · · = ℓi−1 = 2. Hence, k satisfies the assumption
of the definition, a contradiction. It means that if part (ii) of the definition applies, then
ℓi−1 = ℓi−2 = · · · = ℓ1 = 2.
(ii): If ℓi+1 = 0 then clearly ℓi ≥ 3. Suppose that ℓi = 3. Then ℓi−1 = 2, since
otherwise the assumptions apply to i − 1. As 2q is even, there must be k < i such that
ℓk ≥ 3. Let k be the largest possible value with this property. Then the assumptions apply
to k, a contradiction. Thus, if ℓi+1 = 0 then ℓi ≥ 4.
Note that part (ii) of Lemma 2.5 means that in the sequence L′ = M(L), ℓ′i ≥ 3 and
ℓ′i+1 = 1. The corresponding graph H will thus have a single vertex of degree 3 in the final
layer.
Example 2.6. For an illustration, the sequence of sequences
Lm, M(Lm), M2(Lm), M3(Lm), . . .
for 2q = 20 is
(4, 8, 8), (4, 5, 6, 5), (3, 4, 5, 6, 2), (2, 3, 4, 7, 4), (2, 2, 3, 5, 7, 1),
(4, 7, 9), (4, 4, 7, 5), (3, 4, 4, 7, 2), (2, 3, 4, 6, 5), (2, 2, 3, 5, 6, 2),
(4, 6, 10), (3, 5, 7, 5), (3, 3, 5, 7, 2), (2, 3, 4, 5, 6), (2, 2, 3, 4, 7, 2),
(4, 6, 9, 1), (3, 5, 6, 6), (2, 4, 5, 7, 2), (2, 3, 4, 4, 7), (2, 2, 3, 4, 6, 3),
(4, 6, 8, 2), (3, 4, 7, 6), (2, 4, 5, 6, 3), (2, 3, 3, 5, 7), (2, 2, 3, 4, 5, 4),
(4, 5, 9, 2), (3, 4, 6, 7), (2, 4, 4, 7, 3), (2, 2, 4, 5, 7), etc.
(4, 5, 8, 3), (3, 4, 5, 8), (2, 3, 5, 7, 3), (2, 2, 4, 5, 6, 1),
(4, 5, 7, 4), (3, 4, 5, 7, 1), (2, 3, 5, 6, 4), (2, 2, 4, 4, 7, 1),
There are altogether 67 sequences since Dm −Dm = 66 when 2q = 20.
Lemma 2.7. Let t ≥ 3. There exist rooted trees T1 and T2 such that vertices u1 and u2
are Šoltés vertices in the graph Q obtained from Gt by attaching T1 and T2 to vertices v1
and v2.
Proof. By Lemma 2.2, there exists q such that Dm ≤ f(t) ≤ Dm. From Lemma 2.4, we
obtain the sequence L, which gives us the appropriate number of vertices in every layer of
the forest T = T1 ∪ T2. This ensures that v1 and v2 are Šoltés vertices in Q.
N. Bašić et al.: On regular graphs with Šoltés vertices 11
Now, we construct a graph Q containing Gt and realising L. Let Tj be the tree rooted
at vj , 1 ≤ j ≤ 2. Then T1 will have ⌈ℓi/2⌉ vertices at distance i from v1 and T2 will have
⌊ℓi/2⌋ vertices at distance i from v2. Observe that it is possible to construct both T1 and
T2. We have two possibilities.
Case 1: ℓi = 2ℓi−1. Then either ℓi = 2i+1, ℓi−1 = 2i, . . . , ℓ1 = 4 and on the first i levels
both T1 and T2 are complete binary trees of height i; or ℓ1 = ℓ2 = · · · = ℓi−1 = 2 and
ℓi = 4, which means that both T1 and T2 contain one vertex at levels 1, 2, . . . , i − 1 and
two vertices at level i.
Case 2: ℓi ≤ 2ℓi−1 − 1. If ℓi−1 is even then we can construct i-th level of both T1 and T2,
and at least one vertex of level i− 1 of T2 will have degree less than 3. On the other hand,
if ℓi−1 is odd then T2 has only (ℓi−1 − 1)/2 vertices at level i− 1. However, it has ⌊ℓi/2⌋
vertices at level i and ⌊ℓi/2⌋ ≤ ⌊(2ℓi−1 − 1)/2⌋ = ℓi−1 − 1 = 2⌊ℓi−1/2⌋, so in T2, the
number of vertices at level i is at most twice the number of vertices at level i − 1. In this
case, at least one vertex at level i − 1 in T1 will have degree less than 3. This concludes
Case 2.
We construct the trees T1 and T2 so that at each level we minimise the number of
vertices of degree 3. Observe that then there is no level in which there are vertices of
degree 1 and also vertices of degree 3.
Consider v1 and v2 as vertices of level 0, and set ℓ0 = 2. We plan to add edges within
levels (i.e. ‘blue’ edges) to create a cubic graph, but sometimes we must also add edges
between consecutive levels (i.e. ‘red’ edges). First, we add necessary edges connecting
vertices of different levels. For every i ≥ 1, if
∑i
j=0 ℓj is odd then add an edge joining a
vertex (of degree ≤ 2) of (i− 1)-th level with a vertex of i-th level.
Lemma 2.8. It is possible to add edges to Q as described above, so that the resulting graph
has no parallel edges and it is subcubic.
Proof. We add the red edges step by step starting with level 1, together with creating the
trees T1 and T2. And we show that at each level it is possible to add a required edge. We
distinguish two cases:
Case 1: There is no red edge between levels i − 2 and i − 1. If 2ℓi−1 = ℓi, then either
(a) ℓ1 = ℓ2 = · · · = ℓi−1 = 2 and ℓi = 4, or (b) ℓj = 2j+1 for all j ≤ i. In both
subcases
∑i
j=0 ℓj is even, and no red edge is added between levels i − 1 and i. Suppose
that 2ℓi−1 > ℓi. Then there is a vertex at (i − 1)-st level, say x, whose degree is less than
3. If 2ℓi > ℓi+1, then there is a vertex at i-th level, say y, whose degree is also less than 3,
and we can add the edge xy. (Observe that if we add these additional edges together with
the construction of trees T1 and T2, then we do not create parallel edges. The only problem
occures when x is the unique vertex at level i− 1 in Tj and y is also in Tj . But then either
ℓi−1 = 3 and j = 2, in which case x can be chosen in T1, or ℓi−1 = 2 and ℓi = 3 in which
case x can be chosen in T2 and y in T1.) On the other hand, if 2ℓi = ℓi+1 then (recall that
2ℓi−1 > ℓi) ℓ1 = · · · = ℓi−1 = ℓi = 2 and ℓi+1 = 4, so
∑i
j=0 ℓj is even, and no red edge
is added between levels i− 1 and i.
Case 2: There is a red edge between levels i− 2 and i− 1. Then
∑i−1
j=0 ℓj is odd. Assume
that we also have to add a red edge between levels i − 1 and i. Then
∑i
j=0 ℓj is also odd
which means that ℓi is even and that 2ℓi−1 > ℓi, as shown in Case 1. Hence, 2ℓi−1 > ℓi+1,
12 Ars Math. Contemp. 25 (2025) #P2.01
so there is a vertex at (i − 1)-st level, say x, whose degree is less than 3. As 2ℓi > ℓi+1,
there is a vertex at i-th level, say y, whose degree is also less than 3, and we can add the
edge xy. (Multiple edges can be avoided analogously as in Case 1.)
We remark that we did not precisely specify how to choose the vertices x and y, when
a red edge is add between levels i− 1 and i in case there are several possibilities. Here are
a few simple rules to follow when choosing x or y at level i:
(i) if there are at least three leaves (in T1∪T2) at level i, then do not choose these leaves;
(ii) if there is eactly one leaf w at level i, w ∈ V (Tj), then there must be a protected
degree-2 vertex at level i in T3−j (i.e. the protected vertex shall not be chosen);
(iii) if there are two leaves w and w′ at level i (one of them is in T1 and the other in T2, as
we will prove later), then one degree-2 vertex from T1 and one degree-2 vertex from
T2 has to be protected;
(iv) if there are no leaves at level i, we have no constraints.
The above rules will be fully justified later, when we will consider 2-connectivity of the
resulting graph H . Denote by R the graph obtained after adding red edges, as described
above. We have the following statement.
Lemma 2.9. In each level of R, the sum of free valencies is even.
Proof. Let 1 ≤ i ≤ d. We prove the statement for level i. So denote by a1, a2, . . . , aℓi the
vertices at i-th level. Our task is to show that
∑ℓi
j=1(3−degR(aj)) is even. We distinguish
two cases, with two subcases each.
Case 1:
∑i
j=0 ℓj is odd. Then there are ℓi + 1 edges between levels ℓi−1 and ℓi in R.
If ℓi+1 is odd, then
∑i+1
j=0 ℓj is even, so there are ℓi+1 edges between levels i and i + 1.
Hence,
∑ℓi
j=1(3− degR(aj)) = 3ℓi − ℓi − 1− ℓi+1 is even. On the other hand, if ℓi+1 is
even, then
∑i+1
j=0 ℓj is odd, so there are ℓi+1 + 1 edges between levels i and i+ 1. Hence,∑ℓi
j=1(3− degR(aj)) = 3ℓi − ℓi − 1− ℓi+1 − 1 is even.
Case 2:
∑i
j=0 ℓj is even. Then there are ℓi edges between levels ℓi−1 and ℓi in R. If
ℓi+1 is odd, then
∑i+1
j=0 ℓj is odd, so there are ℓi+1 + 1 edges between levels i and i + 1.
Hence,
∑ℓi
j=1(3− degR(aj)) = 3ℓi − ℓi − ℓi+1 − 1 is even. On the other hand, if ℓi+1 is
even, then
∑i+1
j=0 ℓj is also even, so there are ℓi+1 edges between levels i and i+1. Hence,∑ℓi
j=1(3− degR(aj)) = 3ℓi − ℓi − ℓi+1 is even.
By Lemma 2.9, the sum of free valencies is even at each level of R. This means that, in
general, after we add some edges connecting vertices within level i, and when we do that
for all i, 1 ≤ i ≤ d, the resulting graph H will be cubic. We now describe how to add these
‘blue’ edges, so that H will be 2-connected, and how to resolve the cases when a level has
small number of remaining degree-2 vertices.
Observation. H will be 2-connected if for every leaf x of T , say x ∈ V (Tk), where
1 ≤ k ≤ 2 and x is a vertex at level i, there is a path, say P , containing only the vertices of
level i and connecting x with a vertex, say y, of T3−k.
N. Bašić et al.: On regular graphs with Šoltés vertices 13
We refer to the above as the 2-connectivity condition. The reason is that P can be
completed to a cycle using a (vk, x)-path in Tk and a (v3−k, y)-path in T3−k. Since all
cycles constructed in this way contain three vertices of Gt, the resulting graph H will be
2-connected. We remark that in one special case the path P will contain vertices of levels
i and i+1, but it will still be possible to complete P to a cycle containing three vertices of
Gt. Thus, our attention will be focused on the leaves of T .
Lemma 2.10. It is possible to add edges to R so that the resulting graph H will be cubic
and 2-connected.
Proof. First, we consider the d-th (i.e., the last) level. Note that all the vertices at level d
are leaves of T . Since
∑d
j=1 ℓj = 2q is even, each vertex at level d has degree 1 in R. We
distinguish three cases.
Case 1: ℓd ≥ 3. In this case, we add to graph R a cycle passing through all the vertices
of level d. Then the vertices of level d will have degree 3 and they will satisfy the 2-
connectivity condition, since ⌈ℓd/2⌉ vertices of level d are in T1 and ⌊ℓd/d⌋ of them are
in T2.
Case 2: ℓd = 1. Then ℓd−1 ≥ 3, as already shown. In this case, we replace the sequence
L = (ℓ1, ℓ2, . . . , ℓd−1, 1) by L∗ = (ℓ1, ℓ2, . . . , ℓd−1, 3) and we find a 2-connected cubic
graph H∗ realizing L∗. In this graph, the pendant vertices of level d are connected to
three different vertices of level d− 1 in T , since at each level we minimised the number of
degree-3 vertices. Since
∑d
j=1 ℓj is even, there are no other edges connecting vertices of
level d− 1 with those of level d in R. Hence, we add a 3-cycle as described in Case 1, and
then contract the three vertices at level d to a single vertex. If H∗ is cubic and 2-connected,
then so is the resulting graph H .
Case 3: ℓd = 2. In this case, we simultaneously resolve the problem for levels d and d− 1.
Since
∑d−1
j=1 ℓj is even, all vertices of level d− 1 have degree 1 except for two, which have
degree 2. (Recall that T was constructed so that at each level the number of vertices of
degree 3 was minimised.)
If ℓd−1 = 2, then connect both vertices of level d− 1 with both vertices of level d and
add an edge connecting the vertices of level d. Then the vertices of levels d− 1 and d have
degree 3 and they satisfy the 2-connectivity condition.
If ℓd−1 ≥ 3, then pick a vertex of degree 1 at level d − 1, say x, and join it to both
vertices of level d. Then x has degree 3, but since it is a leaf of T , it does not satisfy
the 2-connectivity condition in the strict sense. Nevertheless, there is a cycle in H which
contains edges of Gt, a path connecting v1 with a vertex of level d in T1, a path connecting
v2 with a vertex of level d in T2, and the two edges connecting x with the vertices of level
d, which is sufficient. Then add to H the edge connecting vertices of level d and add a path
passing through all vertices of level d− 1 except x, and starting/ending in the two degree-2
vertices. This resolves the problem for levels d and d− 1. This concludes Case 3.
We now turn to level i, 1 ≤ i < d. In case ℓd = 2, we assume i < d− 1. Then vertices of
level i are connected to vertices of levels i− 1 and i+1 using only the edges of R, and we
now add only edges connecting vertices within level i, i.e. the blue edges.
In some cases, we specify positions of red edges that were added to T to form R, to
justify the four rules for choosing vertices x and y in the process of creating R.
14 Ars Math. Contemp. 25 (2025) #P2.01
If there is no leaf at level i, then all vertices of this level have degrees 2 and 3 in R. By
Lemma 2.9, there is an even number of degree-2 vertices. Thus, we can add a collection
of independent edges so that all vertices of level i will have degree 3. Since there were no
leaves, the vertices of level i satisfy the 2-connectivity condition.
Now suppose that there are leaves at level i. Since we minimised the number of vertices
of degree 3 when constructing T , there are no vertices of degree 3 in level i. Consequently,
each vertex of level i is connected to at most one vertex in level i+ 1 in T . Hence, T1 and
T2 have, respectively, ⌈ℓi/2⌉ − ⌈ℓi+1/2⌉ and ⌊ℓi/2⌋ − ⌊ℓi+1/2⌋ leaves at level i. Denote
k = (⌈ℓi/2⌉−⌈ℓi+1/2⌉)−(⌊ℓi/2⌋−⌊ℓi+1/2⌋). Since k = (⌈ℓi/2⌉−⌊ℓi/2⌋)−(⌈ℓi+1/2⌉−
⌊ℓi+1/2⌋), we have
−1 ≤ k ≤ 1. (2.5)
This means that the numbers of leaves at level i in T1 and T2 differ by at most one, and also
that there are no degree-3 vertices at level i in T . Moreover, since i < d, level i contains
two vertices, say b1 and b2, such that b1 ∈ V (T1), b2 ∈ V (T2) and b1, b2 are not leaves in
T . (Recall that if i = d− 1 and ℓd = 1, then then we solve this case for L∗ where ℓd = 3,
and afterwards we provide the contraction of vertices at level d, see Case 2 above.) Then
degT (b1) = degT (b2) = 2. We distinguish three cases.
Case 1: T has at least 3 leaves at level i. If E(R) \ E(T ) contains an edge connecting
levels i − 1 and i, then this edge will terminate at b1, and if E(R) \ E(T ) contains an
edge connecting levels i and i + 1, then this edge will start at b2. (Note that if we create
T and R simultaneously, level by level, then we can form b1 and b2, so that we do not get
parallel edges. In the worst case we relabel b1 and b2, so that b1 ∈ V (T2) and b2 ∈ V (T1).)
This leaves the leaves untouched. Then we add a cycle passing through all leaves of level
i and add a collection of independent edges so that all vertices of level i become degree-3
vertices. Since, at level i, at least one leaf is in T1 and at least one is in T2, the vertices at
level i satisfy the 2-connectivity condition.
Case 2: T has exactly two leaves at level i. Denote these vertices by a1 and a2. As
mentioned above, we may assume that a1 ∈ V (T1) and a2 ∈ V (T2). If E(R) \ E(T )
contains an edge connecting levels i − 1 and i, then this edge will terminate at a1, and if
E(R) \ E(T ) contains an edge connecting levels i and i + 1, then this edge will start at
a2. (Again, not to create parallel edges, the red edge between levels i − 1 and i may be
connected to a2 instead of a1, and then possible red edge between levels i and i + 1 will
start at a1.) Then add edges a1b2, a2b1, and a collection of independent edges so that all
vertices of level i become degree-3 vertices. Due to the presence of edges a1b2 and a2b1,
the vertices at level i satisfy the 2-connectivity condition.
Case 3: T has exactly one leaf at level i. Denote this vertex by a. Without loss of generality,
assume that a ∈ V (T1). If E(R) \ E(T ) contains an edge connecting levels i − 1 and i,
then this edge will terminate at b1, and if E(R) \E(T ) contains an edge connecting levels
i and i+1, then this edge will start at a. (Not to create parallel edges, the red edge between
levels i− 1 and i may be connected to a instead of b1, and then possible red edge between
levels i and i + 1 will start at b1.) Then add the edge ab2, and a collection of independent
edges so that all vertices of level i become degree-3 vertices. Due to the presence of edge
ab2, vertices at level i satisfy the 2-connectivity condition.
N. Bašić et al.: On regular graphs with Šoltés vertices 15
3 Cubic 2-connected graphs with 2r Šoltés vertices
Now we generalise Theorem 2.1 to higher amount of Šoltés vertices.
Theorem 3.1. Let r ≥ 1. There exist infinitely many cubic 2-connected graphs G which
contain at least 2r Šoltés vertices.
Proof. We reconsider the graph Gt from the proof of Theorem 2.1. This graph consists of
a chain of 2t diamonds attached to vertices z1 and z2 of a graph on 8 vertices. Denote this
graph on 8 vertices by F .
We construct Gt,r. Take a binary tree B of depth r−1. This tree has 2r−1 vertices, out
of which 2r−1 are leaves. Denote these leaves by a1, a2, . . . , a2r−1 . Let B′ be a copy of B.
To distinguish endvertices of B′ from those of B, put to the endvertices of B′ dashes. Now
take 2r−1 chains of 2t diamonds and identify the ends (the vertices of degree 2) of k-th
chain with ak and a′k, respectively. Finally, join the roots of B and B
′ (i.e., the vertices of
degree 2) by edges to z1 and z2.
u1
u2
z1
z2
v1
v2
Figure 5: The graph G3,2. Edges of binary trees of depth 1 are red.
Denote by Gt,r the resulting graph, see Figure 5 for G3,2. Then Gt,r has 8t2r−1 +
2(2r−1− 1)+8 vertices. Moreover, all central vertices of 2r−1 chains of diamonds belong
to the same orbit of Gt,r. Observe that there are 2r such vertices. Let u1 and u2 be central
vertices of one of the chains of diamonds. If we show that limt→∞(W (Gt,r − u1) −
W (Gt,r)) = ∞, we can complete Gt,r analogously as Gt was completed to H in the proof
of Theorem 2.1, to obtain a cubic 2−connected graph with at least 2r Šoltés vertices.
Thus, it remains to show that W (Gt,r − u1) − W (Gt,r) tends to infinity as t → ∞.
Observe that W (Gt,r − u1)−W (Gt,r) equals∑
x,y∈V (Gt,r)\{u1}
(
dGt,r−u1(x, y)− dGt,r (x, y)
)
− wGt,r (u1).
We first estimate wGt,r (u1) from above. For small i, there are at most 4 vertices at
distance i from u1. For bigger i the amount of vertices at distance i grows, but it cannot
exceed 4 ·2r+8 since there are 2r−1 chains attached to F and F itself has 8 vertices. Thus,
16 Ars Math. Contemp. 25 (2025) #P2.01
wGt,r (u1) ≤ (2r+2 + 8)
∑1+3t+2r+3t+3
i=1 i. And if we held r constant, wGt,r (u1) can be
bounded from above by a quadratic polynomial in t.
Now we estimate
∑
x,y∈V (Gt,r)\{u1}
(
dGt,r−u1(x, y) − dGt,r (x, y)
)
from below. For
every x, y ∈ V (Gt,r)\{u1} we have dGt,r−u1(x, y) ≥ dGt,r (x, y), since Gt,r has all paths
which exist in Gt,r −u1. However, it suffices to consider only x, y being in the same chain
of diamonds as u1. Observe that the distance from u2 to a neighbour of u1 ( ̸= u2) is 2 in
Gt,r, but it is at least 6t in Gt,r − u1 (with equality if r = 1, i.e. if Gt,r = Gt). So this
distance is increased at least by 6t − 2. The distance from u2 to the second neighbour of
u1 is increased at least by 6t − 4, etc. However, we should consider also a neighbour of
u2 ( ̸= u1). For this vertex the distances are increased at least by 6t−4, 6t−6, . . . Summing
up,
D ≥
3t−1∑
j=1
j∑
i=1
2i = 2
3t−1∑
j=1
(
j + 1
2
)
= 2
(
3t+ 1
3
)
.
Consequently, W (Gt,r−u1)−W (Gt,r) is bounded from below by a cubic polynomial
(in t) with leading coefficient 9. Thus, limt→∞(W (Gt,r − u1) − W (Gt,r)) = ∞ as
required.
4 Concluding remarks and further work
We believe that if there exists another Šoltés graph in addition to C11, it is likely to be
vertex-transitive or has a low number of vertex orbits. Vertices of the same orbit are either
all Šoltés vertices or none of them is.
Holt and Royle [5] have constructed a census of all vertex-transitive graphs with less
than 48 vertices; these graphs can be obtained from their Zenodo repository [14] in the
graph6 format [10]. The repository contains 100 720 391 graphs in total, 100 716 591 of
which are connected [12]. The computer search revealed that the only Šoltés graph among
them is the well-known C11.
We also examined the census of cubic vertex-transitive graphs by Potočnik, Spiga and
Verret [13]. Their census contains all (connected) cubic vertex-transitive graphs on up to
1280 vertices; there are 111 360 such graphs. CVT(n, i) denotes the i-th graph of order
n in the census. No Šoltés graph has been found, but the search revealed that there exist
graphs that are 13 -Šoltés, i.e.
1
3 of all vertices are Šoltés vertices. We found 7 cubic
1
3 -
Šoltés graphs; all of them are trunctations of certain cubic vertex-transitive graphs. In
this paper, the truncation of a graph G is denoted by Tr(G). Note that the truncation of
a vertex-transitive graph is not necessarily a vertex-transitive graph; in the case of cubic
graphs, there may be up to 3 vertex orbits. When doing the computer search, we have to
check the Šoltés property for one vertex from each orbit only. Here is the list of cubic
vertex-transitive graphs G, such that Tr(G) is a 13 -Šoltés graph:
CVT(384, 805), CVT(600, 259), CVT(768, 3650), CVT(1000, 302),
CVT(1056, 538), CVT(1056, 511), CVT(1280, 967).
Interestingly, all these graphs are Cayley graphs. Several properties of these graphs are
listed in the Appendix. The graph CVT(768, 3650) is the only non-bipartite example,
while the rest are bipartite. Girths of these graph are values from the set {4, 6, 8, 10, 12}.
We were able to identify seven such graphs. However, we believe that there could exist
many more.
N. Bašić et al.: On regular graphs with Šoltés vertices 17
Problem 4.1. Find an infinite family of cubic vertex-trainsitive graphs {Gi}∞i=1, such that
Tr(Gi) is a 13 -Šoltés graph for all i ≥ 1.
Moreover, we also found an example of a 4-regular 13 -Šoltés graph, namely the graph
L(CVT(324, 104)). It has order 486 and is the line graph of CVT(324, 104), which is a
Cayley graph. More data can be found in the Appendix.
Of course, 13 -Šoltés is still a long way from being Šoltés. The next conjecture is ad-
ditionally reinforced by the fact that there are no Šoltés graphs among vertex-transitive
graphs with less than 48 vertices.
Conjecture 4.2. The cycle on eleven vertices, C11, is the only Šoltés graph.
ORCID iDs
Nino Bašić https://orcid.org/0000-0002-6555-8668
Martin Knor https://orcid.org/0000-0003-3555-3994
Riste Škrekovski https://orcid.org/0000-0001-6851-3214
References
[1] M. Akhmejanova, K. Olmezov, A. Volostnov, I. Vorobyev, K. Vorob’ev and Y. Yarovikov,
Wiener index and graphs, almost half of whose vertices satisfy Šoltés property, Discrete
Appl. Math. 325 (2023), 37–42, doi:10.1016/j.dam.2022.09.021, https://doi.org/10.
1016/j.dam.2022.09.021.
[2] H. U. Besche, B. Eick and E. O’Brien, SmallGrp (The GAP Small Groups Library), https:
//docs.gap-system.org/pkg/smallgrp/doc/manual.pdf.
[3] J. Bok, N. Jedličková and J. Maxová, A relaxed version of Šoltés’s problem and cactus graphs,
Bull. Malays. Math. Sci. Soc. 44 (2021), 3733–3745, doi:10.1007/s40840-021-01144-5,
https://doi.org/10.1007/s40840-021-01144-5.
[4] A. A. Dobrynin, On the preservation of the Wiener index of cubic graphs upon vertex removal,
Sib. Electron. Math. Rep. 20 (2023), 285–292.
[5] D. Holt and G. Royle, A census of small transitive groups and vertex-transitive graphs, J.
Symb. Comput. 101 (2020), 51–60, doi:10.1016/j.jsc.2019.06.006, https://doi.org/
10.1016/j.jsc.2019.06.006.
[6] Y. Hu, Z. Zhu, P. Wu, Z. Shao and A. Fahad, On investigations of graphs preserving the Wiener
index upon vertex removal, AIMS Math. 6 (2021), 12976–12985, doi:10.3934/math.2021750,
https://doi.org/10.3934/math.2021750.
[7] M. Knor, S. Majstorović and R. Škrekovski, Graphs whose Wiener index does not change
when a specific vertex is removed, Discrete Appl. Math. 238 (2018), 126–132, doi:10.1016/j.
dam.2017.12.012, https://doi.org/10.1016/j.dam.2017.12.012.
[8] M. Knor, S. Majstorović and R. Škrekovski, Graphs preserving Wiener index upon vertex
removal, Appl. Math. Comput. 338 (2018), 25–32, doi:10.1016/j.amc.2018.05.047, https:
//doi.org/10.1016/j.amc.2018.05.047.
[9] M. Knor, R. Škrekovski and A. Tepeh, Mathematical aspects of Wiener index, Ars Math.
Contemp. 11 (2016), 327–352, doi:10.26493/1855-3974.795.ebf, https://doi.org/10.
26493/1855-3974.795.ebf.
[10] B. D. McKay, Description of graph6, sparse6 and digraph6 encodings, http://
users.cecs.anu.edu.au/~bdm/data/formats.txt.
18 Ars Math. Contemp. 25 (2025) #P2.01
[11] B. D. McKay and A. Piperno, Practical graph isomorphism, II, J. Symb. Comput. 60 (2014), 94–
112, doi:10.1016/j.jsc.2013.09.003, https://doi.org/10.1016/j.jsc.2013.09.
003.
[12] OEIS Foundation Inc., Entry A006799 in The On-Line Encyclopedia of Integer Sequences,
2022, https://oeis.org/A006799.
[13] P. Potočnik, P. Spiga and G. Verret, Cubic vertex-transitive graphs on up to 1280 vertices,
J. Symb. Comput. 50 (2013), 465–477, doi:10.1016/j.jsc.2012.09.002, https://doi.org/
10.1016/j.jsc.2012.09.002.
[14] G. Royle and D. Holt, Vertex-transitive graphs on fewer than 48 vertices [Data set], Zenodo,
https://doi.org/10.5281/zenodo.4010122.
[15] L’. Šoltés, Transmission in graphs: a bound and vertex removing, Math. Slovaca 41 (1991),
11–16.
[16] H. Wiener, Structural determination of paraffin boiling points, J. Am. Chem. Soc. 69 (1947),
17–20, doi:10.1021/ja01193a005, https://doi.org/10.1021/ja01193a005.
N. Bašić et al.: On regular graphs with Šoltés vertices 19
A Appendix
There are 7 cubic vertex-transitive graphs G on up to 1280 vertices, such that Tr(G) is a
1
3 -Šoltés graph. Since all these graph are Cayley graphs, we give the generating set for the
Cayley graph. Note that the group itself (its permutation representation) is given implicitly
by these generators; however, we also give the group’s ID from GAP’s library of small
groups [2]. SmallGroup(n, k) is the k-th group of order n from that library. We also
calculated girth, diameter and tested all graphs for bipartiteness.
• CVT(384, 805):
Group([(2, 4)(6, 12, 17, 19, 18, 14)(7, 10, 20)(8, 15, 16, 9, 11, 13),
(1, 4)(2, 3)(5, 13)(6, 18)(7, 17)(8, 15)(9, 12)(10, 14)(11, 19)(16, 20)])
∼= SmallGroup(384, 5781)
girth: 6; diameter: 10; bipartite? True
• CVT(600, 259):
Group([(1, 2)(3, 4)(5, 6)(7, 9)(8, 10)(13, 14)(16, 17),
(1, 3)(5, 7)(6, 8)(9, 12)(10, 13)(11, 14)(15, 16),
(1, 4)(2, 3)(5, 6)(8, 11)(9, 10)(13, 14)(15, 17)])
∼= SmallGroup(600, 103)
girth: 10; diameter: 13; bipartite? True
• CVT(768, 3650):
Group([(2, 3)(4, 7)(5, 6)(10, 12),
(2, 4)(3, 5)(6, 7)(9, 10)(11, 12),
(1, 2)(3, 6)(4, 8)(5, 7)])
∼= SmallGroup(768, 1090104)
girth: 8; diameter: 16; bipartite? False
• CVT(1000, 302):
Group([(4, 5)(6, 7)(9, 14)(10, 18)(11, 21)(12, 23)(13, 25)(15, 24)(16, 27)(17, 29)
(19, 26)(20, 31)(22, 28)(30, 32),
(1, 2)(3, 4)(5, 6)(8, 9)(10, 15)(11, 19)(12, 18)(13, 21)(14, 23)(16, 17)
(20, 27)(22, 29)(24, 31)(25, 32)(26, 28),
(1, 2)(8, 17)(9, 27)(10, 11)(12, 26)(13, 24)(14, 22)(15, 18)(16, 30)(20, 32)
(21, 28)(23, 31)(25, 29)])
∼= SmallGroup(1000, 105)
girth: 10; diameter: 15; bipartite? True
20 Ars Math. Contemp. 25 (2025) #P2.01
• CVT(1056, 538):
Group([(2, 3)(4, 5)(6, 8)(7, 10)(9, 11)(13, 14)(15, 16)(17, 18)(19, 20)(21, 22),
(1, 2)(4, 6)(7, 9)(12, 13)(14, 15)(16, 17)(18, 19)(20, 21),
(4, 7)(6, 9)(10, 11)(12, 13)(14, 15)(16, 17)(18, 19)(20, 21)])
∼= SmallGroup(1056, 493)
girth: 4; diameter: 22; bipartite? True
• CVT(1056, 511):
Group([(2, 3)(12, 13)(14, 15)(16, 17)(18, 19)(20, 21),
(1, 2)(4, 5)(6, 7)(8, 9)(10, 11)(12, 14)(15, 16)(17, 18)(19, 20)(21, 22),
(5, 6)(7, 8)(9, 10)(12, 13)(14, 15)(16, 17)(18, 19)(20, 21)])
∼= SmallGroup(1056, 468)
girth: 4; diameter: 22; bipartite? True
• CVT(1280, 967):
Group([(1, 2)(3, 5)(7, 9)(8, 11)(10, 15)(12, 19)(13, 20)(14, 22)(16, 25)(17, 27)
(18, 29)(21, 32)(23, 34)(24, 30)(26, 31)(28, 37),
(1, 3)(4, 5)(6, 7)(8, 12)(9, 13)(10, 16)(11, 17)(15, 23)(18, 30)(20, 31)
(21, 27)(22, 25)(24, 28)(26, 36)(29, 33)(35, 37),
(1, 4)(2, 3)(6, 8)(7, 10)(9, 14)(11, 18)(12, 20)(13, 21)(15, 24)(16, 26)
(17, 28)(19, 29)(22, 33)(23, 35)(25, 30)(27, 36)(31, 34)(32, 37)])
∼= SmallGroup(1280, 81752)
girth: 12; diameter: 16; bipartite? True
There exists one cubic vertex-transitive graph G on up to 1280 vertices, such that L(G) is
a 13 -Šoltés graph.
• CVT(324, 104):
Group([(2, 9)(3, 4)(5, 7)(6, 8),
(1, 5)(2, 6)(3, 9)(4, 7),
(2, 9)(3, 6)(4, 8)])
∼= SmallGroup(324, 39)
girth: 4; diameter: 12; bipartite: True