PreprintCC BY 4.0arXiv
An infinite family of graphs with Šoltés fraction uniformly above one half
Abstract
The Wiener index W(G) of a connected graph G is the sum of the distances between all unordered pairs of vertices. A vertex x is a Šoltés vertex if G−x is connected and 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 and decreases to this value from 2/3. The family is also described by a generalized Pell equation and starts from a $12$-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.
Related
- An infinite family of intransitive directed strongly regular graphs with rank 6 Weisfeiler--Leman closure
- A new infinite family of covers of complete graphs that admit a half-transitive action of a Suzuki simple group
- On Almost Uniformly Locally Finite Graphs
- Rainbow spanning configurations in uniformly coloured pseudorandom graphs
- Graphs versus loopless digraphs with a given degree sequence, and convergence of uniformly random graphs at every density
BibTeX
@misc{dobrynin2026infinite,
title = {{An infinite family of graphs with Šoltés fraction uniformly above one half}},
author = {A. A. Dobrynin},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.01808},
eprint = {2611.01808},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.01808},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - An infinite family of graphs with Šoltés fraction uniformly above one half
AU - A. A. Dobrynin
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.01808
UR - https://arxiv.org/abs/2611.01808
AB - The Wiener index W(G) of a connected graph G is the sum of the distances between all unordered pairs of vertices. A vertex x is a Šoltés vertex if G−x is connected and 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 and decreases to this value from 2/3. The family is also described by a generalized Pell equation and starts from a $12$-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.
ER -