betaFeedback

WorksMathematics

An infinite family of graphs with Šoltés fraction uniformly above one half

Abstract

The Wiener index W(G)W(G) of a connected graph GG is the sum of the distances between all unordered pairs of vertices. A vertex xx is a Šoltés vertex if G−xG-x is connected and W(G−x)=W(G)W(G-x)=W(G). We construct an infinite family of graphs in which the proportion of Šoltés vertices is strictly greater than (21−3)/3=0.5275…>1/2(\sqrt{21}-3)/3=0.5275\ldots>1/2 and decreases to this value from 2/32/3. The family is also described by a generalized Pell equation and starts from a 1212-vertex example of Akhmejanova et al. (Discrete Appl. Math. 325 (2023) 37-42). We also show that the construction remains valid after adding edges among certain vertices.

Introduction

In this paper we are concerned with finite simple undirected connected graphs. The vertex set of GG is denoted by V(G)V(G). The cardinality of the set V(G)V(G) is called the order of the graph GG. If uu and vv are vertices of GG, then the number of edges in a shortest path connecting them is said to be their distance and is denoted by d(u,v)d(u,v). The transmission of a vertex vv in a graph GG is the sum of distances between vv and all other vertices of GG, TG(v)=∑u∈V(G)dG(v,u)T_G(v)=\sum_{u\in V(G)}d_G(v,u). The Wiener index of GG is a distance-based graph invariant defined as the sum of distances between all unordered pairs of vertices of GG,

W(G)=∑{u,v}⊆V(G)dG(u,v)=12∑v∈V(G)TG(v).W(G)=\sum_{\{u,v\}\subseteq V(G)}d_G(u,v)=\frac{1}{2}\sum_{v\in V(G)}T_G(v).

It was originally introduced as a structural descriptor for alkanes, whose carbon skeletons are trees with vertex degrees at most four [21]. Mathematical properties and chemical applications of the Wiener index have been intensively studied over the past decades [6, 9, 10, 12, 16, 17, 19, 20].

One of the research directions concerning the index involves describing its properties under graph operations. A vertex v∈V(G)v\in V(G) is called a Šoltés vertex if G−vG-v is connected and W(G−v)=W(G)W(G-v)=W(G). In 1991, Šoltés [18] posed the problem of finding all graphs in which every vertex is a Šoltés vertex. The cycle C11C_{11} is the only known example, and the problem remains open.

Since the full problem seems out of reach, various relaxations have been studied. Subsequent work has investigated preservation upon the removal of particular vertices, including constructions in the classes of unicyclic, cactus, cubic, and regular graphs [3, 4, 5, 8, 14, 15]. The problem of finding graphs with arbitrarily many Šoltés vertices was posed in [14]. For every k≥1k\geq1, infinitely many graphs with at least kk Šoltés vertices were constructed in [4, 5, 13]. Such families of cubic 2-connected graphs were constructed in [3]. Preservation of the Wiener index under the simultaneous deletion of k≥2k\geq2 vertices was studied in [13], following a problem posed in [14].

Other relaxations concern graphs in which at least a fixed proportion of the vertices are Šoltés vertices [3]. We measure this proportion by the Šoltés fraction R0(G)=NS/∣V(G)∣R_0(G)=N_S/|V(G)|, where NSN_S is the number of Šoltés vertices. Two values of R0R_0 are of particular interest. The first is 1/21/2. It is difficult to find graphs whose Šoltés fraction is close to or greater than this value. The constructions in [11] produce three graphs with R0∈{4/7,5/9,6/11}R_0\in\{4/7,5/9,6/11\}. A graph of order 12 with Šoltés fraction exactly 1/21/2 is shown in [7]. It can be verified computationally that some generalized Petersen graphs GP(n,k)GP(n,k) have Šoltés fraction exactly 1/21/2. Infinite families of graphs whose Šoltés fraction tends to 1/21/2 from below were constructed in [1, 11]. The second value is 2/32/3. Only a few graphs with this Šoltés fraction are known. A graph of order 12 with Šoltés fraction 2/32/3 appears in [1]. Eight graphs with Šoltés fraction 2/32/3, including this one, are described by Cambie [7]. To the best of our knowledge, no infinite family of graphs with Šoltés fraction above 1/21/2 has previously been presented.

In this note we construct an explicit infinite family of graphs whose Šoltés fractions have a common lower bound strictly greater than 1/21/2. The first member is the graph of order 12 with Šoltés fraction 2/32/3 from [1]. Further infinite families are obtained by adding edges between certain vertices without changing the set of Šoltés vertices.

Main result

For integers d≥2d \ge2 and r≥1r \ge1, consider the graph G(d,r)G(d,r) shown in Figure 1. Its vertex set consists of base vertices aija_{ij}, bijb_{ij} and auxiliary vertices uitu_{it}, vjtv_{jt}, where 1≤i,j≤d1 \le i,j \le d and 1≤t≤r1 \le t \le r. For each ii, the vertices ai1,…,aida_{i1},\ldots,a_{id} induce a clique AiA_i of order dd. For each jj, the vertices b1j,…,bdjb_{1j},\ldots,b_{dj} induce a clique BjB_j of order dd. The cliques AiA_i and BjB_j are called base cliques. These 2d2d cliques are pairwise disjoint and are joined by the edges aijbija_{ij}b_{ij}. Each auxiliary vertex uitu_{it} is adjacent to all vertices of AiA_i, and each vjtv_{jt} to all vertices of BjB_j.

The graph G(d,r)

Figure 1. The graph G(d,r)G(d,r).

Thus G(d,r)G(d,r) has 2d22d^2 base vertices of degree d+rd+r, and 2dr2dr auxiliary vertices of degree dd. The order of G(d,r)G(d,r) is 2d(d+r)2d(d+r). Deleting the auxiliary vertices and contracting each of the cliques AiA_i, BjB_j to a single vertex gives the complete bipartite graph Kd,dK_{d,d}. The base vertices and the auxiliary vertices form the two orbits of the automorphism group of G(d,r)G(d,r). Indeed, this group contains the maps that permute the first indices ii (together with the corresponding uitu_{it}), those that permute the second indices jj (together with the corresponding vjtv_{jt}), those that permute the index tt, and the involution aij↔bjia_{ij} \leftrightarrow b_{ji}, uit↔vitu_{it} \leftrightarrow v_{it}.

Using G(d,r)G(d,r), we construct an infinite family of graphs in which more than half of the vertices are Šoltés vertices.

Theorem 1. Let Gn=G(dn,rn)G_n=G(d_n,r_n), where dn=2snd_n=2s_n, s0=r0=1s_0=r_0=1, and

sn+1=14sn+5rn−4,rn+1=25sn+9rn−8(n≥0).s_{n+1}=14s_n+5r_n-4,\qquad r_{n+1}=25s_n+9r_n-8 \qquad(n\ge0).

Then GnG_n of order 2dn(dn+rn)2d_n(d_n+r_n) has exactly 2dn22d_n^2 Šoltés vertices,

R0(Gn)=dndn+rn>21−33=0.527525…>12,R_0(G_n)=\frac{d_n}{d_n+r_n}>\frac{\sqrt{21}-3}{3}=0.527525\ldots>\frac{1}{2},

and R0(Gn)R_0(G_n) decreases strictly from 2/32/3 to (21−3)/3(\sqrt{21}-3)/3.

The construction of GnG_n allows us to obtain new families of graphs with a similar structure satisfying Theorem 1.

Corollary 1. Let Gn′G'_n be obtained from GnG_n by adding arbitrary edges within each set of rnr_n auxiliary vertices attached to the same base clique. Then Gn′G'_n has the same order and the same Šoltés vertices as GnG_n, so Theorem 1 holds for Gn′G'_n.

Changes in distances after vertex removal

Let G=G(d,r)G=G(d,r) and ΔG(x)=W(G)−W(G−x)\Delta_G(x)=W(G)-W(G-x) for x∈V(G)x\in V(G).

Lemma 1. If xx is a base vertex of GG, then

ΔG(x)=5d2−8d+4−2dr−4r2.(1)\Delta_G(x)=5d^2-8d+4-2dr-4r^2. \tag*{(1)}

Proof. The base vertices form a single orbit, so we may take x=a11x=a_{11}. A shortest path between base vertices contains no auxiliary vertex, since the neighbours of every auxiliary vertex form a clique.

The vertex xx has dd base neighbours: b11b_{11} and a1ja_{1j} for 2≤j≤d2\le j\le d. At distance 2 from xx there are 2(d−1)2(d-1) base vertices: b1jb_{1j} for 2≤j≤d2\le j\le d and bi1b_{i1} for 2≤i≤d2\le i\le d. At distance 3 from xx there are d(d−1)d(d-1) base vertices, forming two sets:

  • the d−1d-1 vertices ai1a_{i1}, 2≤i≤d2\le i\le d, reached by the path (a11,b11,bi1,ai1)(a_{11},b_{11},b_{i1},a_{i1});

  • the (d−1)2(d-1)^2 vertices bijb_{ij}, 2≤i,j≤d2\le i,j\le d, reached by the path (a11,a1j,b1j,bij)(a_{11},a_{1j},b_{1j},b_{ij}).

Neither set meets the first two distance layers, so these paths are shortest. At distance 4 from xx there are (d−1)2(d-1)^2 base vertices aija_{ij}, 2≤i,j≤d2\le i,j\le d, reached by the path (a11,a1j,b1j,bij,aij)(a_{11},a_{1j},b_{1j},b_{ij},a_{ij}). This path is shortest because aija_{ij} has no base neighbour at distance less than 3 from xx.

For each t∈{1,…,r}t\in\{1,\ldots,r\}, the auxiliary vertices u1tu_{1t}, v1tv_{1t}, vjtv_{jt} (2≤j≤d)(2\le j\le d) and uitu_{it} (2≤i≤d)(2\le i\le d) lie at distances 1, 2, 3, 4 from xx, respectively. Hence

TG(x)=7d2−6d+(7d−4)r.(2)T_G(x)=7d^2-6d+(7d-4)r. \tag*{(2)}

Table 1 lists all unordered pairs of vertices of G−xG-x whose distance increases when x=a11x=a_{11} is deleted. Each path is written as a sequence of vertices; i,j∈{2,…,d}i,j\in\{2,\ldots,d\} and s,t∈{1,…,r}s,t\in\{1,\ldots,r\} vary independently. The index 2 appearing in some paths is admissible because d≥2d\ge2.

PairBeforePath in GGAfterPath in G−xG-xPairs
a1j,bi1a_{1j},b_{i1}3(a1j,a11,b11,bi1)(a_{1j},a_{11},b_{11},b_{i1})5(a1j,b1j,bij,aij,ai1,bi1)(a_{1j},b_{1j},b_{ij},a_{ij},a_{i1},b_{i1})(d−1)2(d-1)^2
a1j,b11a_{1j},b_{11}2(a1j,a11,b11)(a_{1j},a_{11},b_{11})6(a1j,b1j,b2j,a2j,a21,b21,b11)(a_{1j},b_{1j},b_{2j},a_{2j},a_{21},b_{21},b_{11})d−1d-1
b11,b1jb_{11},b_{1j}3(b11,a11,a1j,b1j)(b_{11},a_{11},a_{1j},b_{1j})5(b11,b21,a21,a2j,b2j,b1j)(b_{11},b_{21},a_{21},a_{2j},b_{2j},b_{1j})d−1d-1
ai1,u1ta_{i1},u_{1t}4(ai1,bi1,b11,a11,u1t)(a_{i1},b_{i1},b_{11},a_{11},u_{1t})5(ai1,ai2,bi2,b12,a12,u1t)(a_{i1},a_{i2},b_{i2},b_{12},a_{12},u_{1t})(d−1)r(d-1)r
a1j,v1ta_{1j},v_{1t}3(a1j,a11,b11,v1t)(a_{1j},a_{11},b_{11},v_{1t})6(a1j,b1j,b2j,a2j,a21,b21,v1t)(a_{1j},b_{1j},b_{2j},a_{2j},a_{21},b_{21},v_{1t})(d−1)r(d-1)r
bi1,u1tb_{i1},u_{1t}3(bi1,b11,a11,u1t)(b_{i1},b_{11},a_{11},u_{1t})6(bi1,ai1,ai2,bi2,b12,a12,u1t)(b_{i1},a_{i1},a_{i2},b_{i2},b_{12},a_{12},u_{1t})(d−1)r(d-1)r
b1j,v1tb_{1j},v_{1t}4(b1j,a1j,a11,b11,v1t)(b_{1j},a_{1j},a_{11},b_{11},v_{1t})5(b1j,b2j,a2j,a21,b21,v1t)(b_{1j},b_{2j},a_{2j},a_{21},b_{21},v_{1t})(d−1)r(d-1)r
b11,u1tb_{11},u_{1t}2(b11,a11,u1t)(b_{11},a_{11},u_{1t})7(b11,b21,a21,a22,b22,b12,a12,u1t)(b_{11},b_{21},a_{21},a_{22},b_{22},b_{12},a_{12},u_{1t})rr
b11,vjtb_{11},v_{jt}4(b11,a11,a1j,b1j,vjt)(b_{11},a_{11},a_{1j},b_{1j},v_{jt})5(b11,b21,a21,a2j,b2j,vjt)(b_{11},b_{21},a_{21},a_{2j},b_{2j},v_{jt})(d−1)r(d-1)r
u1t,v1su_{1t},v_{1s}3(u1t,a11,b11,v1s)(u_{1t},a_{11},b_{11},v_{1s})7(u1t,a12,b12,b22,a22,a21,b21,v1s)(u_{1t},a_{12},b_{12},b_{22},a_{22},a_{21},b_{21},v_{1s})r2r^2

Table 1. Distances and shortest paths before and after deleting a11a_{11}.

To see that the listed paths are shortest and that the list is exhaustive, consider the subgraph induced by the base vertices and contract each base clique to a single vertex. Deleting a11a_{11} removes the edge a11b11a_{11}b_{11} joining the cliques A1A_1 and B1B_1 (see Figure 1). In Kd,dK_{d,d}, deleting this edge changes only the distance between its endpoints, from 1 to 3. In the subgraph induced by the base vertices, consecutive edges joining distinct cliques are separated by an edge inside a clique. In G−a11G-a_{11}, every base neighbour of b11b_{11} lies in the clique B1B_1 containing b11b_{11}. Together, these facts justify the first three rows of Table 1.

For a base vertex yy and an auxiliary vertex zz of H∈{G,G−x}H \in\{G,G-x\},

dH(y,z)=1+min⁡a∈NH(z)dH(y,a).d_H(y,z)=1+\min_{a\in N_H(z)}d_H(y,a).

where NH(z)N_H(z) denotes the set of neighbours of zz in HH. The distances in the next six rows follow from this formula. For two distinct auxiliary vertices zz and z′z',

dH(z,z′)=2+min⁡a∈NH(z)b∈NH(z′)dH(a,b).d_H(z,z')=2+\min_{\substack{a\in N_H(z)\\b\in N_H(z')}}d_H(a,b).

The last row follows from this identity. Distances within a base clique and between auxiliary vertices attached to the same base clique do not change. The total increase of distances among the remaining pairs is therefore

D(x)=∑{y,z}⊆V(G)∖{x}(dG−x(y,z)−dG(y,z))=2(d−1)(d+2)+(9d−4)r+4r2.D(x)=\sum_{\{y,z\}\subseteq V(G)\setminus\{x\}}\left(d_{G-x}(y,z)-d_G(y,z)\right)=2(d-1)(d+2)+(9d-4)r+4r^2.

Since ΔG(x)=TG(x)−D(x)\Delta_G(x)=T_G(x)-D(x), equation (2) yields (1).

If xx is an auxiliary vertex, its neighbours form a clique, so deleting xx does not change any distance between the remaining vertices. Hence ΔG(x)=TG(x)>0\Delta_G(x)=T_G(x)>0. For an auxiliary vertex zz,

TG(z)=7d2−4d+(8d−3)r−2.T_G(z)=7d^2-4d+(8d-3)r-2.

Since the Wiener index is half the sum of the vertex transmissions, we obtain

W(G(d,r))=7d4−6d3+(14d3−8d2−2d)r+d(8d−3)r2.W(G(d,r))=7d^4-6d^3+(14d^3-8d^2-2d)r+d(8d-3)r^2.

Proof of Theorem 1

Let d=2sd=2s. By equation (1), ΔG(x)=4F(s,r)\Delta_G(x)=4F(s,r) for a base vertex xx, where

F(s,r)=5s2−4s+1−sr−r2.F(s,r)=5s^2-4s+1-sr-r^2.

Direct expansion gives the polynomial identity

F(14s+5r−4,25s+9r−8)=F(s,r).(3)F(14s+5r-4,25s+9r-8)=F(s,r). \tag*{(3)}

Since F(s0,r0)=F(1,1)=0F(s_0,r_0)=F(1,1)=0, identity (3) and induction give F(sn,rn)=0F(s_n,r_n)=0 for all n≥0n\ge0. The recurrences yield sn+1>sn≥1s_{n+1}>s_n\ge1 and rn+1>rn≥1r_{n+1}>r_n\ge1, so the orders of the graphs GnG_n strictly increase. By Lemma 1, every base vertex xx of GnG_n satisfies ΔGn(x)=4F(sn,rn)=0\Delta_{G_n}(x)=4F(s_n,r_n)=0, whereas ΔGn(z)>0\Delta_{G_n}(z)>0 for every auxiliary vertex zz. Consequently, the Šoltés vertices of GnG_n are precisely its 2dn22d_n^2 base vertices.

The equation F(s,r)=0F(s,r)=0, regarded as a quadratic equation in rr, has the positive root

r=−s+21s2−16s+42.r=\frac{-s+\sqrt{21s^{2}-16s+4}}{2}.

Therefore

R0(Gn)=2dn22dn(dn+rn)=2sn2sn+rn=43+21−16/sn+4/sn2(4)R_{0}(G_n)=\frac{2d_n^2}{2d_n(d_n+r_n)}=\frac{2s_n}{2s_n+r_n}=\frac{4}{3+\sqrt{21-16/s_n+4/s_n^2}} \tag*{(4)}

For s≥1s\ge1, the expression 21−16/s+4/s221-16/s+4/s^2 is strictly increasing in ss and less than 21. Since sn→∞s_n\to\infty, the fractions in (4) decrease strictly to

43+21=21−33=0.527525…>12.\frac{4}{3+\sqrt{21}}=\frac{\sqrt{21}-3}{3}=0.527525\ldots>\frac{1}{2}.

This completes the proof of Theorem 1.

The first graph G0=G(2,1)G_0=G(2,1) in the family is shown in Figure 2. It has order 12 and R0(G(2,1))=2/3R_0(G(2,1))=2/3. This graph was first introduced by Akhmejanova et al. [1].

The graph $G_0=G(2,1)$

Figure 2. The graph G0=G(2,1)G_0=G(2,1).

Remark (A Pell-type interpretation). By Lemma 1, deleting a base vertex of G(2s,r)G(2s,r) preserves the Wiener index if and only if F(s,r)=0F(s,r)=0. Thus, to construct infinitely many such graphs, it suffices to find infinitely many positive integer solutions (s,r)(s,r) of this equation. An alternative way to obtain these solutions is to use a generalized Pell equation (see [2] for background). The substitution x=42s−16x=42s-16, y=2s+4ry=2s+4r transforms F(s,r)=0F(s,r)=0 into

x2−21y2=−80.x^2-21y^2=-80.

The initial pair (s0,r0)=(1,1)(s_0,r_0)=(1,1) corresponds to the solution (x0,y0)=(26,6)(x_0,y_0)=(26,6). Starting with this solution, we multiply xn+yn21x_n+y_n\sqrt{21} by (23+521)/2(23+5\sqrt{21})/2 and define the next pair by

xn+1+yn+121=23+5212(xn+yn21).(5)x_{n+1}+y_{n+1}\sqrt{21}=\frac{23+5\sqrt{21}}{2}(x_n+y_n\sqrt{21}). \tag*{(5)}

The new pair satisfies the same Pell equation. Indeed, multiplying (5) by its conjugate, we obtain

xn+12−21yn+12=232−21⋅524(xn2−21yn2)=xn2−21yn2=−80.x_{n+1}^2-21y_{n+1}^2=\frac{23^2-21\cdot5^2}{4}(x_n^2-21y_n^2)=x_n^2-21y_n^2=-80.

Comparing the coefficients of 1 and 21\sqrt{21} in (5), we obtain

xn+1=23xn+105yn2,yn+1=5xn+23yn2.(6)x_{n+1}=\frac{23x_n+105y_n}{2},\qquad y_{n+1}=\frac{5x_n+23y_n}{2}. \tag*{(6)}

Returning to the original parameters, we obtain

sn+1=xn+1+1642=14sn+5rn−4,s_{n+1}=\frac{x_{n+1}+16}{42}=14s_n+5r_n-4,
rn+1=yn+1−2sn+14=25sn+9rn−8.r_{n+1}=\frac{y_{n+1}-2s_{n+1}}{4}=25s_n+9r_n-8.

These are the recurrences in Theorem 1. They ensure that sns_n and rnr_n are positive integers and that sn+1>sns_{n+1}>s_n. Hence they generate infinitely many distinct graphs Gn=G(2sn,rn)G_n=G(2s_n,r_n).

Table 2 contains parameters of the smallest graphs Gn=G(dn,rn)G_n=G(d_n,r_n).

nndnd_nrnr_nOrderŠoltés verticesR0R_0
0211282/32/3
130263360180015/28≈0.53571415/28\approx0.535714
26726011710912903168672/1273≈0.527887672/1273\approx0.527887
3154101380190028302047493620015410/29211≈0.52754115410/29211\approx0.527541
4353742316826474416130912250266805128176871/335284≈0.527526176871/335284\approx0.527526
5812064072732012500156819564801318895880192008120640/15393841≈0.5275258120640/15393841\approx0.527525

Table 2. Initial members of the infinite sequence.

Proof of Corollary 1

We first establish the following lemma.

Lemma 2. Let GG be a connected graph, and let ZZ be an independent set of vertices that all have the same neighbourhood XX, where ∣X∣≥2|X|\ge2. Let HH be obtained from GG by adding arbitrary edges between vertices of ZZ. Then, for every x∈V(G)∖Zx\in V(G)\setminus Z such that G−xG-x is connected,

W(H)−W(H−x)=W(G)−W(G−x).W(H)-W(H-x)=W(G)-W(G-x).

Proof. Let E+=E(H)∖E(G)E^+=E(H)\setminus E(G) and m=∣E+∣m=|E^+|. Obviously, a shortest path in HH with at least one endpoint outside ZZ contains no added edge. Since any two distinct vertices of ZZ are at distance 2 in GG, for distinct u,v∈V(G)u,v\in V(G) we have dG(u,v)−dH(u,v)=1d_G(u,v)-d_H(u,v)=1 if uv∈E+uv\in E^+, and 0 otherwise. Hence W(H)=W(G)−mW(H)=W(G)-m. Since x∉Zx\notin Z, all mm added edges remain in H−xH-x. Since ∣X∣≥2|X|\ge2, the vertices of ZZ always have a common neighbour in G−xG-x, and the same argument yields W(H−x)=W(G−x)−mW(H-x)=W(G-x)-m. Subtracting the two equalities proves the lemma. □

Proof of Corollary 1. Apply Lemma 2 successively to the 2dn2d_n sets of rnr_n auxiliary vertices attached to the same base clique. For each of them, XX is that clique and ∣X∣=dn≥2|X|=d_n\ge2. For every base vertex xx this implies

ΔGn′(x)=ΔGn(x)=0.\Delta_{G'_n}(x)=\Delta_{G_n}(x)=0.

If zz is an auxiliary vertex, deleting zz does not change distances between the remaining vertices. Hence ΔGn′(z)>0\Delta_{G'_n}(z)>0. Consequently, Gn′G'_n has the same Šoltés vertices as GnG_n. □

As a particular case, add all edges within each set of rr auxiliary vertices, and denote the resulting graph by Gc(d,r)G^c(d,r). It has the same Šoltés vertices as G(d,r)G(d,r), and

W(Gc(d,r))=W(G(d,r))−dr(r−1).W(G^c(d,r))=W(G(d,r))-dr(r-1).

Each base clique, together with its auxiliary vertices, now induces Kd+rK_{d+r}. In Gc(d,r)G^c(d,r), base vertices have degree d+rd+r, and auxiliary vertices have degree d+r−1d+r-1.

Auxiliary verticesBase vertex degreeAuxiliary vertex degreeWWŠoltés vertices
Independent5630199536001800
Cliques5655199341001800

Table 3. Two versions of the graph of order 3360.

Conclusion

We have constructed an infinite family of graphs in which the proportion of Šoltés vertices is strictly greater than (21−3)/3=0.5275…>1/2(\sqrt{21}-3)/3 = 0.5275\ldots> 1/2 and decreases to this value from 2/32/3. Adding arbitrary edges within each set of auxiliary vertices attached to the same base clique preserves the set of Šoltés vertices. The distance formulas for G(d,r)G(d,r) were verified computationally for several small values of dd and rr.

Acknowledgements

This work was supported by the state contract of the Sobolev Institute of Mathematics (project number FWNF-2022-0017).

Declaration of generative AI use

ChatGPT (OpenAI) was used to assist with mathematical discussions and computational checks. The author reviewed and revised the material and takes full responsibility for the final content.

Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk, 630090, Russia

Email address: [email protected]

References

  1. [1]M. Akhmejanova, K. Olmezcov, A. Volostnov, I. Vorobyev, K. Vorob’ev, Y. Yarovikov, Wiener index and graphs, almost half of whose vertices satisfy Šoltés property, Discrete Appl. Math. 325 (2023) 37–42.DOI
  2. [2]E. J. Barbeau, Pell’s Equation, Problem Books in Mathematics, Springer, New York, 2003.
  3. [3]N. Bašić, M. Knor, R. Škrekovski, On regular graphs with Šoltés vertices, Ars Math. Contemp. 25:2 (2025) P2.01.arxiv.org/abs/2303.11996
  4. [4]J. Bok, N. Jedličková, J. Maxová, On relaxed Šoltés’s problem, Acta Math. Univ. Comenian. 88:3 (2019) 475–480.
  5. [5]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.DOI
  6. [6]D. Bonchev, D. H. Rouvray (eds.), Chemical Graph Theory: Introduction and Fundamentals, Gordon and Breach, New York, 1991.
  7. [7]S. Cambie, Towards the essence of Šoltés’ problem, Appl. Math. Comput. 508 (2026) 129621.arxiv.org/abs/2406.03451
  8. [8]A. A. Dobrynin, On the preservation of the Wiener index of cubic graphs upon vertex removal, Siberian Electron. Math. Rep. 20:1 (2023) 285–292.
  9. [9]A. A. Dobrynin, R. C. Entringer, I. Gutman, Wiener index of trees: theory and applications, Acta Appl. Math. 66:3 (2001) 211–249.DOI
  10. [10]A. A. Dobrynin, I. Gutman, S. Klavžar, P. Žigert, Wiener index of hexagonal systems, Acta Appl. Math. 72:3 (2002) 247–294.DOI
  11. [11]A. A. Dobrynin, K. V. Vorob’ev, Some results on the Wiener index related to the Šoltés problem of graphs, Discrete Appl. Math. 344 (2024) 154–160.arxiv.org/abs/2311.15144
  12. [12]I. Gutman, O.E. Polansky, Mathematical Concepts in Organic Chemistry. Springer–Verlag, Berlin, 1986.
  13. [13]Y. Hu, Z. Zhu, P. Wu, Z. Shao, A. Fahad, On investigations of graphs preserving the Wiener index upon vertex removal, AIMS Math. 6:12 (2021) 12976–12985.DOI
  14. [14]M. Knor, S. Majstorović, R. Škrekovski, Graphs preserving Wiener index upon vertex removal, Appl. Math. Comput. 338 (2018) 25–32.DOI
  15. [15]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.DOI
  16. [16]M. Knor, R. Škrekovski, A. Tepeh, Mathematical aspects of Wiener index, Ars Math. Contemp. 11:2 (2016) 327–352.arxiv.org/abs/1510.00800
  17. [17]M. Knor, R. Škrekovski, A. Tepeh, Selected topics on Wiener index, Ars Math. Contemp. 24:4 (2024) P4.07.arxiv.org/abs/2303.11405
  18. [18]L. Šoltés, Transmission in graphs: A bound and vertex removing, Math. Slovaca 41:1 (1991) 11–16.
  19. [19]N. Trinajstić, Chemical Graph Theory, CRC Press, Boca Raton, 1992.
  20. [20]S. Wagner, H. Wang, Introduction to Chemical Graph Theory, Chapman and Hall/CRC, 2018.DOI
  21. [21]H. Wiener, Structural determination of paraffin boiling points, J. Amer. Chem. Soc. 69 (1947) 17–20.pubmed.ncbi.nlm.nih.gov/20291038

Paper details

vlnc:W_882derwy
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

ChatGPT

View statement
Looking for related papers…
Contents