Abundancy of $z$-Šoltés' digraphs

Basic Information

• Paper ID: 2501.00102
• Title: Abundancy of $z$-Šoltés' digraphs
• Author: Stijn Cambie (KU Leuven Campus Kulak-Kortrijk)
• Classification: math.CO (Combinatorics)
• Submission Date: December 30, 2024
• Paper Link: https://arxiv.org/abs/2501.00102

Abstract

This paper proves the existence of infinitely many Šoltés digraphs, which are directed graph analogues of Šoltés graphs. Additionally, an example of a Šoltés digraph with trivial automorphism group is provided.

Research Background and Motivation

Problem Background

1. Definition of Šoltés graphs: Originating from Šoltés' 1991 paper, Šoltés graphs are graphs where the total distance decreases by exactly a fixed value upon removal of any vertex.
2. Generalization to digraphs: This paper extends this concept to directed graphs, defining $z$-Šoltés digraphs as digraphs where the total distance decreases by exactly $z$ upon removal of any vertex.
3. Special cases: When $z=0$, these are called Šoltés digraphs; when $z \leq 0$, they are called negative Šoltés digraphs.

Research Motivation

1. Theoretical completion: Answering Question 13 in reference 5 regarding whether infinitely many negative Šoltés graphs with minimum degree at least 3 exist.
2. Directed graph perspective: Strengthening understanding of the original problem by confirming this conjecture in the directed graph case.
3. Abundance proof: Demonstrating not only the infinite existence of negative Šoltés digraphs but also of Šoltés digraphs.

Core Contributions

1. Main Theorem: Proves that for each integer $z$, there exist infinitely many digraphs $D$ such that $W(D) - W(D \setminus v) = z$ for any vertex $v$.
2. Infinity of Šoltés digraphs: As a corollary of the main theorem, proves the existence of infinitely many Šoltés digraphs.
3. Concrete constructions: Provides specific examples of Šoltés digraphs, including $D(11,\{1\}) \cong C_{11}$ and $D(85,\{4\})$.
4. Non-vertex-transitive example: Constructs a Šoltés digraph of order 3306 with trivial automorphism group, strongly refuting the directed graph analogue of a related conjecture.

Methodology Details

Core Definition

Definition 4: For a subset $S \subseteq [n-2] = \{1,2,\ldots,n-2\}$, define the circulant digraph $D(n,S)$ with vertex set $V = [n]$ and directed edge set: $E = \{(i, i-1) | i \in [n]\} \cup \{(i, i+k) | i \in [n], k \in S\}$ where numbers are interpreted modulo $n$.

Construction Strategy

1. Dense digraphs for positive values: Proposition 5 proves that when $\delta^-(D) + \delta^+(D) \geq n \geq 4$, we have $W(D) - W(D \setminus v) > 0$.
2. Sparse digraphs for negative values: Proposition 6 proves that when $\max S \leq \frac{1}{9}n^{1/2}$ and $n$ is sufficiently large, we have $W(D_{n,S}) - W(D_{n,S} \setminus v) < 0$.

Main Proof Strategy

The proof proceeds through three key steps:

Step 1 (Claim 7): Choose $n \sim 6m^2$ such that $D(n,[m])$ satisfies $z-9m \leq W(D) - W(D-v) \leq z-3$.

Step 2 (Claim 8): By removing certain large elements from $[m]$, construct $D(n,[m-\ell] \cup \{m-1,m\})$ such that the difference is near $z$ and even.

Step 3: By precisely removing an appropriate number of odd elements, finally obtain $W(D) - W(D \setminus v) = z$.

Experimental Setup

Concrete Examples Verification

1. Small-scale examples: $D(11,\{1\}) \cong C_{11}$ and $D(85,\{4\})$ are both Šoltés digraphs.
2. Large-scale construction: Constructs a non-vertex-transitive Šoltés digraph of order 3306 with trivial automorphism group.

Computational Verification

For $D(85,\{4\})$, verification shows that upon removing vertex $v$, the distance from its left neighbors to right neighbors changes from 2 to 22, demonstrating the redistribution of distances.

Experimental Results

Main Results

1. Proof of Theorem 1: Successfully constructs infinitely many $z$-Šoltés digraphs for any integer $z$.
2. Concrete examples:
   • $D(85,\{4\})$ is a concrete Šoltés digraph
   • Constructs a 2-regular, bipartite but non-vertex-transitive Šoltés digraph of order 960
   • Constructs a Šoltés digraph of order 3306 with trivial automorphism group

Technical Details Verification

Appendix B provides detailed calculations of specific parameter choices:

• When $a = 6m-1$, $r = m$: $W(D-v) - W(D) = \frac{7}{2}m^2 - O(m) > z$
• When $a = 6m-1$, $r = 0$: $W(D-v) - W(D) = -\frac{5}{2}m^2 - O(m) < z - 9m$

Related Work

Historical Development

1. Original Šoltés work: Šoltés first introduced the concept in 1991
2. Applications in graph theory: Related research on the Wiener index (total distance)
3. Vertex-transitive graphs: Directed graph analogues of Adam's conjecture and counterexamples

Positioning of This Paper's Contribution

This paper generalizes the Šoltés property from graph theory to directed graphs and provides systematic existence proofs through circulant digraph construction methods.

Conclusions and Discussion

Main Conclusions

1. For any integer $z$, there exist infinitely many $z$-Šoltés digraphs
2. In particular, there exist infinitely many Šoltés digraphs (the case $z=0$)
3. There exist Šoltés digraphs with trivial automorphism group, strongly refuting related conjectures

Theoretical Significance

These findings strengthen the intuition from reference 5 regarding the graph case, namely that the essence of the problem lies in the extremal question of infinite existence of negative Šoltés graphs. If clearly abundant negative Šoltés graphs exist, we can expect Šoltés graphs to be equally abundant.

Future Directions

1. Study precise enumeration of non-isomorphic $z$-Šoltés digraphs
2. Explore similar properties in other graph classes
3. Investigate relationships between Šoltés properties and other graph-theoretic parameters

In-Depth Evaluation

Strengths

1. Theoretical completeness: Systematically resolves the generalization of Šoltés graphs to directed graphs
2. Innovative construction methods: Achieves precise parameter control through clever circulant digraph constructions
3. Strength of counterexamples: The constructed example with trivial automorphism group strongly refutes related conjectures
4. Computational rigor: Detailed calculations in the appendix ensure result reliability

Technical Highlights

1. Stepwise construction strategy: Decomposes complex existence proofs into three controllable steps
2. Parameter optimization: Achieves optimal parameter balance through the choice $n \sim 6m^2$
3. Parity control: Cleverly exploits removal of odd elements to achieve precise difference adjustment

Limitations

1. Construction complexity: While existence is proven, the concrete construction process is quite involved
2. Counting problems: Precise enumeration of non-isomorphic graphs remains difficult
3. Application scope: Primarily theoretical results with limited practical application value

Impact Assessment

1. Theoretical contribution: Provides a complete directed graph solution to the Šoltés problem in combinatorial graph theory
2. Methodological value: Circulant digraph construction methods may be applicable to other similar problems
3. Refutation value: The refutation of related conjectures has important theoretical significance

References

The paper cites 10 major references covering original Šoltés work, Wiener index research, circulant graph theory, and related combinatorial optimization problems, reflecting the systematicity and completeness of the research.