On regular graphs with Šoltés vertices (2024)

Nino BašićFAMNIT, University of Primorska, Koper, SloveniaIAM, University of Primorska, Koper, SloveniaInstitute of Mathematics, Physics and Mechanics, Ljubljana, SloveniaMartin KnorSlovak University of Technology in Bratislava, SlovakiaRiste ŠkrekovskiFAMNIT, University of Primorska, Koper, SloveniaFaculty of Mathematics and Physics, University of Ljubljana, SloveniaFaculty of Information Studies, Novo mesto, Slovenia

Abstract

Let $W(G)$ be the Wiener index of a graph $G$ . We say that a vertex $v\in 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 $C_{11}$ . As the original problem appears to be too challenging, several relaxationswere studied: one may look for graphs with at least $k$ Šoltes vertices; orone may look for $\alpha$ -Šoltés graphs, i.e.graphs where the ratio between the number of Šoltésvertices and the order of the graph is at least $\alpha$ . 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 andhas 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\geq 1$ we describe a construction of an infinite family of cubic $2$ -connected graphs with at least $2^{r}$ Šoltés vertices.Moreover, we report that a computer search on publicly available collections of vertex-transitive graphs did not reveal any $1$ -Šoltés graph.We are only able to provide examples of large $\frac{1}{3}$ -Š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 $C_{11}$ 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)=\frac{1}{2}\sum_{u\in V(G)}\sum_{v\in V(G)}d_{G}(u,v)=\sum_{\{u,v\}%\subseteq V(G)}d_{G}(u,v),

(1)

where $d_{G}(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)=\infty$ .The Wiener index was introduced in 1947 [17] and has been extensively studied ever since. For a recent survey onthe Wiener index see [9]. The transmission of a vertex $v$ in a graph $G$ , denoted by $w_{G}(v)$ , is defined as $w_{G}(v)=\sum_{u\in V(G)}d_{G}(u,v)$ . Note that (1) can also be expressed as $W(G)=\frac{1}{2}\sum_{u\in V(G)}w_{G}(u)$ .

Let $v\in 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(K_{7})=21$ and $W(K_{7}-v)=W(K_{6})=15$ );
(b)
the Wiener index increases (e.g. $W(\mathrm{Wh}_{9})=56$ and $W(\mathrm{Wh}_{9}-v_{0})=W(C_{8})=64$ , where $\mathrm{Wh}_{n}$ denotes thewheel graph on $n$ vertices and $v_{0}$ is the central vertex of the wheel);
(c)
the Wiener index does not change (e.g. $W(\mathrm{Wh}_{8})=42$ and $W(\mathrm{Wh}_{8}-v_{0})=W(C_{7})=42$ , where $v_{0}$ is the central vertexof $\mathrm{Wh}_{8}$ ).

We say that a vertex $v\in 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\in V(G)\mid W(G)=W(G-v)\}

and let $0\leq\alpha\leq 1$ .We say that a graph $G$ is an $\alpha$ -Šoltés graph if $|S(G)|\geq\alpha|V(G)|$ , i.e.the ratio between thenumber of Šoltés vertices of $G$ and the order of $G$ is at least $\alpha$ .For example, the graph in Figure1 is the smallest cubic $\frac{1}{3}$ -Š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, $C_{11}$ . In this paper, Šoltés graph is simply thesynonym for $1$ -Šoltés graph.

The Šoltés problem [15] was forgotten for nearly three decades. It was revived and popularised in 2018 by Knoret al.[7].They considered a relaxation of the original problem: one may look for graphs witha prescribed number of Šoltés vertices. Theyshowed that there exists a unicyclic graph on $n$ vertices with at least one Šoltés vertex for every $n\geq 9$ . They also showed that there exists a unicyclicgraph with a cycle of length $c$ and at least one Šoltés vertex for every $c\geq 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\geq 3$ there exist infinitely many graphs with a Šoltés vertex of degree $d$ . Necessary conditions for the existence of Šoltés verticesin Cartesian products of graphs were also considered[8].In 2021, Boket al.[3] showed that for every $k\geq 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 problem and showed that there exist infinitely many graphs where the Wiener indexremains the same even if $r\geq 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ésvertices?They constructed two infinite families of graphs with a relatively high proportion of Šoltés vertices.Their first family comprises graphs $B(k)$ , $k\geq 2$ , where $B(k)$ is a $\frac{2k}{5k+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 $\frac{2}{5}$ ,but tends to $\frac{2}{5}$ as $k$ goes to infinity. They also introduced a two-parametric infinite family $L(k,m)$ , $m\geq 7$ and $k\geq\frac{m-3}{m-6}$ .Here, the percentage of Šoltés vertices is below $\frac{1}{2}$ , but tends to $\frac{1}{2}$ as $k$ goes to infinity for a fixed $m$ . These graphscontain 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.

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 significantly differentfor two different vertices $u,v\in 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 graphis likely to be vertex transitive.

Conjecture 2.

If $G$ is a Šoltés graph, then $G$ is vertex transitive.

Among truncations of cubic vertex-transitive graphs we found several $\frac{1}{3}$ -Šoltés graphs; see Section4.Interestingly, all our examples are in fact Cayley graphs and this leads us to pose the following conjecture.

Conjecture 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 $\mathcal{R}^{r}$ denote the class of all $r$ -regular graphs and let $\mathcal{R}^{r}_{n}$ denote the set of $r$ -regular graphs on $n$ vertices. Let $N(\mathcal{G},k)$ be the number of graphs in the class $\mathcal{G}$ that contain exactly $k$ Šoltés vertices.

Table1 shows the numbers of (non-isomorphic) cubic graphs of orders $n\leq 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 Figure2(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 Figure2(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 Figure2(g)).Numbers of $4$ -regular and $5$ -regular graphs with respect to their number of Šoltés vertices are given in Tables2 and3, respectively.

$\begin{array}[]{r|r||r|r|r|r|r|r|r|r}&&\lx@intercol\hfil N(\mathcal{R}^{3}_{n}%,k)\hfil\lx@intercol\\\cline{3-10}\cr n&|\mathcal{R}^{3}_{n}|&k=1&k=2&k=3&k=4&k=5&k=6&k=7&k=8\\\hline\cr\hline\cr\leq 12&112&\text{-}&\text{-}&\text{-}&\text{-}&\text{-}&%\text{-}&\text{-}&\text{-}\\14&509&4&{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}%\mathbf{3}}&\text{-}&\text{-}&\text{-}&\text{-}&\text{-}&\text{-}\\16&4060&108&37&{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{%0,0,1}\mathbf{1}}&{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{%0,0,1}\mathbf{2}}&\text{-}&\text{-}&\text{-}&\text{-}\\18&41301&1014&200&\text{-}&{\color[rgb]{0,0,1}\definecolor[named]{%pgfstrokecolor}{rgb}{0,0,1}\mathbf{1}}&\text{-}&\text{-}&\text{-}&\text{-}\\20&510489&13460&1076&6&13&\text{-}&\text{-}&\text{-}&\text{-}\\22&7319447&194432&9610&151&52&\text{-}&1&\text{-}&\text{-}\\24&117940535&3161124&130087&2596&333&2&3&\text{-}&{\color[rgb]{0,0,1}%\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathbf{1}}\\\end{array}$

$\begin{array}[]{r|r||r|r|r|r}&&\lx@intercol\hfil N(\mathcal{R}^{4}_{n},k)\hfil%\lx@intercol\\\cline{3-6}\cr n&|\mathcal{R}^{4}_{n}|&k=1&k=2&k=3&k=4\\\hline\cr\hline\cr\leq 12&1894&\text{-}&\text{-}&\text{-}&\text{-}\\13&10778&\text{-}&{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{%0,0,1}\mathbf{1}}&\text{-}&\text{-}\\14&88168&30&6&\text{-}&\text{-}\\15&805491&265&85&\text{-}&5\\16&8037418&2191&472&\text{-}&\text{-}\\17&86221634&14430&2097&4&1\\\end{array}$

$\begin{array}[]{r|r||r|r|r|r}&&\lx@intercol\hfil N(\mathcal{R}^{5}_{n},k)\hfil%\lx@intercol\\\cline{3-6}\cr n&|\mathcal{R}^{5}_{n}|&k=1&k=2&k=3&k=4\\\hline\cr\hline\cr\leq 12&7912&\text{-}&\text{-}&\text{-}&\text{-}\\14&3459383&8&3&\text{-}&\text{-}\\\end{array}$

In the next two sections we construct an infinite family of cubic $2$ -connected graphs with at least $2^{r}$ , $r\geq 1$ , Šoltés vertices.It recently came to our attention that Dobrynin independently found an infinite family of cubic graphs with fourŠoltés vertices[4]. However, our method is more general.

2 Cubic $\boldsymbol{2}$ -connected graphs with two Šoltés vertices

In the present section we prove the following result.

Theorem 4.

There exist infinitely many cubic $2$ -connected graphs $G$ which contain at least two Šoltés vertices.

We prove Theorem4 by a sequence of lemmas.We start by giving several definitions.First, we define a graph $G_{t}$ on $8t+8$ vertices, where $t\geq 1$ .Take $2t$ copies of the diamond graph (i.e. $K_{4}-e$ ) and connect their degree- $2$ vertices, so that a ring of $2t$ copies of $K_{4}-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 $z_{1}$ and $z_{2}$ , and connect $z_{1}$ and $z_{2}$ 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 $G_{t}$ .For an illustration, see $G_{3}$ in Figure3.Note that $G_{t}$ has exactly two leaves, denote them by $v_{1}$ and $v_{2}$ , and all the remaining vertices have degree $3$ .Denote by $u_{1}$ and $u_{2}$ the two vertices at the longest distance from $v_{1}$ .This distance is $d_{G}(v_{1},u_{1})=d_{G}(v_{1},u_{2})=3t+3$ and also $d_{G}(v_{2},u_{1})=d_{G}(v_{2},u_{2})=3t+3$ .Observe that $G_{t}$ has an automorphism (a symmetry) fixing both $v_{1}$ and $v_{2}$ , while interchanging $u_{1}$ with $u_{2}$ .

Now, we determine $f(t)=W(G_{t}-u_{1})-W(G_{t})$ .We compute $f(t)$ by summing the contributions of all vertices (first the contribution of quadruples of vertices of all copies of $K_{4}-e$ , and then the contribution of the vertices which are not in any copy of $K_{4}-e$ ).As the calculation is long and tedious, we present just the result

f(t)=16t^{3}-8t^{2}-26t-14,

(2)

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, $\lim_{t\to\infty}f(t)=\infty$ ; see also Section3,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 $T_{1}$ and $T_{2}$ to vertices $v_{1}$ and $v_{2}$ of $G_{t}$ , and then we add edges to them so that the resulting graph $H$ will be cubic and $2$ -connected.See Figure4 for an example.This will be done in three phases.

P1)
In the first phase, we will construct trees $T_{1}$ and $T_{2}$ to guarantee that vertices $u_{1}$ and $u_{2}$ are indeed Šoltés vertices.The vertices of $T_{1}$ and $T_{2}$ can be partitioned into several layers based on their distance to $v_{1}$ and $v_{2}$ , 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 consecutive 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 subcubicgraph $G$ is $3-\deg_{G}(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 $T_{1}\cup T_{2}$ . Adding ‘red’ and ‘blue’ edges has no influence on Šoltésness of $u_{1}$ and $u_{2}$ .

Let us consider the resulting graph $H$ .Observe that if $x\in V(H)\setminus V(G_{t})$ , then we have $w_{H}(x)-w_{H-u_{1}}(x)=d_{H}(u_{1},x)$ . Clearly, every $(u_{1},x)$ -path containsone of the vertices from $\{v_{1},v_{2}\}$ .Hence, for calculating $W(H)-W(H-u_{1})$ , only the distance of the new vertices $x$ to $\{v_{1},v_{2}\}$ matters.

We need to find suitable trees $T_{1}$ and $T_{2}$ rooted at $v_{1}$ and $v_{2}$ , respectively.Each of these trees will have $q$ vertices and their depth, say $d$ , will be determined later.What next properties do $T_{1}$ and $T_{2}$ need to have?Let $\ell_{i}$ be the number of vertices of the forest $T_{1}\cup T_{2}$ at distance $i$ , $1\leq i\leq d$ , from $\{v_{1},v_{2}\}$ .Since the resulting graph will be cubic and $2$ -connected, we have $2\leq\ell_{1}\leq 4,2\leq\ell_{2}\leq 8,2\leq\ell_{3}\leq 2^{4},\dots$ and for the last value $\ell_{d}$ we have $1\leq\ell_{d}\leq 2^{d+1}$ .The trees attached to $v_{1}$ and $v_{2}$ may be paths in which case we get $\ell_{1}=\ell_{2}=\cdots=\ell_{q}=2$ (since each of $T_{1}$ and $T_{2}$ have exactly $q$ vertices).In this case the transmission of $v_{j}$ in $T_{j}$ is biggest possible, $1\leq j\leq 2$ .In the other extremal situation the transmission of $v_{j}$ in $T_{j}$ is smallest possible, $1\leq j\leq 2$ , which results in $\ell_{i}=2^{i+1}$ , $1\leq i<d$ .If $x\in V(H)\setminus V(G_{t})$ is at distance $i$ from $\{v_{1},v_{2}\}$ , then $d_{H}(u_{1},x)=3t+3+i$ .Denote by $D$ the sum of distances from all vertices of $V(H)\setminus V(G_{t})$ to $u_{1}$ .Then

D=\sum_{i=1}^{d}(3t+3+i)\ell_{i}.

(3)

Observe that we need to find a finite sequence $(\ell_{1},\ell_{2},\ldots,\ell_{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 $G_{t}$ .What are the bounds for $D$ ?

First, we determine the lower bound; let us denote it by $D_{m}$ .This bound will be obtained when $\ell_{i}$ attains the maximum possible value of $2^{i+1}$ for every $1\leq i\leq d-1$ .In other words, we are attaching complete binary trees to $v_{1}$ and $v_{2}$ .Let $a=\lfloor\log_{2}(2q+3)\rfloor$ . Recall that the depth of a complete binary tree with $n$ vertices is $\lfloor\log_{2}(n)\rfloor$ and note that in our case $a-1=d$ . Then

	$\displaystyle\ell_{1}$	$\displaystyle=4,$
	$\displaystyle\ell_{2}$	$\displaystyle=8,$
		$\displaystyle\;\;\vdots$
	$\displaystyle\ell_{a-2}$	$\displaystyle=2^{a-1},$
	$\displaystyle\ell_{a-1}$	$\displaystyle=2q-\sum_{i=1}^{a-2}\ell_{i}=2q-2^{a}+4.$

The above sequence will be called the short sequence and denoted by $L_{m}$ .Using the formula $\sum_{i=1}^{a}ix^{i-1}=(ax^{a+1}-(a+1)x^{a}+1)/(x-1)^{2}$ , we get

$\displaystyle D_{m}$	$\displaystyle=\sum_{i=1}^{a-2}(3t+3+i)2^{i+1}+(3t+a+2)(2q-2^{a}+4)$	(4)
	$\displaystyle=(3t+1)2q+\sum_{i=1}^{a-2}(i+2)2^{i+1}+(a+1)(2q-2^{a}+4)+2\cdot 2%^{1}+1\cdot 2^{0}-5$
	$\displaystyle=(3t+1)2q+\sum_{i=1}^{a}i2^{i-1}+(a+1)(2q-2^{a}+4)-5$
	$\displaystyle=(3t+1)2q+a2^{a+1}-(a+1)2^{a}+1+(a+1)2q-(a+1)2^{a}+4(a+1)-5$
	$\displaystyle=(3t+1)2q+a2^{a+1}-(a+1)2^{a+1}+(a+1)2q+4a$
	$\displaystyle=(3t+1)2q-2^{a+1}+(a+1)2q+4a.$

Lemma 5.

Let $t\geq 3$ . Then there exists $q$ , such that $D_{m}\leq f(t)\leq D^{m}$ .

Proof.

Observe that if $q\sim 4t\sqrt{t}$ then we have $D_{m}\leq f(t)\leq D^{m}$ for large enough $t$ .For small values of $t$ we computed the minimum and maximum value of $q$ that satisfies the conditionof the lemma; see Table4.∎

Note that the value $q$ in Lemma5 is uniquely determined only for $t=3$ .For larger values of $t$ we get a range of options. Any $q$ between $q_{\text{min}}$ and $q_{\text{max}}$ can beused. Moreover, different values of $q$ lead to non-isomorphic graphs $H$ .

$\begin{array}[]{r||rrrrrrrrrrrrrrrr}t&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18%\\\hline\cr q_{\text{min}}&9&17&27&38&50&64&78&94&110&128&146&165&185&205&227&24%9\\\hline\cr q_{\text{max}}&9&21&38&59&85&116&152&192&238&288&344&405&471&542&617%&698\end{array}$

$\begin{array}[]{r||rrrrrrrrrrrrr}t&19&20&21&22&23&24&25&26&27&28&29&30&31\\\hline\cr q_{\text{min}}&272&295&319&344&370&396&422&450&478&506&535&565&595\\\hline\cr q_{\text{max}}&785&876&973&1075&1182&1294&1411&1533&1661&1795&1933&2%077&2225\end{array}$

Now, we show that for every integer $D$ , $D_{m}\leq D\leq D^{m}$ , there exists a finite sequence $(\ell_{1},\ell_{2},\ldots,\ell_{d})$ which realises $D$ .Moreover, the graph $G_{t}$ can be extended to $H$ by attaching trees $T_{1}$ and $T_{2}$ that have $\ell_{i}$ vertices at distance $i$ from $\{v_{1},v_{2}\}$ , such that $H$ is a $2$ -connected cubic graph.

Let us define an operation $\mathcal{M}$ that modifies one such sequence $L=(\ell_{1},\ell_{2},\ldots,\ell_{d})$ .

Definition 6.

Let $L=(\ell_{1},\ell_{2},\ldots,\ell_{d})$ .Set $\ell_{d+1}=0$ .Let $i$ be the smallest value such that $\ell_{i}\geq 3$ and either

(i)
$2(\ell_{i}-1)>\ell_{i+1}+1$ or
(ii)
$\ell_{i}=\ell_{i+1}=3$ .

We say that $\mathcal{M}(L)=(\ell^{\prime}_{1},\ell^{\prime}_{2},\ldots,\ell^{\prime}_{d})$ is a modification of sequence $L$ if $\ell_{j}^{\prime}=\ell_{j}$ for all $j$ , $1\leq j\leq d+1$ , except for $j\in\{i,i+1\}$ , for which $\ell_{i}^{\prime}=\ell_{i}-1$ and $\ell_{i+1}^{\prime}=\ell_{i+1}+1$ .

Lemma 7.

Let $t\geq 1$ and $q\geq 0$ . For every $D$ , $D_{m}\leq D\leq D^{m}$ , there existsa finite sequence $L=(\ell_{1},\ell_{2},\ldots,\ell_{d})$ , such that

(i)
$\sum_{i=1}^{d}\ell_{i}=2q$ ;
(ii)
$2\leq\ell_{i}\leq 2^{i+1}$ for $i<d$ and $1\leq\ell_{d}\leq 2^{d+1}$ ;
(iii)
$\ell_{i+1}\leq 2\ell_{i}$ .

Namely, $L=\mathcal{M}^{D-D_{m}}(L_{m})$ .

Proof.

We start with the short sequence $L_{m}=(4,8,16,\dots)$ . It clearly satisfies conditions (i) to (iii). We have alreadyseen that $L_{m}$ realises $D_{m}$ . This established the base of induction.

Every other $D$ can be realised by a sequence that is obtained from $L_{m}$ by iteratively applying operation $\mathcal{M}$ .Assume that after $(D-1)-D_{m}$ steps we obtained the sequence $L=(\ell_{1},\ell_{2},\dots,\ell_{d})$ which realises $D-1$ .Obviously, $\mathcal{M}(L)$ realises $D$ . It is easy to check that conditions (i) to (iii) are satisfied for $\mathcal{M}(L)$ .∎

Next, we prove two additional properties that hold when operation $\mathcal{M}$ is iteratively applied on $L_{m}$ .

Lemma 8.

Let $t\geq 1$ and $q\geq 0$ . Let $L=(\ell_{1},\ell_{2},\ldots,\ell_{d})$ be obtained from $L_{m}$ by iteratively applying operation $\mathcal{M}$ .Then the following holds:

(i)
If (ii) of Definition6 applies, then $\ell_{j}=2$ for all $j<i$ .
(ii)
If index $i$ in Definition6 is such that $\ell_{i+1}=0$ , then $\ell_{i}\geq 4$ .

Proof.

(i): Observe that if part (ii) of Definition6 applies and $i\geq 2$ , then $\ell_{i-1}=2$ , since otherwise $i-1$ satisfiesthe assumption of the definition, thus $i$ is not the smallest such value.Moreover, if there is $k$ , $k<i$ , with $\ell_{k}\geq 3$ , then choose the largest possible $k$ with this property.Then $\ell_{k+1}=\ell_{k+2}=\dots=\ell_{i-1}=2$ .Hence, $k$ satisfies the assumption of the definition, a contradiction.It means that if part (ii) of the definition applies, then $\ell_{i-1}=\ell_{i-2}=\dots=\ell_{1}=2$ .

(ii): If $\ell_{i+1}=0$ then clearly $\ell_{i}\geq 3$ .Suppose that $\ell_{i}=3$ . Then $\ell_{i-1}=2$ , since otherwise the assumptions apply to $i-1$ .As $2q$ is even, there must be $k<i$ such that $\ell_{k}\geq 3$ .Let $k$ be the largest possible value with this property.Then the assumptions apply to $k$ , a contradiction.Thus, if $\ell_{i+1}=0$ then $\ell_{i}\geq 4$ .∎

Note that part (ii) of Lemma8 means that in the sequence $L^{\prime}=\mathcal{M}(L)$ , $\ell_{i}^{\prime}\geq 3$ and $\ell_{i+1}^{\prime}=1$ . The corresponding graph $H$ will thus have a single vertex of degree $3$ in the final layer.

Example 9.

For an illustration, the sequence of sequences

L_{m},\ \mathcal{M}(L_{m}),\ \mathcal{M}^{2}(L_{m}),\ \mathcal{M}^{3}(L_{m}),\ \ldots

for $2q=20$ is

$\displaystyle(4,8,8),$	$\displaystyle(4,5,6,5),$	$\displaystyle(3,4,5,6,2),$	$\displaystyle(2,3,4,7,4),$	$\displaystyle(2,2,3,5,7,1),$
$\displaystyle(4,7,9),$	$\displaystyle(4,4,7,5),$	$\displaystyle(3,4,4,7,2),$	$\displaystyle(2,3,4,6,5),$	$\displaystyle(2,2,3,5,6,2),$
$\displaystyle(4,6,10),$	$\displaystyle(3,5,7,5),$	$\displaystyle(3,3,5,7,2),$	$\displaystyle(2,3,4,5,6),$	$\displaystyle(2,2,3,4,7,2),$
$\displaystyle(4,6,9,1),$	$\displaystyle(3,5,6,6),$	$\displaystyle(2,4,5,7,2),$	$\displaystyle(2,3,4,4,7),$	$\displaystyle(2,2,3,4,6,3),$
$\displaystyle(4,6,8,2),$	$\displaystyle(3,4,7,6),$	$\displaystyle(2,4,5,6,3),$	$\displaystyle(2,3,3,5,7),$	$\displaystyle(2,2,3,4,5,4),$
$\displaystyle(4,5,9,2),$	$\displaystyle(3,4,6,7),$	$\displaystyle(2,4,4,7,3),$	$\displaystyle(2,2,4,5,7),$	etc.
$\displaystyle(4,5,8,3),$	$\displaystyle(3,4,5,8),$	$\displaystyle(2,3,5,7,3),$	$\displaystyle(2,2,4,5,6,1),$
$\displaystyle(4,5,7,4),$	$\displaystyle(3,4,5,7,1),$	$\displaystyle(2,3,5,6,4),$	$\displaystyle(2,2,4,4,7,1),$

There are altogether $67$ sequences since $D^{m}-D_{m}=66$ when $2q=20$ .

Lemma 10.

Let $t\geq 3$ . There exist rooted trees $T_{1}$ and $T_{2}$ such that vertices $u_{1}$ and $u_{2}$ are Šoltés vertices inthe graph $Q$ obtained from $G_{t}$ by attaching $T_{1}$ and $T_{2}$ to vertices $v_{1}$ and $v_{2}$ .

Proof.

By Lemma5, there exists $q$ such that $D_{m}\leq f(t)\leq D^{m}$ .From Lemma7, we obtain the sequence $L$ , which gives us the appropriate number of vertices inevery layer of the forest $T=T_{1}\cup T_{2}$ . This ensures that $v_{1}$ and $v_{2}$ are Šoltés vertices in $Q$ .

Lemma 11.

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 $T_{1}$ and $T_{2}$ .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\ell_{i-1}=\ell_{i}$ , then either (a) $\ell_{1}=\ell_{2}=\dots=\ell_{i-1}=2$ and $\ell_{i}=4$ , or (b) $\ell_{j}=2^{j+1}$ for all $j\leq i$ .In both subcases $\sum_{j=0}^{i}\ell_{j}$ is even, and no red edge is added between levels $i-1$ and $i$ .Suppose that $2\ell_{i-1}>\ell_{i}$ .Then there is a vertex at $(i-1)$ -st level, say $x$ , whose degree is less than $3$ .If $2\ell_{i}>\ell_{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 $T_{1}$ and $T_{2}$ , then we do not create parallel edges.The only problem occures when $x$ is the unique vertex at level $i-1$ in $T_{j}$ and $y$ is also in $T_{j}$ .But then either $\ell_{i-1}=3$ and $j=2$ , in which case $x$ can be chosen in $T_{1}$ , or $\ell_{i-1}=2$ and $\ell_{i}=3$ in which case $x$ can be chosen in $T_{2}$ and $y$ in $T_{1}$ .)On the other hand, if $2\ell_{i}=\ell_{i+1}$ then (recall that $2\ell_{i-1}>\ell_{i}$ ) $\ell_{1}=\dots=\ell_{i-1}=\ell_{i}=2$ and $\ell_{i+1}=4$ , so $\sum_{j=0}^{i}\ell_{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 $\sum_{j=0}^{i-1}\ell_{j}$ is odd.Assume that we also have to add a red edge between levels $i-1$ and $i$ .Then $\sum_{j=0}^{i}\ell_{j}$ is also odd which means that $\ell_{i}$ is even and that $2\ell_{i-1}>\ell_{i}$ , as shown in Case1.Hence, $2\ell_{i-1}>\ell_{i}+1$ , so there is a vertex at $(i-1)$ -st level, say $x$ , whose degree is less than $3$ .As $2\ell_{i}>\ell_{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 Case1.)∎

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 casethere 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 $T_{1}\cup T_{2}$ ) at level $i$ , then do not choose these leaves;
(ii)
if there is eactly one leaf $w$ at level $i$ , $w\in V(T_{j})$ , then there must be a protected degree-2 vertex at level $i$ in $T_{3-j}$ (i.e.the protected vertex shall not be chosen);
(iii)
if there are two leaves $w$ and $w^{\prime}$ at level $i$ (one of them is in $T_{1}$ and the other in $T_{2}$ , as we will prove later),then one degree- $2$ vertex from $T_{1}$ and one degree- $2$ vertex from $T_{2}$ 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 12.

In each level of $R$ , the sum of free valencies is even.

Proof.

Let $1\leq i\leq d$ .We prove the statement for level $i$ .So denote by $a_{1},a_{2},\dots,a_{\ell_{i}}$ the vertices at $i$ -th level.Our task is to show that $\sum_{j=1}^{\ell_{i}}(3-\deg_{R}(a_{j}))$ is even.We distinguish two cases, with two subcases each.

Case 1: $\sum_{j=0}^{i}\ell_{j}$ is odd.Then there are $\ell_{i}+1$ edges between levels $\ell_{i-1}$ and $\ell_{i}$ in $R$ .If $\ell_{i+1}$ is odd, then $\sum_{j=0}^{i+1}\ell_{j}$ is even, so there are $\ell_{i+1}$ edges between levels $i$ and $i+1$ .Hence, $\sum_{j=1}^{\ell_{i}}(3-\deg_{R}(a_{j}))=3\ell_{i}-\ell_{i}-1-\ell_{i+1}$ is even.On the other hand, if $\ell_{i+1}$ is even, then $\sum_{j=0}^{i+1}\ell_{j}$ is odd, so there are $\ell_{i+1}+1$ edges between levels $i$ and $i+1$ .Hence, $\sum_{j=1}^{\ell_{i}}(3-\deg_{R}(a_{j}))=3\ell_{i}-\ell_{i}-1-\ell_{i+1}-1$ is even.

Case 2: $\sum_{j=0}^{i}\ell_{j}$ is even.Then there are $\ell_{i}$ edges between levels $\ell_{i-1}$ and $\ell_{i}$ in $R$ .If $\ell_{i+1}$ is odd, then $\sum_{j=0}^{i+1}\ell_{j}$ is odd, so there are $\ell_{i+1}+1$ edges between levels $i$ and $i+1$ .Hence, $\sum_{j=1}^{\ell_{i}}(3-\deg_{R}(a_{j}))=3\ell_{i}-\ell_{i}-\ell_{i+1}-1$ is even.On the other hand, if $\ell_{i+1}$ is even, then $\sum_{j=0}^{i+1}\ell_{j}$ is also even, so there are $\ell_{i+1}$ edges between levels $i$ and $i+1$ .Hence, $\sum_{j=1}^{\ell_{i}}(3-\deg_{R}(a_{j}))=3\ell_{i}-\ell_{i}-\ell_{i+1}$ is even.∎

By Lemma12, 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\leq i\leq 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 iffor every leaf $x$ of $T$ , say $x\in V(T_{k})$ , where $1\leq k\leq 2$ and $x$ is a vertex at level $i$ , there is apath, say $P$ , containing only the vertices of level $i$ and connecting $x$ with a vertex, say $y$ , of $T_{3-k}$ .

We refer to the above as the $2$ -connectivity condition.The reason is that $P$ can be completed to a cycle using a $(v_{k},x)$ -path in $T_{k}$ and a $(v_{3-k},y)$ -path in $T_{3-k}$ .Since all cycles constructed in this way contain three vertices of $G_{t}$ ,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 cyclecontaining three vertices of $G_{t}$ .Thus, our attention will be focused on the leaves of $T$ .

Lemma 13.

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 $\sum_{j=1}^{d}\ell_{j}=2q$ is even, each vertex at level $d$ hasdegree $1$ in $R$ .We distinguish three cases.

Case 1: $\ell_{d}\geq 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 satisfythe $2$ -connectivity condition, since $\lceil\ell_{d}/2\rceil$ vertices oflevel $d$ are in $T_{1}$ and $\lfloor\ell_{d}/d\rfloor$ of them are in $T_{2}$ .

Case 2: $\ell_{d}=1$ .Then $\ell_{d-1}\geq 3$ , as already shown.In this case, we replace the sequence $L=(\ell_{1},\ell_{2},\dots,\ell_{d-1},1)$ by $L^{*}=(\ell_{1},\ell_{2},\dots,\ell_{d-1},3)$ and we find a 2-connected cubicgraph $H^{*}$ realizing $L^{*}$ .In this graph, the pendant vertices of level $d$ are connected to threedifferent vertices of level $d-1$ in $T$ , since at each level we minimised the number of degree- $3$ vertices.Since $\sum_{j=1}^{d}\ell_{j}$ is even, there are no other edges connectingvertices of level $d-1$ with those of level $d$ in $R$ .Hence, we add a $3$ -cycle as described in Case1, and then contract thethree vertices at level $d$ to a single vertex.If $H^{*}$ is cubic and $2$ -connected, then so is the resulting graph $H$ .

Case 3: $\ell_{d}=2$ .In this case, we simultaneously resolve the problem for levels $d$ and $d-1$ .Since $\sum_{j=1}^{d-1}\ell_{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 ofvertices of degree $3$ was minimised.)

If $\ell_{d-1}=2$ , then connect both vertices of level $d-1$ with bothvertices 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 satisfythe 2-connectivity condition.

If $\ell_{d-1}\geq 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 satisfythe $2$ -connectivity condition in the strict sense.Nevertheless, there is a cycle in $H$ which contains edges of $G_{t}$ , a pathconnecting $v_{1}$ with a vertex of level $d$ in $T_{1}$ , a path connecting $v_{2}$ with a vertex of level $d$ in $T_{2}$ , 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 pathpassing through all vertices of level $d-1$ except $x$ , and starting/endingin the two degree- $2$ vertices.This resolves the problem for levels $d$ and $d-1$ . This concludes Case3.

We now turn to level $i$ , $1\leq i<d$ . In case $\ell_{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 connectingvertices 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 ofcreating $R$ .

If there is no leaf at level $i$ , then all vertices of this levelhave degrees $2$ and $3$ in $R$ .By Lemma12, there is an even number of degree- $2$ vertices.Thus, we can add a collection of independent edges so that all vertices oflevel $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 novertices 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, $T_{1}$ and $T_{2}$ have, respectively, $\lceil\ell_{i}/2\rceil-\lceil\ell_{i+1}/2\rceil$ and $\lfloor\ell_{i}/2\rfloor-\lfloor\ell_{i+1}/2\rfloor$ leaves at level $i$ .Denote $k=(\lceil\ell_{i}/2\rceil-\lceil\ell_{i+1}/2\rceil)-(\lfloor\ell_{i}/2\rfloor-%\lfloor\ell_{i+1}/2\rfloor)$ .Since $k=(\lceil\ell_{i}/2\rceil-\lfloor\ell_{i}/2\rfloor)-(\lceil\ell_{i+1}/2\rceil-%\lfloor\ell_{i+1}/2\rfloor)$ ,we have

-1\leq k\leq 1.

(6)

This means that the numbers of leaves at level $i$ in $T_{1}$ and $T_{2}$ 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 $b_{1}$ and $b_{2}$ ,such that $b_{1}\in V(T_{1})$ , $b_{2}\in V(T_{2})$ and $b_{1},b_{2}$ are not leaves in $T$ .(Recall that if $i=d-1$ and $\ell_{d}=1$ , then then we solve this case for $L^{*}$ where $\ell_{d}=3$ , and afterwards we provide the contraction of vertices at level $d$ , see Case2 above.)Then $\deg_{T}(b_{1})=\deg_{T}(b_{2})=2$ .We distinguish three cases.

Case1: $T$ has at least $3$ leaves at level $i$ .If $E(R)\setminus E(T)$ contains an edge connecting levels $i-1$ and $i$ , then thisedge will terminate at $b_{1}$ , and if $E(R)\setminus E(T)$ contains an edge connectinglevels $i$ and $i+1$ , then this edge will start at $b_{2}$ .(Note that if we create $T$ and $R$ simultaneously, level by level, then we can form $b_{1}$ and $b_{2}$ , so that we do not get parallel edges.In the worst case we relabel $b_{1}$ and $b_{2}$ , so that $b_{1}\in V(T_{2})$ and $b_{2}\in V(T_{1})$ .)This leaves the leaves untouched.Then we add a cycle passing through all leaves of level $i$ and adda 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 $T_{1}$ and at least one is in $T_{2}$ , the vertices at level $i$ satisfy the $2$ -connectivitycondition.

Case2: $T$ has exactly two leaves at level $i$ .Denote these vertices by $a_{1}$ and $a_{2}$ .As mentioned above, we may assume that $a_{1}\in V(T_{1})$ and $a_{2}\in V(T_{2})$ .If $E(R)\setminus E(T)$ contains an edge connecting levels $i-1$ and $i$ , then thisedge will terminate at $a_{1}$ , and if $E(R)\setminus E(T)$ contains an edge connectinglevels $i$ and $i+1$ , then this edge will start at $a_{2}$ .(Again, not to create parallel edges, the red edge between levels $i-1$ and $i$ may be connected to $a_{2}$ instead of $a_{1}$ , and then possible red edge between levels $i$ and $i+1$ will start at $a_{1}$ .)Then add edges $a_{1}b_{2}$ , $a_{2}b_{1}$ , and a collection of independent edges sothat all vertices of level $i$ become degree- $3$ vertices.Due to the presence of edges $a_{1}b_{2}$ and $a_{2}b_{1}$ , the vertices at level $i$ satisfy the $2$ -connectivity condition.

Case3: $T$ has exactly one leaf at level $i$ .Denote this vertex by $a$ .Without loss of generality, assume that $a\in V(T_{1})$ .If $E(R)\setminus E(T)$ contains an edge connecting levels $i-1$ and $i$ , then thisedge will terminate at $b_{1}$ , and if $E(R)\setminus E(T)$ contains an edge connectinglevels $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 $b_{1}$ , and then possible red edge between levels $i$ and $i+1$ will start at $b_{1}$ .)Then add the edge $ab_{2}$ , and a collection of independent edges sothat all vertices of level $i$ become degree- $3$ vertices.Due to the presence of edge $ab_{2}$ , vertices at level $i$ satisfy the $2$ -connectivitycondition.∎

3 Cubic $\boldsymbol{2}$ -connected graphs with $\boldsymbol{2^{r}}$ Šoltés vertices

Now we generalise Theorem4 to higher amount of Šoltés vertices.

Theorem 14.

Let $r\geq 1$ .There exist infinitely many cubic $2$ -connected graphs $G$ which contain at least $2^{r}$ Šoltés vertices.

Proof.

We reconsider the graph $G_{t}$ from the proof of Theorem4.This graph consists of a chain of $2t$ diamonds attached to vertices $z_{1}$ and $z_{2}$ of a graph on $8$ vertices.Denote this graph on $8$ vertices by $F$ .

We construct $G_{t,r}$ .Take a binary tree $B$ of depth $r-1$ .This tree has $2^{r}-1$ vertices, out of which $2^{r-1}$ are leaves.Denote these leaves by $a_{1},a_{2},\dots,a_{2^{r-1}}$ .Let $B^{\prime}$ be a copy of $B$ .To distinguish endvertices of $B^{\prime}$ from those of $B$ , put to the endvertices of $B^{\prime}$ dashes.Now take $2^{r-1}$ chains of $2t$ diamonds and identify the ends (the vertices of degree $2$ ) of $k$ -th chain with $a_{k}$ and $a^{\prime}_{k}$ , respectively.Finally, join the roots of $B$ and $B^{\prime}$ (i.e., the vertices of degree $2$ ) by edges to $z_{1}$ and $z_{2}$ .

Denote by $G_{t,r}$ the resulting graph, see Figure5 for $G_{3,2}$ .Then $G_{t,r}$ has $8t2^{r-1}+2(2^{r-1}-1)+8$ vertices.Moreover, all central vertices of $2^{r-1}$ chains of diamonds belong to the same orbit of $G_{t,r}$ .Observe that there are $2^{r}$ such vertices.Let $u_{1}$ and $u_{2}$ be central vertices of one of the chains of diamonds.If we show that $\lim_{t\to\infty}(W(G_{t,r}-u_{1})-W(G_{t,r}))=\infty$ , we can complete $G_{t,r}$ analogously as $G_{t}$ was completed to $H$ in the proof of Theorem4, to obtain a cubic $2-$ connected graph with at least $2^{r}$ Šoltés vertices.

Thus, it remains to show that $W(G_{t,r}-u_{1})-W(G_{t,r})$ tends to infinity as $t\to\infty$ .Observe that $W(G_{t,r}-u_{1})-W(G_{t,r})$ equals

\sum_{x,y\in V(G_{t,r})\setminus\{u_{1}\}}\Big{(}d_{G_{t,r}-u_{1}}(x,y)-d_{G_{%t,r}}(x,y)\Big{)}-w_{G_{t,r}}(u_{1}).

We first estimate $w_{G_{t,r}}(u_{1})$ from above.For small $i$ , there are at most $4$ vertices at distance $i$ from $u_{1}$ .For bigger $i$ the amount of vertices at distance $i$ grows, but it cannot exceed $4\cdot 2^{r}+8$ since there are $2^{r-1}$ chains attached to $F$ and $F$ itself has $8$ vertices.Thus, $w_{G_{t,r}}(u_{1})\leq(2^{r+2}+8)\sum_{i=1}^{1+3t+2r+3t+3}i$ .And if we held $r$ constant, $w_{G_{t,r}}(u_{1})$ can be bounded from above by a quadratic polynomial in $t$ .

Now we estimate $\sum_{x,y\in V(G_{t,r})\setminus\{u_{1}\}}\big{(}d_{G_{t,r}-u_{1}}(x,y)-d_{G_{%t,r}}(x,y)\big{)}$ from below.For every $x,y\in V(G_{t,r})\setminus\{u_{1}\}$ we have $d_{G_{t,r}-u_{1}}(x,y)\geq d_{G_{t,r}}(x,y)$ , since $G_{t,r}$ has all paths which exist in $G_{t,r}-u_{1}$ .However, it suffices to consider only $x,y$ being in the same chain of diamonds as $u_{1}$ .Observe that the distance from $u_{2}$ to a neighbour of $u_{1}$ ( $\neq u_{2}$ ) is $2$ in $G_{t,r}$ , but it is at least $6t$ in $G_{t,r}-u_{1}$ (with equality if $r=1$ , i.e. if $G_{t,r}=G_{t}$ ).So this distance is increased at least by $6t-2$ .The distance from $u_{2}$ to the second neighbour of $u_{1}$ is increased at least by $6t-4$ , etc.However, we should consider also a neighbour of $u_{2}$ ( $\neq u_{1}$ ).For this vertex the distances are increased at least by $6t-4$ , $6t-6$ , …Summing up,

D\geq\sum_{j=1}^{3t-1}\sum_{i=1}^{j}2i=2\sum_{j=1}^{3t-1}\binom{j+1}{2}=2%\binom{3t+1}{3}.

Consequently, $W(G_{t,r}-u_{1})-W(G_{t,r})$ is bounded from below by a cubic polynomial (in $t$ ) with leading coefficient $9$ .Thus, $\lim_{t\to\infty}(W(G_{t,r}-u_{1})-W(G_{t,r}))=\infty$ as required.∎

4 Concluding remarks and further work

We believe that if there exists another Šoltés graph in addition to $C_{11}$ , 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 lessthan $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 $C_{11}$ .

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. $\operatorname{CVT}(n,i)$ denotes the $i$ -th graph of order $n$ in the census.No Šoltés graph has been found, but the searchrevealed that there exist graphs that are $\frac{1}{3}$ -Šoltés, i.e. $\frac{1}{3}$ of all verticesare Šoltés vertices. We found $7$ cubic $\frac{1}{3}$ -Šoltés graphs; all of them are trunctationsof certain cubic vertex-transitive graphs. In this paper, the truncation of a graph $G$ is denoted by $\operatorname{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 forone vertex from each orbit only. Here is the list of cubic vertex-transitive graphs $G$ ,such that $\operatorname{Tr}(G)$ is a $\frac{1}{3}$ -Šoltés graph:

	$\displaystyle\operatorname{CVT}(384,805),$	$\displaystyle\operatorname{CVT}(600,259),$	$\displaystyle\operatorname{CVT}(768,3650),$	$\displaystyle\operatorname{CVT}(1000,302),$
	$\displaystyle\operatorname{CVT}(1056,538),$	$\displaystyle\operatorname{CVT}(1056,511),$	$\displaystyle\operatorname{CVT}(1280,967).$

Interestingly, all these graphs are Cayley graphs. Several properties of these graphs are listedin the Appendix. The graph $\operatorname{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.

Problem 15.

Find an infinite family of cubic vertex-trainsitive graphs $\{G_{i}\}_{i=1}^{\infty}$ , such that $\operatorname{Tr}(G_{i})$ isa $\frac{1}{3}$ -Šoltés graph for all $i\geq 1$ .

Moreover, we also found an example of a $4$ -regular $\frac{1}{3}$ -Šoltés graph, namelythe graph $L(\operatorname{CVT}(324,104))$ . It has order $486$ and isthe line graph of $\operatorname{CVT}(324,104)$ , which is a Cayley graph.More data can be found in the Appendix.

Of course, $\frac{1}{3}$ -Šoltés is still a long way from being Šoltés.The next conjecture is additionally reinforced by the fact that there are no Šoltés graphs amongvertex-transitive graphs with less than $48$ vertices.

Conjecture 16.

The cycle on eleven vertices, $C_{11}$ , is the only Šoltés graph.

Acknowledgments.The first 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 second author acknowledges partial support by Slovak research grants VEGA 1/0567/22, VEGA 1/0206/20,APVV–19–0308, and APVV–22–0005.The second and third authors acknowledge partial support of the Slovenian researchagency ARRS; program P1-0383 and ARRS project J1-3002.

References

[1]M.Akhmejanova, K.Olmezov, A.Volostnov, I.Vorobyev, K.Vorob’ev, Y.Yarovikov,Wiener index and graphs, almost half of whose vertices satisfy Šoltés property,Discrete Applied Mathematics,
[2]H.U.Besche, B.Eick, 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á, J.Maxová,A relaxed version of Šoltés’s problem and cactus graphs,Bull.Malays.Math.Sci.Soc. 44 (2021) 3733–3745.
[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, G.Royle,A census of small transitive groups and vertex-transitive graphs,J.Symb.Comput. 101 (2020) 51–60.
[6]Y.Hu, Z.Zhu, P.Wu, Z.Shao, A.Fahad,On investigations of graphs preserving the Wiener index upon vertex removal,AIMS Math. 6 (2021) 12976–12985.
[7]M.Knor, S.Majstorović, R.Škrekovski,Graphs whose Wiener index does not change when a specific vertex is removed,Discrete Appl.Math. 238 (2018) 126–132.
[8]M.Knor, S.Majstorović, R.Škrekovski,Graphs preserving Wiener index upon vertex removal,Appl.Math.Comput. 338 (2018) 25–32.
[9]M.Knor, R.Škrekovski, A.Tepeh,Mathematical aspects of Wiener index,Ars Math.Contemp. 11 (2016) 327–352.
[10]B.D.McKay,Description of graph6, sparse6 and digraph6 encodings,http://users.cecs.anu.edu.au/~bdm/data/formats.txt.
[11]B.D.McKay, A.Piperno,Practical graph isomorphism, II,J.Symb.Comput. 60 (2014) 94–112.
[12]OEIS Foundation Inc.(2022),Entry A006799 in The On-Line Encyclopedia of Integer Sequences,https://oeis.org/A006799.
[13]P.Potočnik, P.Spiga, G.Verret,Cubic vertex-transitive graphs on up to $1280$ vertices,J.Symb.Comput. 50 (2013) 465–477.
[14]G.Royle, D.Holt, Vertex-transitive graphs on fewer than $48$ vertices [Data set],Zenodo, https://doi.org/10.5281/zenodo.4010122.
[15]Ľ.Šoltés,Transmission in graphs: A bound and vertex removing,Math.Slovaca 41 (1991) 11–16.
[16]S.Spiro,The Wiener index of signed graphs,Appl.Math.Comput. 416 (2022) 126755.
[17]H.Wiener,Structural determination of paraffin boiling points,J.Am.Chem.Soc. 69 (1947) 17–20.

5 Appendix

There are $7$ cubic vertex-transitive graphs $G$ on up to $1280$ vertices,such that $\operatorname{Tr}(G)$ is a $\frac{1}{3}$ -Šoltés graph. Since all these graphare Cayley graphs, we give the generating set for the Cayley graph.Note that the group itself (its permutation representation) is givenimplicitly by these generators;however, we also give the group’s ID from GAP’s library of small groups [2]. $\operatorname{SmallGroup}(n,k)$ is the $k$ -th group of order $n$ from that library.We also calculated girth, diameter and tested all graphsfor bipartiteness.

•

$\operatorname{CVT}(384,805)$ :

	$\displaystyle\operatorname{Group}([$	$\displaystyle(2,4)(6,12,17,19,18,14)(7,10,20)(8,15,16,9,11,13),$
		$\displaystyle(1,4)(2,3)(5,13)(6,18)(7,17)(8,15)(9,12)(10,14)(11,19)(16,20)])$
		$\displaystyle\cong\operatorname{SmallGroup}(384,5781)$

girth: 6;diameter: 10;bipartite? True

•

$\operatorname{CVT}(600,259)$ :

	$\displaystyle\operatorname{Group}([$	$\displaystyle(1,2)(3,4)(5,6)(7,9)(8,10)(13,14)(16,17),$
		$\displaystyle(1,3)(5,7)(6,8)(9,12)(10,13)(11,14)(15,16),$
		$\displaystyle(1,4)(2,3)(5,6)(8,11)(9,10)(13,14)(15,17)])$
		$\displaystyle\cong\operatorname{SmallGroup}(600,103)$

girth: 10;diameter: 13;bipartite? True

•

$\operatorname{CVT}(768,3650)$ :

	$\displaystyle\operatorname{Group}([$	$\displaystyle(2,3)(4,7)(5,6)(10,12),$
		$\displaystyle(2,4)(3,5)(6,7)(9,10)(11,12),$
		$\displaystyle(1,2)(3,6)(4,8)(5,7)])$
		$\displaystyle\cong\operatorname{SmallGroup}(768,1090104)$

girth: 8;diameter: 16;bipartite? False

•

$\operatorname{CVT}(1000,302)$ :

	$\displaystyle\operatorname{Group}([$	$\displaystyle(4,5)(6,7)(9,14)(10,18)(11,21)(12,23)(13,25)(15,24)(16,27)(17,29)$
		$\displaystyle\quad(19,26)(20,31)(22,28)(30,32),$
		$\displaystyle(1,2)(3,4)(5,6)(8,9)(10,15)(11,19)(12,18)(13,21)(14,23)(16,17)(20%,27)$
		$\displaystyle\quad(22,29)(24,31)(25,32)(26,28),$
		$\displaystyle(1,2)(8,17)(9,27)(10,11)(12,26)(13,24)(14,22)(15,18)(16,30)(20,32)$
		$\displaystyle\quad(21,28)(23,31)(25,29)])$
		$\displaystyle\cong\operatorname{SmallGroup}(1000,105)$

girth: 10;diameter: 15;bipartite? True

•

$\operatorname{CVT}(1056,538)$ :

	$\displaystyle\operatorname{Group}([$	$\displaystyle(2,3)(4,5)(6,8)(7,10)(9,11)(13,14)(15,16)(17,18)(19,20)(21,22),$
		$\displaystyle(1,2)(4,6)(7,9)(12,13)(14,15)(16,17)(18,19)(20,21),$
		$\displaystyle(4,7)(6,9)(10,11)(12,13)(14,15)(16,17)(18,19)(20,21)])$
		$\displaystyle\cong\operatorname{SmallGroup}(1056,493)$

girth: 4;diameter: 22;bipartite? True

•

$\operatorname{CVT}(1056,511)$ :

	$\displaystyle\operatorname{Group}([$	$\displaystyle(2,3)(12,13)(14,15)(16,17)(18,19)(20,21),$
		$\displaystyle(1,2)(4,5)(6,7)(8,9)(10,11)(12,14)(15,16)(17,18)(19,20)(21,22),$
		$\displaystyle(5,6)(7,8)(9,10)(12,13)(14,15)(16,17)(18,19)(20,21)])$
		$\displaystyle\cong\operatorname{SmallGroup}(1056,468)$

girth: 4;diameter: 22;bipartite? True

•

$\operatorname{CVT}(1280,967)$ :

	$\displaystyle\operatorname{Group}([$	$\displaystyle(1,2)(3,5)(7,9)(8,11)(10,15)(12,19)(13,20)(14,22)(16,25)(17,27)$
		$\displaystyle\quad(18,29)(21,32)(23,34)(24,30)(26,31)(28,37),$
		$\displaystyle(1,3)(4,5)(6,7)(8,12)(9,13)(10,16)(11,17)(15,23)(18,30)(20,31)$
		$\displaystyle\quad(21,27)(22,25)(24,28)(26,36)(29,33)(35,37),$
		$\displaystyle(1,4)(2,3)(6,8)(7,10)(9,14)(11,18)(12,20)(13,21)(15,24)(16,26)$
		$\displaystyle\quad(17,28)(19,29)(22,33)(23,35)(25,30)(27,36)(31,34)(32,37)])$
		$\displaystyle\cong\operatorname{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 $\frac{1}{3}$ -Šoltés graph.

•

$\operatorname{CVT}(324,104)$ :

	$\displaystyle\operatorname{Group}([$	$\displaystyle(2,9)(3,4)(5,7)(6,8),$
		$\displaystyle(1,5)(2,6)(3,9)(4,7),$
		$\displaystyle(2,9)(3,6)(4,8)])$
		$\displaystyle\cong\operatorname{SmallGroup}(324,39)$

girth: 4;diameter: 12;bipartite: True

$\displaystyle D^{m}$	$\displaystyle=2(3t+4)+2(3t+5)+\dots+2(3t+3+q)$	(5)
	$\displaystyle=(3t+3)2q+2\sum_{i=1}^{q}i$
	$\displaystyle=(3t+1)2q+q^{2}+5q.$

On regular graphs with Šoltés vertices (2024)

Abstract

1 Introduction

Conjecture 1.

Conjecture 2.

Conjecture 3.

2 Cubic 𝟐2\boldsymbol{2}bold_2-connected graphs with two Šoltés vertices

Theorem 4.

Lemma 5.

Proof.

Definition 6.

Lemma 7.

Proof.

Lemma 8.

Proof.

Example 9.

Lemma 10.

Proof.

Lemma 11.

Proof.

Lemma 12.

Proof.

Observation.

Lemma 13.

Proof.

3 Cubic 𝟐2\boldsymbol{2}bold_2-connected graphs with 𝟐𝒓superscript2𝒓\boldsymbol{2^{r}}bold_2 start_POSTSUPERSCRIPT bold_italic_r end_POSTSUPERSCRIPT Šoltés vertices

Theorem 14.

Proof.

4 Concluding remarks and further work

Problem 15.

Conjecture 16.

References

5 Appendix

References

2 Cubic $\boldsymbol{2}$ -connected graphs with two Šoltés vertices

3 Cubic $\boldsymbol{2}$ -connected graphs with $\boldsymbol{2^{r}}$ Šoltés vertices