PreprintarXiv licencearXiv
Conditions for traceability under a bound on the size of even-distance sets
Abstract
We make partial progress towards a proof of Conjecture 189 of Written on the Wall II by showing that a connected graph G satisfying max{disteven(v):v∈ V(G)}≤ d2+1, where disteven(v) is the number of vertices at an even distance from v and d2 is the second smallest degree of G, is traceable whenever at least one of four conditions holds. These conditions involve the vertex-connectivity, order, and diameter of G.
Related
- Finite Matrix Rings of Even Size Are Determined by Their Commuting Graphs
- The Multicolour Size--Ramsey Number of an Even Cycle
- A nearly tight bound on the probability G(n,p) is even-degenerate
- The Erdős--Ginzburg--Ziv constant of Cnr for even n: rigid sequences, products, and growth beyond Harborth's bound
- The Erdős-Gallai bound for consecutive even cycle lengths
BibTeX
@misc{easwar2026conditions,
title = {{Conditions for traceability under a bound on the size of even-distance sets}},
author = {Rohun Easwar and Shaurya Johari},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.11719},
eprint = {2609.11719},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.11719},
}
RIS
TY - UNPB
TI - Conditions for traceability under a bound on the size of even-distance sets
AU - Rohun Easwar
AU - Shaurya Johari
PY - 2026
DA - 2026/09/10
PB - arXiv
DO - 10.48550/arxiv.2609.11719
UR - https://arxiv.org/abs/2609.11719
AB - We make partial progress towards a proof of Conjecture 189 of Written on the Wall II by showing that a connected graph G satisfying max{dist_even(v):v∈ V(G)}≤ d_2+1, where dist_even(v) is the number of vertices at an even distance from v and d_2 is the second smallest degree of G, is traceable whenever at least one of four conditions holds. These conditions involve the vertex-connectivity, order, and diameter of G.
ER -