betaFeedback

WorksMathematics

A 4-regular graph with 4/5 of its vertices satisfying the Šoltés property

Abstract

The Wiener index W(G)W(G) of a connected graph GG is the sum of distances between all unordered pairs of its vertices. A vertex vv is called a Šoltés vertex if G−vG-v is connected and W(G−v)=W(G)W(G-v)=W(G). Since the cycle C11C_{11} 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 44-regular graph with Šoltés fraction 4/54/5, improving the previous value of 2/32/3.

Introduction

All graphs considered are simple, undirected and connected. The vertex set of a graph GG is denoted by V(G)V(G), and its order is ∣V(G)∣|V(G)|. The girth of GG is the length of its shortest cycle. The distance dG(u,v)d_G(u,v) between two vertices uu and vv is the length of a shortest path joining them. The eccentricity of a vertex vv in a graph GG is the maximum distance between vv and any other vertex of GG. The radius and diameter of a graph GG are the minimum and the maximum vertex eccentricity, respectively. The transmission of a vertex vv of GG is the sum of the distances from vv to all other vertices of GG, that is, 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 the sum of distances over all unordered pairs of vertices,

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).

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 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 [19] posed the problem of finding graphs in which all vertices are Šoltés vertices. He also gave the cycle C11C_{11} as the first example. Since C11C_{11} 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 R0(G)R_0(G) is the proportion of vertices of GG 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 HH described below, which will be transformed as explained in the next section.

Let HH 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 HH is connected, bipartite and 4-regular, with 480 vertices and 960 edges. Its girth, diameter and radius are all 8. The graph HH is a Cayley graph of the group identified as SmallGroup(480,955) in the GAP Small Groups Library [3]. The automorphism group of HH has order 1920 and acts regularly on the arcs. In particular, HH is vertex-transitive and edge-transitive. A drawing of HH 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 v∈V(H)v \in V(H), we have W(H)−W(H−v)=579 360−577 598=1 762>0W(H) - W(H - v) = 579\,360 - 577\,598 = 1\,762 > 0.

Figure 1. The base graph HH. Red and dark blue indicate its two bipartition classes.

There are 1080 cycles of length 8 in HH, and each vertex belongs to 18 of them. A computational analysis establishes the following property of HH.

Cyclic property. For every vertex vv, four of the six paths of length 2 with middle vertex vv 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 HH be the base graph described above. We construct GG from HH as follows.

  1. Replace each vertex vv of HH by four vertices vuv_u, vwv_w, vxv_x, and vyv_y, where uu, ww, xx, and yy are the neighbors of vv, as shown in Figure 2. Each original edge uvuv becomes the edge uvvuuv_{v_u}. These new vertices have degree 1 and correspond to the arcs of HH.

Figure 2. Transformation of the base graph HH into GG.

  1. For each vertex vv and each pair of distinct neighbors uu and ww of vv, join vuv_u and vwv_w if and only if the path uvwuvw lies in exactly one cycle of length 8 in HH. By the cyclic property, for every vv exactly two of the six pairs are excluded by this rule, and these two pairs are disjoint. Hence vertices vu,vw,vx,vyv_u,v_w,v_x,v_y induce a 4-cycle CvC_v.

  1. For each vertex vv, add an auxiliary vertex zvz_v and join it to all four vertices of CvC_v.

The graph GG is connected and 4-regular, with order ∣V(G)∣=5⋅480=2400|V(G)| = 5 \cdot480 = 2400 and size ∣E(G)∣=960+8⋅480=4800|E(G)| = 960 + 8 \cdot480 = 4800. Its diameter and radius are both 18, and the girth is 3.

Every automorphism of HH preserves the rule that defines the added edges, and therefore extends to an automorphism of GG. The vertices of the cycles CvC_v correspond to the arcs of HH, and the auxiliary vertices correspond to the vertices of HH. Since HH is arc-transitive, the group induced by Aut⁡(H)\operatorname{Aut}(H) acts transitively on each of these two sets. A vertex of a cycle CvC_v lies in exactly two triangles, whereas an auxiliary vertex lies in exactly four. Hence no automorphism of GG maps a vertex of one set to a vertex of the other, so these two sets are precisely the two vertex orbits of Aut⁡(G)\operatorname{Aut}(G), of sizes 1920 and 480.

Proposition 1. The graph GG of order 2400 has exactly 1920 Šoltés vertices, and hence its Šoltés fraction equals 4/54/5.

The graph G−vG-v is connected for every v∈V(G)v \in V(G). The differences ΔG(v)=W(G)−W(G−v)\Delta_G(v) = W(G)-W(G-v) 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 typeNumberTG(v)T_G(v)W(G−v)W(G-v)ΔG(v)\Delta_G(v)
Quadrilateral192027 28932 823 1200
Auxiliary48027 60732 795 51327 607

Table 1. Transmissions and vertex-deletion values for GG.

Thus W(G)=(1920⋅27 289+480⋅27 607)/2=32 823 120W(G) = (1920 \cdot27\,289 + 480 \cdot27\,607)/2 = 32\,823\,120, and the Šoltés vertices are precisely the 1920 vertices of the quadrilaterals. Therefore, R0(G)=4/5R_0(G) = 4/5.

The dataset containing the edge list of GG 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 HH were produced using ChatGPT. The author reviewed and revised the material and takes full responsibility for the final content.

References

Appendix

The graph HH 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 HH with different rotational symmetries.

Figure 3. An alternative drawing of the base graph HH, with the same vertex colors.

Figure 4. An alternative drawing of the base graph HH, with the same vertex colors.

Figure 5. An alternative drawing of the base graph HH with the same vertex colors.

Figure 6. An alternative drawing of the base graph HH, with the same vertex colors.

References

  1. [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. [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. [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. [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 cactūs graphs, Bull. Malays. Math. Sci. Soc. 44 (2021) 3733–3745.DOI
  6. [6]S. Cambie, Towards the essence of Šoltés’ problem, Appl. Math. Comput. 508 (2026) 129621.arxiv.org/abs/2406.03451
  7. [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. [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. [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. [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. [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. [12]M. Knor, S. Majstorović, R. Škrekovski, Graphs preserving Wiener index upon vertex removal, Appl. Math. Comput. 338 (2018) 25–32.
  13. [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. [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. [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. [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. [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. [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. [19]L. Šoltés, Transmission in graphs: A bound and vertex removing, Math. Slovaca 41:1 (1991) 11–16.
  20. [20]N. Trinajstić, Chemical Graph Theory, CRC Press, Boca Raton, 1992.
  21. [21]S. Wagner, H. Wang, Introduction to Chemical Graph Theory, Chapman and Hall/CRC, 2018.DOI
  22. [22]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_yne6r6cg
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 (OpenAI)

View statement
Looking for related papers…
Contents