WorksMathematics
An infinite family of graphs with Šoltés fraction uniformly above one half
Abstract
The Wiener index of a connected graph is the sum of the distances between all unordered pairs of vertices. A vertex is a Šoltés vertex if is connected and . We construct an infinite family of graphs in which the proportion of Šoltés vertices is strictly greater than and decreases to this value from . The family is also described by a generalized Pell equation and starts from a -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 is denoted by . The cardinality of the set is called the order of the graph . If and are vertices of , then the number of edges in a shortest path connecting them is said to be their distance and is denoted by . The transmission of a vertex in a graph is the sum of distances between and all other vertices of , . The Wiener index of is a distance-based graph invariant defined as the sum of distances between all unordered pairs of vertices of ,
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 is called a Šoltés vertex if is connected and . In 1991, Šoltés [18] posed the problem of finding all graphs in which every vertex is a Šoltés vertex. The cycle 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 , infinitely many graphs with at least Š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 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 , where is the number of Šoltés vertices. Two values of are of particular interest. The first is . 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 . A graph of order 12 with Šoltés fraction exactly is shown in [7]. It can be verified computationally that some generalized Petersen graphs have Šoltés fraction exactly . Infinite families of graphs whose Šoltés fraction tends to from below were constructed in [1, 11]. The second value is . Only a few graphs with this Šoltés fraction are known. A graph of order 12 with Šoltés fraction appears in [1]. Eight graphs with Šoltés fraction , including this one, are described by Cambie [7]. To the best of our knowledge, no infinite family of graphs with Šoltés fraction above 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 . The first member is the graph of order 12 with Šoltés fraction 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 and , consider the graph shown in Figure 1. Its vertex set consists of base vertices , and auxiliary vertices , , where and . For each , the vertices induce a clique of order . For each , the vertices induce a clique of order . The cliques and are called base cliques. These cliques are pairwise disjoint and are joined by the edges . Each auxiliary vertex is adjacent to all vertices of , and each to all vertices of .

Figure 1. The graph .
Thus has base vertices of degree , and auxiliary vertices of degree . The order of is . Deleting the auxiliary vertices and contracting each of the cliques , to a single vertex gives the complete bipartite graph . The base vertices and the auxiliary vertices form the two orbits of the automorphism group of . Indeed, this group contains the maps that permute the first indices (together with the corresponding ), those that permute the second indices (together with the corresponding ), those that permute the index , and the involution , .
Using , we construct an infinite family of graphs in which more than half of the vertices are Šoltés vertices.
Theorem 1. Let , where , , and
Then of order has exactly Šoltés vertices,
and decreases strictly from to .
The construction of allows us to obtain new families of graphs with a similar structure satisfying Theorem 1.
Corollary 1. Let be obtained from by adding arbitrary edges within each set of auxiliary vertices attached to the same base clique. Then has the same order and the same Šoltés vertices as , so Theorem 1 holds for .
Changes in distances after vertex removal
Let and for .
Lemma 1. If is a base vertex of , then
Proof. The base vertices form a single orbit, so we may take . A shortest path between base vertices contains no auxiliary vertex, since the neighbours of every auxiliary vertex form a clique.
The vertex has base neighbours: and for . At distance 2 from there are base vertices: for and for . At distance 3 from there are base vertices, forming two sets:
the vertices , , reached by the path ;
the vertices , , reached by the path .
Neither set meets the first two distance layers, so these paths are shortest. At distance 4 from there are base vertices , , reached by the path . This path is shortest because has no base neighbour at distance less than 3 from .
For each , the auxiliary vertices , , and lie at distances 1, 2, 3, 4 from , respectively. Hence
Table 1 lists all unordered pairs of vertices of whose distance increases when is deleted. Each path is written as a sequence of vertices; and vary independently. The index 2 appearing in some paths is admissible because .
| Pair | Before | Path in | After | Path in | Pairs |
| 3 | 5 | ||||
| 2 | 6 | ||||
| 3 | 5 | ||||
| 4 | 5 | ||||
| 3 | 6 | ||||
| 3 | 6 | ||||
| 4 | 5 | ||||
| 2 | 7 | ||||
| 4 | 5 | ||||
| 3 | 7 |
Table 1. Distances and shortest paths before and after deleting .
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 removes the edge joining the cliques and (see Figure 1). In , 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 , every base neighbour of lies in the clique containing . Together, these facts justify the first three rows of Table 1.
For a base vertex and an auxiliary vertex of ,
where denotes the set of neighbours of in . The distances in the next six rows follow from this formula. For two distinct auxiliary vertices and ,
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
Since , equation (2) yields (1).
If is an auxiliary vertex, its neighbours form a clique, so deleting does not change any distance between the remaining vertices. Hence . For an auxiliary vertex ,
Since the Wiener index is half the sum of the vertex transmissions, we obtain
Proof of Theorem 1
Let . By equation (1), for a base vertex , where
Direct expansion gives the polynomial identity
Since , identity (3) and induction give for all . The recurrences yield and , so the orders of the graphs strictly increase. By Lemma 1, every base vertex of satisfies , whereas for every auxiliary vertex . Consequently, the Šoltés vertices of are precisely its base vertices.
The equation , regarded as a quadratic equation in , has the positive root
Therefore
For , the expression is strictly increasing in and less than 21. Since , the fractions in (4) decrease strictly to
This completes the proof of Theorem 1.
The first graph in the family is shown in Figure 2. It has order 12 and . This graph was first introduced by Akhmejanova et al. [1].

Figure 2. The graph .
Remark (A Pell-type interpretation). By Lemma 1, deleting a base vertex of preserves the Wiener index if and only if . Thus, to construct infinitely many such graphs, it suffices to find infinitely many positive integer solutions of this equation. An alternative way to obtain these solutions is to use a generalized Pell equation (see [2] for background). The substitution , transforms into
The initial pair corresponds to the solution . Starting with this solution, we multiply by and define the next pair by
The new pair satisfies the same Pell equation. Indeed, multiplying (5) by its conjugate, we obtain
Comparing the coefficients of 1 and in (5), we obtain
Returning to the original parameters, we obtain
These are the recurrences in Theorem 1. They ensure that and are positive integers and that . Hence they generate infinitely many distinct graphs .
Table 2 contains parameters of the smallest graphs .
| Order | Šoltés vertices | ||||
| 0 | 2 | 1 | 12 | 8 | |
| 1 | 30 | 26 | 3360 | 1800 | |
| 2 | 672 | 601 | 1710912 | 903168 | |
| 3 | 15410 | 13801 | 900283020 | 474936200 | |
| 4 | 353742 | 316826 | 474416130912 | 250266805128 | |
| 5 | 8120640 | 7273201 | 250015681956480 | 131889588019200 |
Table 2. Initial members of the infinite sequence.
Proof of Corollary 1
We first establish the following lemma.
Lemma 2. Let be a connected graph, and let be an independent set of vertices that all have the same neighbourhood , where . Let be obtained from by adding arbitrary edges between vertices of . Then, for every such that is connected,
Proof. Let and . Obviously, a shortest path in with at least one endpoint outside contains no added edge. Since any two distinct vertices of are at distance 2 in , for distinct we have if , and 0 otherwise. Hence . Since , all added edges remain in . Since , the vertices of always have a common neighbour in , and the same argument yields . Subtracting the two equalities proves the lemma. □
Proof of Corollary 1. Apply Lemma 2 successively to the sets of auxiliary vertices attached to the same base clique. For each of them, is that clique and . For every base vertex this implies
If is an auxiliary vertex, deleting does not change distances between the remaining vertices. Hence . Consequently, has the same Šoltés vertices as . □
As a particular case, add all edges within each set of auxiliary vertices, and denote the resulting graph by . It has the same Šoltés vertices as , and
Each base clique, together with its auxiliary vertices, now induces . In , base vertices have degree , and auxiliary vertices have degree .
| Auxiliary vertices | Base vertex degree | Auxiliary vertex degree | Šoltés vertices | |
| Independent | 56 | 30 | 19953600 | 1800 |
| Cliques | 56 | 55 | 19934100 | 1800 |
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 and decreases to this value from . 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 were verified computationally for several small values of and .
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]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]E. J. Barbeau, Pell’s Equation, Problem Books in Mathematics, Springer, New York, 2003.
- [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]J. Bok, N. Jedličková, J. Maxová, On relaxed Šoltés’s problem, Acta Math. Univ. Comenian. 88:3 (2019) 475–480.
- [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]D. Bonchev, D. H. Rouvray (eds.), Chemical Graph Theory: Introduction and Fundamentals, Gordon and Breach, New York, 1991.
- [7]S. Cambie, Towards the essence of Šoltés’ problem, Appl. Math. Comput. 508 (2026) 129621.arxiv.org/abs/2406.03451
- [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]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]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]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]I. Gutman, O.E. Polansky, Mathematical Concepts in Organic Chemistry. Springer–Verlag, Berlin, 1986.
- [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]M. Knor, S. Majstorović, R. Škrekovski, Graphs preserving Wiener index upon vertex removal, Appl. Math. Comput. 338 (2018) 25–32.DOI
- [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]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]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]L. Šoltés, Transmission in graphs: A bound and vertex removing, Math. Slovaca 41:1 (1991) 11–16.
- [19]N. Trinajstić, Chemical Graph Theory, CRC Press, Boca Raton, 1992.
- [20]S. Wagner, H. Wang, Introduction to Chemical Graph Theory, Chapman and Hall/CRC, 2018.DOI
- [21]H. Wiener, Structural determination of paraffin boiling points, J. Amer. Chem. Soc. 69 (1947) 17–20.pubmed.ncbi.nlm.nih.gov/20291038