\documentclass[10pt]{amsart}
\usepackage[cp1251]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{graphicx}

\def\udcs{519.17} %Здесь автор определяет УДК своей работы
\def\mscs{05C09} %Здесь автор определяет классификаторы AMS своей работы
\setcounter{page}{144}

\newtheorem{theorem}{Theorem}
\newtheorem{proposition}{Proposition}
\newtheorem{corollary}{Corollary}
\newtheorem{problem}{Problem}

\def\logo{{\bf\huge S\raisebox{0.2ex}{\hspace{0.55ex}\raisebox{0.05ex}e\hspace{-1.65ex}$\bigcirc$}MR}}

\def\semrtop
     {
  \vbox{
     \noindent\logo
     \hspace{80mm}\raisebox{1ex}{ISSN 1813-3304 }

     \vspace{5mm}

     \begin{center}
     {\huge СИБИРСКИЕ \ ЭЛЕКТРОННЫЕ} \\[2mm]
     {\huge МАТЕМАТИЧЕСКИЕ ИЗВЕСТИЯ} \\[2mm]
     {\large Siberian Electronic Mathematical Reports} \\[1mm]
     {\LARGE\tt{http://semr.math.nsc.ru}}\\[0.5mm]
%     {\small Институт математики им. С.Л.Соболева СО РАН}\\[-1mm]
%     {\small Sobolev Institute of Mathematics SB RAS}
     \end{center}
     \vspace{-3mm}
     \noindent
     \begin{tabular}{c}
     \hphantom{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa} \\
     \hline\hline
     \end{tabular}

     \vspace{1mm}
     {\flushleft\it Том 20, стр. 144--144 (2023) \hspace{63mm}{\rm\small УДК \udcs}}
     \newline
     	{\rm\small DOI~10.33048/semi.2019.16.xxx}\hphantom{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaai}{\rm\small MSC\  \mscs }
  }%\vbox
}

\begin{document}
\renewcommand{\refname}{References}
\renewcommand{\figurename}{Fig.}
\renewcommand{\tablename}{Table}

\thispagestyle{empty}

\title[On the preservation of the Wiener index]
{On the preservation of the Wiener index of cubic graphs upon vertex removal}
\author{{A.A. DOBRYNIN}}%
\address{Andrey Alekseevich Dobrynin  % Контактные данные всех авторов и место работы указываются только на английском языке
\newline\hphantom{iii} Sobolev Institute of Mathematics,
\newline\hphantom{iii} pr. Koptyuga, 4,
\newline\hphantom{iii} 630090, Novosibirsk, Russia}%
\email{dobr@math.nsc.ru}%

\thanks{\sc Dobrynin, A.A.,
On the preservation of the Wiener index of cubic graphs upon vertex removal}
\thanks{\copyright \ 2023 Dobrynin A.A}
\thanks{\rm This work was supported by the Russian Science Foundation under grant 23-21-00459.}
\thanks{\it Received February, 3, 2023, published October 2, 2023}%


\semrtop \vspace{1cm}
\maketitle {\small
\begin{quote}
\noindent{\sc Abstract. }
The Wiener index, $W(G)$, is the sum of distances between all
vertices of a connected graph $G$.
 In 2018, Majstorovi\'{c}, Knor and \v{S}krekovski
posed the problem of finding $r$-regular graphs except cycle $C_{11}$ having at least
one vertex $v$ with property $W(G)=W(G-v)$.
An infinite family of cubic graphs with four such vertices
is constructed.\medskip

\noindent{\bf Keywords:} distance invariant, Wiener index, \v{S}olt\'{e}s problem.
 \end{quote}
}

\section{Introduction}

All graphs $G$ considered in this paper are simple and connected.
The cardinality of the vertex set $V(G)$ is called the order of $G$.
Denote by $G-v$ the graph obtained by removing a vertex $v$ from $G$.
The distance $d(u,v)$ between vertices
$u,v \in V(G)$ is the number of edges on a shortest path connecting
these vertices in $G$.
The vertex distance for $v \in V(G)$  is defined as the sum
of distances from $v$ to all the other vertices of $G$,
$d_G(v)=\sum_{u\in V(G)} d(v,u)$.
A half of the sum of vertex distances is the Wiener index of $G$
that has found numerous applications
\cite{Dobr01,Dobr02,Gutm86,Knor16,Trin83},
$$
W(G)=\frac{1}{2} \sum_{v\in V(G)} d_G(v).
$$

One of directions in the study of the Wiener index is that
how it changes under graph transformations.
In 1991, \v{S}olt\'{e}s posed the following problem:
find all graphs $G$ having the property $W(G)=W(G-v)$ for all vertices $v$ of $G$
\cite{Solt91}.
Such graphs will be called  \v{S}olt\'{e}s graphs.
The simple cycle $C_{11}$ is the unique known example of \v{S}olt\'{e}s graphs.
Unsuccessful attempts to find new \v{S}olt\'{e}s graphs led to the
formulations of various relaxed problems
\cite{Akhm2020,Bok19,Bok21,Knor18-1,Knor18-2,Majs18,Hu21}.
The following problem was proposed in \cite{Knor18-2}:

\begin{problem} \label{Problem1}
Are there $r$-regular connected graphs $G$ other than $C_{11}$ for which
the equality $W(G)=W(G-v)$ holds for at least one vertex $v\in V(G)$?
\end{problem}

In this paper, an infinite family of cubic graphs having
four such vertices $v$ is constructed.

\section{Main result}

Consider a cubic graph $G$ of order $2(2k + s + 2)$ shown in Fig.~\ref{Fig1}.
It consists of the left and right symmetrical ladders with
$k$ rungs and the middle ladder  between them with $s$ rungs.
Let ${\mathcal G}_{k,s}$
be a family of such graphs where $k \ge 4$ and $s \ge 2$.
The following statement is the basis for solving 
Problem~\ref{Problem1} for the case of cubic graphs ($r=3$).

\begin{figure}[h]
\center{\includegraphics[width=0.95\linewidth]{Figure_1.eps}}
\caption{Cubic graph $G \in {\mathcal G}_{k,s}$.}
\label{Fig1}
\end{figure}


\begin{proposition} \label{Prop1}
Let $G \in {\mathcal G}_{k,s}$ and integers $k$ and $s$ are even. Then
\begin{align*}
W(G)           & =   3k^3 + \frac{1}{2}k^2(12s + 39) + k(4s^2 + 20s + 19) \\
               & \phantom{=} \ + \frac{1}{3}s(2s^2 + 15s + 34) + 8, \\[1mm]
W(G-u_{s/2})   & =  3k^3 + \frac{1}{2}k^2(12s + 41) + k(4s^2 + 20s + 15) \\
               & \phantom{=} \ + \frac{1}{3}s(2s^2 + 15s + 28) + 4.
\end{align*}
\end{proposition}


The proof of this proposition will be given in the next section.

Since $W(G)-W(G-u_{s/2})= -k^2 + 4k + 2s + 4$
and vertices $u_{s/2},u_{s/2+1}, u'_{s/2}$, and $u'_{s/2+1}$ belong
to the same orbit of the automorphism group of $G$,
we obtain the following result.

\begin{corollary} \label{Corol-1}
If $k\ge 6$ is even and $s=(k^2-4k-4)/2$, then a cubic graph $G\in {\mathcal G}_{k,s}$
has four vertices $v$ for which $W(G)=W(G-v)$.
\end{corollary}

Table~\ref{ParamEven} contains order and the Wiener index  of graphs
$G\in {\mathcal G}_{k,s}$
of Corollary \ref{Corol-1} for the initial values of $k$ and $s$.


\begin{table}[h]
\centering
\caption{Graphs $G \in {\mathcal G}_{k,s}$ for even $k \ge 6$.} \label{ParamEven}
%\vspace{0.6mm} % additional space after caption
\begin{tabular}{rrrr} \hline
%\rule{0cm}{2mm}  % additional space after line
$k$ & $s$  &  $ |V(G)|$ &  $W(G)$   \\ \hline
6   &  4   &  36  \ \   &     3368  \\
8   &  14  &  64  \ \   &    19800  \\
10  &  28  &  100 \ \   &    77780  \\
12  &  46  &  144 \ \   &   236572  \\
14  &  68  &  196 \ \   &   603792  \\
16  &  94  &  256 \ \   &  1356528  \\
18  &  124 &  324 \ \   &  2766300  \\
20  &  158 &  400 \ \   &  5227860  \\
\hline
\end{tabular}
\end{table}


\section{Proof of Proposition \ref{Prop1}}
If distances $d_G(u,v)$ are considered in graph $G$, then
we will drop the subscript $G$.
Let $d(X,Y)$ be the sum of distances between
vertices of subsets $X$ and $Y$ in a graph,
$d(X,Y)= \sum_{x\in X, y\in Y} d(x,y)$.
Denote by $p_n$ and $c_n$ the distances of a pendent
vertex of  the simple path $P_n$ and a vertex of the simple
cycle $C_n$ of order $n$, respectively.
It is known that $p_n=n(n-1)/2$ and $c_n=n^2/4$ for even $n$, and
$W(P_n)=n(n^2-1)/6$.

Let $G \in {\mathcal G}_{k,s}$ where $k$ and $s$ are even.
Divide the vertex set of $G$ into eight disjoint subsets:
$V =\{v_1,v_2,\dots,v_k\}$,
$V' =\{v'_1,v'_2,\dots,v'_k\}$,
$W =\{w_1,w_2,\dots,w_k\}$,
$W' =\{w'_1,w'_2,\dots,w'_k\}$,
$U =\{u_1,u_2,\dots,u_s\}$,
$U' =\{u'_1,u'_2,\dots,u'_s\}$,
$A =\{a,a'\}$, and
$B =\{b,b'\}$
(see Fig.~\ref{Fig1}).
Denote by $L$, $R$, and $M$ the induced subgraphs of $G$
with vertex sets $V\cup V' \cup A$, $W\cup W' \cup B$,
and  $U\cup U'$, respectively.
Then the Wiener index of $G$ can be represented as the sum of several parts:
\begin{align} \label{WG}
W(G) & =  \frac{1}{2} [\, d(L,L) + d(R,R) +  d(M,M) \,] + d(L,R) + d(L,M) + d(R,M) \nonumber \\[1mm]
     & =  \frac{1}{2} d(M,M) + d(L,L) + d(L,R) + 2d(L,M).
\end{align}
The last equality is valid due to the symmetric structure of $G$.
Next we will calculate the summands of equation (\ref{WG}) .

1. Consider distances between vertices of subgraph $M$.
For vertices $u_i \in V(M)$, $i=1,2,\dots,s$, we have
$$
d(u_i) = \sum_{j=1}^{s} d(u_i,u_j)+ \sum_{j=1}^{s} d(u_i,u_j')= 2 d_{P_s}(u_i)+ s.
$$
By symmetry of $G$, $d(u_i)=d(u'_i)$, $i=1,2,\dots,s$. Then
\begin{align*}
d(M,M) & = 2\sum_{i=1}^{s} d(u_i) = 2\sum_{i=1}^{s} (2d_{P_s}(u_i)+ s)=2(4W(P_s)+s^2) \\
       & = \frac{2}{3}s(s + 2)(2s - 1).
\end{align*}

2. Consider distances between vertices of subgraphs $L$ and $M$.
Since vertices $v_i$ and $v'_i$, $i=1,2,\dots,k$, belong to the same orbit
of the automorphism group of $G$, we can write
\begin{align*}
d(u_i,L) & =  2\sum_{j=1}^{k/2} [d(u_i,a)+d(a,v_j)] + 2\sum_{j=k/2+1}^{k} [d(u_i,a')+d(a',v_j)] \\
         & \phantom{=} \ + d(u_i,a) + d(u_i,a')  \\[1mm]
         & =  2\left( \frac{k}{2} i    + \sum_{j=1}^{k/2} d(a,v_j) \right) +
              2\left(\frac{k}{2} (i+1) + \sum_{j=k/2+1}^{k} d(a',v_j) \right) + 2i +1 \\[1mm]
         & = (k+1)(2i+1) + 4p_{k/2+1} =  \frac{1}{2} k^2 + 2k(i+1) + 2i + 1.
\end{align*}
By symmetry of vertices of $U$ and $U'$,
\begin{equation*}
d(L,M) = \sum_{i=1}^{s} d(u_i,L) + \sum_{i=1}^{s} d(u'_i,L) = s(k^2 + 2k(s + 3) + 2(s + 2)).
\end{equation*}


3. Consider distances between vertices of subgraphs $L$ and $R$.
Note that $d(v_i,a)+d(a,u_1) < d(v_i,a')+d(a',u_1')$, $i=1, 2,\dots,k/2$
(see Fig.~\ref{Fig1}).
This implies that all shortest paths from vertices of $L$ to vertices of $R$
lie in the subgraph shown in
Fig.~\ref{Fig2}.


\begin{figure}[h]
\center{\includegraphics[width=0.75\linewidth]{Figure_2.eps}}
\caption{Subgraphs with the shortest paths for $d(L,R)$.}
\label{Fig2}
\end{figure}


By symmetry of $L$ and $R$,
it is sufficient to calculate distances from vertices
$v_i$, $i=1,2,\dots,k/2$. Then
$$
d(L,R) =  4 \sum_{i=1}^{k/2} [2d(v_i,W) + d(v_i,B)]  + 2 [2d(a,W) + d(a,B)].
$$
We have
$d(v_i,W)= \sum_{j=1}^{k} [d(v_i,u_1)+d(u_1,w_j)]=k(i+1)+c_{k+2s+2}-p_{s+1}-p_{s+2}$,
$d(v_i,B)=2(i+1) + 2s+1$, $d(a,W)=k+ c_{k+2s+2}-p_{s+1}-p_{s+2}$, and
$d(a,B)=2s+3$.
As a result, we obtain
$$
d(L,R)= 2(k+1)(k^2 +k(2s+5)+2s+3).
$$

4. Consider distances between vertices of subgraph $L$.
By symmetry, it is sufficient to calculate distances
for vertex $v_i$, $i=1,2,\dots,k/2$.

4.1.  Distances form vertex $v_i$ to vertices of $V \cup A$.
The shortest paths from vertex $v_i$ to vertices of $V \cup A$
are located in subgraphs shown in Fig.~\ref{Fig3}a.
Denote by $C$ the cycle $(v_i,\dots, v_1,a,u_1,u'_1,a',v_k,\dots,v_{i+1},v_i)$
of length $k+4$. Then
$$
d(v_i,V\cup A) = c_{k+4} - d(v_i,u_1)- d(v_i,u') = c_{k+4} - (i+1)-(i+2)  = \frac{1}{4} k^2 + 2k - 2i + 1.
$$


\begin{figure}[t]
\center{\includegraphics[width=0.9\linewidth]{Figure_3.eps}}
\caption{Subgraphs with the shortest paths for $d(L,L)$.}
\label{Fig3}
\end{figure}


4.2.  Distances form vertex $v_i$ to vertices of $V'$.
The shortest paths from $v_i$ to vertices of $V'$
are located in subgraphs shown in
Fig.~\ref{Fig3}bc.
Denote by $C$ the cycle $(v_i',\dots, v'_1,a,u_1,u'_1,a',v'_k,\dots,v'_{i+1},v'_i)$.
Subpath $(v_i,v_{i-1},\dots,v_1,a)$ is a part of the shortest paths
form $v_i$ to vertices $v'_k,v'_{k-1},\dots,v'_j$, $i=1,2,\dots,k/2-2$.
It is convenient to find distances from $v_i$ to all vertices
of $C$ subtracting excess values:
\begin{align*}
d(v_i,V') & =  \sum_{x \in C} [d(v_i,v'_i) + d(v'_i,x))] - d(v'_i,a) - d(v'_i,u_1) - d(v'_i,u'_1) - d(v'_i,a')\\
          &   \phantom{=} \  - (k/2-1-i) \\[1mm]
          & =  (k+4) +c_{k+4} - (i+1)  - (i+2)  - (i+3)  - (i+4) - (k/2-1-i) \\[1mm]
          & =  \frac{1}{4} k^2 + \frac{5}{2} k  -3i - 1.
\end{align*}

For $i=k/2-1,k/2$, path $(v_i,v_{i-1},\dots,v_1,a)$
does not affect the shortest distances $v_i$ to vertices of $V'$
(see Fig.~\ref{Fig3}cd for $i=k/2-2$ and $i=k/2-1$).
Then $d(v_i,V') = k + p_{i} + p_{k+i-1} = k^2/2 - k(2i - 3)/2 + i^2 - i$
and, therefore, $d(v_{k/2-1})=k^2/4 + k + 2$ and $d(v_{k/2-1})=k^2/2 + k$.
Then
$$
d(v_i,L)= \left\{
\begin{array}{ll}
\frac{1}{4} k^2 + \frac{5}{2} k  - 1  - 3i, & i = 1,2,\dots ,k/2-2, \\[1.5mm]
k^2/4 + k + 2, & i=k/2-1, \\[1.5mm]
k^2/2 + k, & i=k/2.
\end{array}
\right.
$$

To calculate distances $d(a,L)$ and $d(a',L)$, it is sufficient to consider
the shortest paths in cycles
$(a,u_1,u'_1,a',v_k,v_{k-1}\dots,v_1,a)$ and
$(a,u_1,u'_1,a',v'_k,v'_{k-1}\dots,v'_1,a)$
(see Fig.~\ref{Fig1}).
Then we can write
$d(a,L)=d(a',L)= \sum_{x\in V\cup V'} d(a,x) + d(a,a') =
2c_{k+4}- 2d(a,u_1) - 2d(a,u'_1) - d(a,a')=2c_{k+4}-9=k^2/2 + 4k - 1$.
Finally, we have
$$
d(L,L) = 4 \left( \sum_{i=1}^{k/2-2} d(v_i,L) + \sum_{i=k/2-1}^{k/2} d(v_i,L) \right) + 2d(a,L)
=\frac{1}{2} (2k^3 + 15k^2 + 6k + 4).
$$

Substituting expressions for $d(L,L)$, $d(M,M)$, $d(L,R)$, and $d(L,M)$
back into equality~(\ref{WG}), we obtain
$$
W(G) =
3k^3 + k^2(6s + 39/2) + k(4s^2 + 20s + 19) + 2s^3/3 + 5s^2 + 34s/3 + 8.
$$

5. To quickly calculate Wiener index of graph $G-u_{s/2}$, we use the following
graph operation. Let $G_1$ and $G_2$ be graphs of order $n_1$ and $n_2$,
respectively. If vertices $v_1 \in V(G_1)$  and $v_2 \in V(G_2)$
are connected by  path $P_3$,
then the Wiener index of the resulting graph $H$
can be written as follows
\cite{Dobr01}
\begin{equation} \label{WGv}
W(H)=W(G_1)+W(G_2) + (n_1+1)d_{G_2}(v_2) + (n_2+1)d_{G_1}(v_1) + 2n_1 n_2 + n_1 + n_2.
\end{equation}

Let $G_1$ and $G_2$ be graphs
of order $n_1=2k+s$ and $n_2=n_1+2$
with vertex sets
$V \cup V' \cup A  \cup \{u_1,\dots,u_{s/2-1}\} \cup \{u'_1,\dots,u'_{s/2-1}\}$ and
$W \cup W' \cup B  \cup \{u_{s/2+1},\dots,u_s\} \cup \{u'_{s/2+1},\dots,u'_s\}$,
respectively.
Then we can represent Wiener indices of graphs $G_1$ and $G_2$
as $W(G_i)=(d(L,L)+d(M,M))/2+d(L,M)$,  where
ladder $M$ has order $2(s/2-1)$ in $G_1$ and $2s$ in $G_2$.
Path $P_3$ connects vertices $v_1 = u_{s/2-1}$ in $G_1$  and
$v_2 = u_{s/2+1}$ in $G_2$ .

Now calculate distance of vertex $u_{s/2-1}$ in  $G_1$.
Let $U^{*} = \{u_1,u_2,\dots,u_{s/2-1}$, $u'_1,u'_2,\dots,u'_{s/2-1}\}$.
It is easy to see that  $d(u_{s/2-1},U^{*})= p_{s/2-1} + p_{s/2}$.
The shortest paths from vertex $u_{s/2-1}$ to vertices of
$V\cup A$ pass on the subgraph of $G_1$ shown in
Fig.~\ref{Fig4}.


\begin{figure}[h]
\center{\includegraphics[width=0.75\linewidth]{Figure_4.eps}}
\caption{Subgraph with the shortest paths for $d(u_{s/2-1},V\cup A)$.}
\label{Fig4}
\end{figure}


Denote by $C$ the cycle $(u_1,a,v_1,v_2,\dots,v_k,a',u'_1,u_1)$ of length $k+4$.
Then
\begin{align*}
d_{G_1}(u_{s/2-1})& = d(u_{s/2-1},V \cup V' \cup A \cup U') \\
 & =  2\sum_{x \in V(C)} [d(u_{s/2-1},u_1) + d(u_1,x)] + d(u_{s/2-1},U')  \\
 &   \phantom{=} \  - 2d(u_{s/2-1},u_1) - 2d(u_{s/2-1},u'_1) -d(u_{s/2-1},a)- d(u_{s/2-1},a') \\[1mm]
 & =  2(k+4)(s/2-2) + 2c_{k+4} + p_{s/2-1} + p_{s/2} - 2(s/2-2) - 2(s/2-1) \\
 &   \phantom{=} \   -(s/2-1)- s/2 \\[1mm]
 & =  k^2/2 + ks + s^2/4.
\end{align*}
By similar consideration, we have
$d_{G_2}(u_{s/2+1})= k^2/2 + k(s + 2) + s^2/4 + s + 1$.
Substituting the obtained expressions back into equality (\ref{WGv}), we get
$$
W(G-u_{s/2})=
3k^3 + k^2(6s + 41/2) + k(4s^2 + 20s + 15) + 2s^3/3 + 5s^2 + 28s/3 + 4.
$$


\section{Other graphs of ${\mathcal G}_{k,s}$}

Computer calculations show that families of  cubic graphs $G$
with the property $W(G)=W(G-v)$ for some vertices $v$ exist also
for odd $k \ge 7$. Here we present two examples.

The left part of Table~\ref{ParamOdd} contains data
for a family of cubic graphs $G\in {\mathcal G}_{k,s}$ of order $2(2k+s+2)$
with odd $k \ge 7$ and  $s=(k+1)(k-5)/2$.
As for graphs with even $k$, vertex $u_{s/2}$ and three symmetrical vertices
can be removed from $G$ without changing the Wiener index.

Cubic graphs $G$ of the right part of Table~\ref{ParamOdd}
consist of ladders of distinct odd lengths. Namely, the left, right, and
central ladders have $k$, $k+6$, and $s=k+1$ rungs, respectively.
In this case, vertex $u_4$ and symmetrical vertex  $u'_4$ can be removed
from graphs $G$ of order $2(2k+s+8)$ without changing the Wiener index.


\begin{table}[h]
\centering
\caption{Graphs $G$ with property  $W(G)=W(G-v)$ for odd $k \ge 7$.} \label{ParamOdd}
%\vspace{0.6mm} % additional space after caption
\begin{tabular}{rrrr|rcrcr} \hline
%\rule{0cm}{2mm}  % additional space after line
$k$ & $s$  &  $|V(G)|$  &  $W(G)$    &  $k$ & $k+6$ & $s$ & $|V(G)|$ & $W(G)$   \\ \hline
7   &  8   &  48  \ \   &     8110   &   7  & 13    & 8   & \ 60     & 14764  \\
9   &  20  &  80  \ \   &    39166   &   9  & 15    & 10  & \ 72     & 25226  \\
11  &  36  &  120 \ \   &   135546   &  11  & 17    & 12  & \ 84     & 39724  \\
13  &  56  &  168 \ \   &   377810   &  13  & 19    & 14  & \ 96     & 58914  \\
15  &  80  &  224 \ \   &   904854   &  15  & 21    & 16  & 108      & 83452  \\
17  &  108 &  288 \ \   &  1936950   &  17  & 23    & 18  & 120      & 113994  \\
19  &  140 &  360 \ \   &  3802626   &  19  & 25    & 20  & 132      & 151196  \\
21  &  176 &  440 \ \   &  6969386   &  21  & 27    & 22  & 144      & 195714  \\
\hline
\end{tabular}
\end{table}

\section*{Acknowledgments}

The author is grateful to the referee for valuable comments.


\bigskip
\begin{thebibliography}{11}
\bibitem{Akhm2020}
M. Akhmejanova,  K. Olmezov, A. Volostnov, I. Vorobyev, K. Vorob’ev, Y. Yarovikov,
{\it Wiener index and graphs, almost half of whose vertices satisfy \v{S}olt\'{e}s property},
Discrete Appl. Math.,
\textbf{325} (2023), 37--42.
https://doi.org/10.1016/j.dam.2022.09.021

\bibitem{Bok19}
J.~Bok, N.~Jedli\v{c}kov\'{a}, J.~Maxov\'{a},
{\it On relaxed \v{S}olt\'{e}s's problem},
Acta Math. Univ. Comenianae,
\textbf{88}:3 (2019), 475--480.
http://www.iam.fmph.uniba.sk/amuc/ojs/ index.php/amuc/article/view/1173

\bibitem{Bok21}
J.~Bok, N.~Jedli\v{c}kov\'{a}, J.~Maxov\'{a},
{\it A relaxed version of \v{S}olt\'{e}s’s problem and cactus graphs},
Bull. Malays. Math. Sci. Soc., \textbf{44} (2021), 3733--3745.
https://doi.org/10.1007/s40840-021-01144-5

\bibitem{Dobr01}
A.A.~Dobrynin, R.~Entringer, I.~Gutman,
{\it Wiener index for trees: theory and applications},
Acta Appl. Math., \textbf{66}:3 (2001), 211--249.
https://doi.org/10.1023/A:1010767517079

\bibitem{Dobr02}
A.A.~Dobrynin, I.~Gutman, S.~Klav\v{z}ar, P.~\v{Z}igert,
{\it Wiener index of hexagonal systems},
Acta Appl. Math.,
\textbf{72}:3 (2002), 247--294.
https://doi.org/10.1023/A:1016290123303

\bibitem{Gutm86}
I.~Gutman, O.E.~Polansky,
{\it Mathematical Concepts in Organic Chemistry},
Springer--Verlag, Berlin, 1986.
https://doi.org/10.1007/978-3-642-70982-1

\bibitem{Hu21}
Y.~Hu, Z.~Zhu, P.~Wu, Z.~Shao, A.~Fahad,
{\it On investigations of graphs preserving the Wiener index upon vertex removal},
AIMS Mathematics,
\textbf{6}:12 (2021), 12976--12985.
https://doi.org/10.3934/math.2021750

\bibitem{Knor18-1}
M.~Knor, S.~Majstorovi\'{c}, R.~\v{S}krekovski,
{\it Graphs whose Wiener index does not change when a specific vertex is removed},
Discrete Appl. Math.,
\textbf{238} (2018), 126--132.
https://doi.org/10.1016/j.dam.2017.12.012

\bibitem{Knor18-2}
M.~Knor, S.~Majstorovi\'{c}, R.~\v{S}krekovski,
{\it Graphs preserving Wiener index upon vertex removal},
Appl. Math. Comput., \textbf{338} (2018), 25--32.
https://doi.org/10.1016/j.amc.2018.05.047

\bibitem{Knor16}
M.~Knor, R.~\v{S}krekovski, A.~Tepeh,
{\it Mathematical aspects of Wiener index},
Ars Math. Contemp.,
\textbf{11}:2 (2016), 327--352.
https://doi.org/10.26493/1855-3974.795.ebf

\bibitem{Majs18}
S.~Majstorovi\'{c}, M.~Knor, R.~\v{S}krekovski,
{\it Graphs preserving total distance upon vertex removal},
Electron. Notes Discrete Math.,
\textbf{68} (2018), 107--112.
https://doi.org/10.1016/j.endm.2018.06.019

\bibitem{Solt91}
L.~\v{S}olt\'{e}s,
{\it Transmission in graphs: a bound and vertex removing},
Math. Slovaca,
\textbf{41}:1 (1991), 11--16.
https://eudml.org/doc/32286

\bibitem{Spir22}
S.~Spiro,
{\it The Wiener index of signed graphs},
Appl. Math. Comput.,
\textbf{416} (2022), 126755.
https://doi.org/10.1016/j.amc.2021.126755

\bibitem{Trin83}
N.~Trinajsti\'{c},
{\it Chemical Graph Theory},
CRC Press, Boca Raton, 1992.
https://doi.org/10.1201/9781315139111

\bibitem{Wien47}
H.~Wiener,
{\it Structural determination of paraffin boiling points},
J. Amer. Chem. Soc.,
\textbf{69} (1947), 17--20.
https://doi.org/10.1021/ja01193a005
\end{thebibliography}
\end{document}


