WorksMathematics
A 4-regular graph with 4/5 of its vertices satisfying the Šoltés property
Abstract
The Wiener index of a connected graph is the sum of distances between all unordered pairs of its vertices. A vertex is called a Šoltés vertex if is connected and . Since the cycle is the only known graph in which every vertex is a Šoltés vertex, a natural problem is to construct other graphs with as large a proportion of such vertices as possible. We construct a -regular graph with Šoltés fraction , improving the previous value of .
Introduction
All graphs considered are simple, undirected and connected. The vertex set of a graph is denoted by , and its order is . The girth of is the length of its shortest cycle. The distance between two vertices and is the length of a shortest path joining them. The eccentricity of a vertex in a graph is the maximum distance between and any other vertex of . The radius and diameter of a graph are the minimum and the maximum vertex eccentricity, respectively. The transmission of a vertex of is the sum of the distances from to all other vertices of , that is, . The Wiener index of is the sum of distances over all unordered pairs of vertices,
The Wiener index was introduced as a structural descriptor for molecular graphs [22]. Its mathematical properties and numerous applications, in particular in organic chemistry, have been extensively studied; see, for example, [8, 9, 14, 15, 20, 21].
A vertex is called a Šoltés vertex if is connected and . In 1991, Šoltés [19] posed the problem of finding graphs in which all vertices are Šoltés vertices. He also gave the cycle as the first example. Since is the only known example, various relaxations of this problem have been studied, including the question of how large a proportion of the vertices can have this property. The Šoltés fraction is the proportion of vertices of that are Šoltés vertices. A number of graph families with prescribed numbers of Šoltés vertices and graphs from restricted classes were constructed in [2, 4, 5, 7, 10, 11, 12, 13]. The Šoltés fraction of graphs from these studies does not exceed 2/3. Akhmejanova et al. [1] presented the first graph of order 12 with eight Šoltés vertices and the fraction 2/3. Cambie [6] described eight graphs with Šoltés fraction 2/3, including this example. He also proposed a conditional construction of graphs with Šoltés fraction approximately 5/7.
In this note we construct a 4-regular graph of order 2400 with exactly 1920 Šoltés vertices, and hence with Šoltés fraction 4/5.
The base graph
To construct a 4-regular graph with Šoltés fraction 4/5, we use the base graph described below, which will be transformed as explained in the next section.
Let denote the graph AT4val[480,150] in the census of connected tetravalent arc-transitive graphs of order at most 640 compiled by Potočnik, Spiga and Verret [16, 17, 18]. The graph is connected, bipartite and 4-regular, with 480 vertices and 960 edges. Its girth, diameter and radius are all 8. The graph is a Cayley graph of the group identified as SmallGroup(480,955) in the GAP Small Groups Library [3]. The automorphism group of has order 1920 and acts regularly on the arcs. In particular, is vertex-transitive and edge-transitive. A drawing of is shown in Figure 1 (see the Appendix for other drawings). The distance partition with respect to a vertex has layers of sizes 1, 4, 12, 36, 93, 154, 129, 46, and 5. Hence every vertex has transmission 2414. For every , we have .
Figure 1. The base graph . Red and dark blue indicate its two bipartition classes.
There are 1080 cycles of length 8 in , and each vertex belongs to 18 of them. A computational analysis establishes the following property of .
Cyclic property. For every vertex , four of the six paths of length 2 with middle vertex are contained in exactly one cycle of length 8, and the other two, which have no edge in common, are contained in exactly seven such cycles.
Construction of the graph
Let be the base graph described above. We construct from as follows.
Replace each vertex of by four vertices , , , and , where , , , and are the neighbors of , as shown in Figure 2. Each original edge becomes the edge . These new vertices have degree 1 and correspond to the arcs of .
Figure 2. Transformation of the base graph into .
For each vertex and each pair of distinct neighbors and of , join and if and only if the path lies in exactly one cycle of length 8 in . By the cyclic property, for every exactly two of the six pairs are excluded by this rule, and these two pairs are disjoint. Hence vertices induce a 4-cycle .
For each vertex , add an auxiliary vertex and join it to all four vertices of .
The graph is connected and 4-regular, with order and size . Its diameter and radius are both 18, and the girth is 3.
Every automorphism of preserves the rule that defines the added edges, and therefore extends to an automorphism of . The vertices of the cycles correspond to the arcs of , and the auxiliary vertices correspond to the vertices of . Since is arc-transitive, the group induced by acts transitively on each of these two sets. A vertex of a cycle lies in exactly two triangles, whereas an auxiliary vertex lies in exactly four. Hence no automorphism of maps a vertex of one set to a vertex of the other, so these two sets are precisely the two vertex orbits of , of sizes 1920 and 480.
Proposition 1. The graph of order 2400 has exactly 1920 Šoltés vertices, and hence its Šoltés fraction equals .
The graph is connected for every . The differences were computed by the author for all 2400 vertices using a program written in Delphi 12. The results for the two vertex orbits are shown in Table 1.
| Vertex type | Number | |||
| Quadrilateral | 1920 | 27 289 | 32 823 120 | 0 |
| Auxiliary | 480 | 27 607 | 32 795 513 | 27 607 |
Table 1. Transmissions and vertex-deletion values for .
Thus , and the Šoltés vertices are precisely the 1920 vertices of the quadrilaterals. Therefore, .
The dataset containing the edge list of and its graph6 and sparse6 encodings is available from the author upon request.
Acknowledgments
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. All drawings of the base graph were produced using ChatGPT. The author reviewed and revised the material and takes full responsibility for the final content.
References
Appendix
The graph admits Cayley representations over three pairwise non-isomorphic groups, identified in the Small Groups Library of GAP as SmallGroup(480,219), SmallGroup(480,955), and SmallGroup(480,959). The figures below show drawings of with different rotational symmetries.
Figure 3. An alternative drawing of the base graph , with the same vertex colors.
Figure 4. An alternative drawing of the base graph , with the same vertex colors.
Figure 5. An alternative drawing of the base graph with the same vertex colors.
Figure 6. An alternative drawing of the base graph , with the same vertex colors.
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 Appl. Math. 325 (2023) 37–42.DOI
- [2]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
- [3]H. U. Besche, B. Eick, E. O’Brien, SmallGrp, The GAP Small Groups Library, Version 1.7.0 (2026), GAP package, https://gap-packages.github.io/smallgrp/.
- [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 cactūs graphs, Bull. Malays. Math. Sci. Soc. 44 (2021) 3733–3745.DOI
- [6]S. Cambie, Towards the essence of Šoltés’ problem, Appl. Math. Comput. 508 (2026) 129621.arxiv.org/abs/2406.03451
- [7]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.
- [8]A. A. Dobrynin, R. C. Entringer, I. Gutman, Wiener index of trees: theory and applications, Acta Appl. Math. 66:3 (2001) 211–249.DOI
- [9]A. A. Dobrynin, I. Gutman, S. Klavžar, P. Žigert, Wiener index of hexagonal systems, Acta Appl. Math. 72:3 (2002) 247–294.DOI
- [10]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.
- [11]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.
- [12]M. Knor, S. Majstorović, R. Škrekovski, Graphs preserving Wiener index upon vertex removal, Appl. Math. Comput. 338 (2018) 25–32.
- [13]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.
- [14]M. Knor, R. Škrekovski, A. Tepeh, Mathematical aspects of Wiener index, Ars Math. Contemp. 11:2 (2016) 327–352.arxiv.org/abs/1510.00800
- [15]M. Knor, R. Škrekovski, A. Tepeh, Selected topics on Wiener index, Ars Math. Contemp. 24:4 (2024) P4.07.arxiv.org/abs/2303.11405
- [16]P. Potočnik, P. Spiga, G. Verret, Cubic vertex-transitive graphs on up to 1280 vertices, J. Symb. Comput. 50 (2013), 465–477.
- [17]P. Potočnik, P. Spiga, G. Verret, Bounding the order of the vertex-stabiliser in 3-valent vertex-transitive and 4-valent arc-transitive graphs, J. Combin. Theory Ser. B 111 (2015), 148–180.
- [18]P. Potočnik, P. Spiga, G. Verret, Census of arc-transitive tetravalent graphs on up to 640 vertices, https://graphsym.net/. Magma data file: Census4val-640.mgm.
- [19]L. Šoltés, Transmission in graphs: A bound and vertex removing, Math. Slovaca 41:1 (1991) 11–16.
- [20]N. Trinajstić, Chemical Graph Theory, CRC Press, Boca Raton, 1992.
- [21]S. Wagner, H. Wang, Introduction to Chemical Graph Theory, Chapman and Hall/CRC, 2018.DOI
- [22]H. Wiener, Structural determination of paraffin boiling points, J. Amer. Chem. Soc. 69 (1947) 17–20.pubmed.ncbi.nlm.nih.gov/20291038





