Uniform Šoltés’ hypergraphs and Šoltés’ weighted graphs

Stijn Cambie, Ajay Tiwari · 2025

Read Uniform Šoltés’ hypergraphs and Šoltés’ weighted graphs by Stijn Cambie, Ajay Tiwari (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-07511.txt.

Introduction

Stijn Cambie and Ajay Tiwari settle a distance puzzle for hypergraphs and weighted graphs. Their paper from twenty twenty-five studies Šoltés objects, where removing any one vertex leaves total distance unchanged. The classic problem asked whether such graphs exist beyond one known case. Hypergraphs widen the stage: edges can hold many vertices at once.

The team proves each uniform Šoltés hypergraph needs at least a set count of vertices. Such hypergraphs exist for near all orders and uniformities. One example is not even regular, which widens the family. Infinitely many weighted Šoltés graphs are built as well. Together these say the puzzle answers yes for the most natural widenings of graphs. Total distance can indeed survive any single vertex loss.

Catalog record

CREATORStijn Cambie, Ajay Tiwari
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE27 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-07511

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Uniform Šoltés’ hypergraphs and Šoltés’ weighted graphs Stijn Cambie, Ajay Tiwari Abstract A Šoltés’ hypergraph is a hypergraph for which the removal of any of its vertices does not change its total distance. We prove that every uniform Šoltés’ hypergraph has order at least 10 10 , there exist uniform Šoltés’ hypergraphs for almost every order or uniformity, and there exist a non-regular uniform Šoltés’ hypergraph. By also providing infinitely many weighted Šoltés’ graphs, we conclude that Šoltés’ problem can be answered positively for the most natural generalisations of graphs. 1 Introduction The Šoltés’ problem [ 7 ] , which asks about graphs for which vertex removal does not change the total distance, has been studied extensively in the context of graph theory, with recent work extending this problem to hypergraphs [ 3 ] . In this paper, we build upon this prior research, focusing specifically on uniform hypergraphs. We assume that the reader is familiar with basic terminology; for those unfamiliar, we refer to [ 3 , Subsec. 1.1] . We address 4 subquestions posed in [ 3 , Ques. 13] . The main results are summarised as follows: • the smallest uniform Šoltés’ hypergraphs have order 10 , • for every n\geq 10 , there exists a uniform Šoltés’ hypergraph of order n , • for most integers k\geq 4 , there exists a k -uniform Šoltés’ hypergraph, • there exists a non-regular uniform Šoltés’ hypergraph. The problem of Šoltés has been considered for various extensions of graphs, and for each of these, one has concluded that there is an abundancy for the analogue of Šoltés’ problem. We first recall a few definitions from [ 8 ] . A signed graph is a pair (G,f) where G is a graph and f is a function from E(G) to \{\pm 1\} , which is called a signing . If P is a path in G and f is a signing of G , f(P):=\sum_{e\in P}f(e). For u,v\in V(G) , the signed distance is defined as d_{G,f}(u,v)=\min_{P}\lvert f(P)\rvert where the minimum ranges over all uv -paths P . The Wiener index W_{f}(G) of the signed graph (G,f) equals W_{f}(G)=\sum_{\{u,v\}\subset V(G)}d_{f}(u,v). Spiro [ 8 , Cor. 1.2] proved that the Šoltés’ problem has an abundance of solutions for signed graphs, including generalisations involving the removal of subsets of vertices. Specifically, the following result holds: Theorem 1 ( [ 8 ] ) . If n is sufficiently large and G is an n -vertex graph with minimum degree at least \frac{2n}{3} , then there exists a signing f of G such that the signed graph (G,f) has Šoltés’ property in a strong form, W_{f}(G)=W_{f}(G-v)=0\quad\text{for all }v\in V(G). Cambie [ 1 , Thm. 1] proved abundancy for the Šoltés’ problem in the digraph (directed graph) setting, as stated below, and gave an example of a large Šoltés’ digraph with trivial automorphism (no two vertices belong to the same vertex orbit). Theorem 2 ( [ 1 ] ) . For every z\in\mathbb{Z}, there are infinitely many digraphs D for which W(D)-W(D\setminus v)=z for every v\in V. While not proven in detail, the same should be true for oriented graphs. We also note that for weighted graphs (with positive weights) Šoltés’ problem has infinitely many solutions. A concrete example is drawn in Fig. 1 . Example 3 . For every k\geq 20 , let n=2k and let G be the prism graph C_{n}\square K_{2} , for which the edges of the two induced cycles C_{n} have all weight 1 and the remaining edges have weight x=\frac{2k^{2}-6k+16}{k^{2}-9k+12} . Then W(G)=W(G\setminus v) for every v\in V(G). Proof. Note that 2<x\leq 3 since k\geq 20 and the weighted graph is vertex-transitive. An elementary computation shows that W(G)=4W(C_{n})+n^{2}x=\frac{n^{3}}{2}+n^{2}x and thus \sigma(v)=\frac{n^{2}}{2}+nx=2k^{2}+2kx for every v\in v(G). Furthermore, the detours are exactly between vertices u,w\in V(G)\setminus v on the same induced C_{n} as v , for which the shortest path in G (and thus the C_{n} ) uses v . The detour is 2 or 4 if d(u,v)=k-1 or d(u,v)=k-2 respectively, or 2x if d(u,v)\leq k-3. Counting the pairs of vertices with these properties, implies that the sum of detours equals \sum_{\begin{subarray}{c}u,w\in V\setminus\{v\}\end{subarray}}\big[d_{G\setminus v}(u,w)-d(u,w)\big]=(k-3)(2+4)+2+2x\binom{k-3}{2}=6k-16+x(k-3)(k-4). By the choice of x, the sum of detours and the transmission of v are equal and thus W(G)=W(G\setminus v) . ∎ Remark 4 . By multiplying the weights of 3 with \frac{k^{2}-9k+12}{\gcd(2k^{2}-6k+16,k^{2}-9k+12)} , one can conclude there are infinitely many examples of weighted graphs with weights in \mathbb{Z}^{+} which satisfy the Šoltés’ property and for which the greatest common divisor of weights is 1 (to prevent C_{11} with 11 times the same arbitrary weight to be considered as an infinite family). The cycle C_{10} with alternating edges having weight 0 and 1 can be considered as a small example. We conclude that in the most natural generalisations of graphs 1 1 1 This is a slightly subjective statement. Some people may consider e.g. matroids, in which case the problem is again quite different. (digraphs, uniform hypergraphs, weighted graphs) Šoltés’ problem has infinitely many solutions. 1 1 3 Figure 1 : A weigthed Šoltés’ graph of order 80 For resolving the graph case, we refer to the survey [Sec. 6] [ 6 ] and the paper [ 2 ] . The main intermediate question asks if there are infinitely many graphs with minimum degree at least 3 , for which the removal of any vertex implies an increase of the total distance. This is essential for possible abundance of Šoltés’ graphs, as was the case in the other settings. Overview and outline of the paper In Section 2 , we prove that there is no uniform Šoltés’ hypergraph with order bounded by 9. We do so by applying different strategies for different pairs (n,k) of order and uniformity on a possible Šoltés’ hypergraph H . • The case k=2 was excluded by a brute force computer check. • If k\geq n-3\geq 3 , the connected hypergraph H\setminus v of order n-1 satisfies W(H\setminus v)\leq\binom{n-1}{2}+4<\binom{n}{2}\leq W(H) . • If k=n-4\geq 3, we can exclude hypergraphs with small size by computer verification and for hypergraphs with large size, we check that W(H\setminus v)<\binom{n}{2}\leq W(H) . • If k=3 and n\in\{8,9\} , we take a vertex v for which H\setminus v has the largest possible value of n_{1} , the number of adjacent pairs of vertices, and conclude that W(H\setminus v)<W(H) in most cases. For the latter, we notice that two adjacent vertices can be non-adjacent in at most one hypergraph of the form H\setminus v. The few remaining (sparse) cases in which W(H\setminus v)<W(H) cannot be concluded, are checked by computer. • The case (n,k)=(9,4) is the main case. In this case, H has diameter 2 and thus the number of adjacent vertices plays an important role in the computation of the total distance W(H). Here we first prove multiple side results on the transmission and sum of detours (increase of distances due to removal another vertex) in special cases. It is observed that adjacent pairs can be non-adjacent in at most two hypergraphs of the form H\setminus v, and equality leads to some structure. In the main proof, these observations are combined and it is proven that for

Read the complete text