CS Paper Radar

Hamilton-connected cores and five cycle--wheel Ramsey numbers

Zehui Shao, Hanxin Jiang

cs.DM math.CO ·submitted 2026-09-30 11:10 UTC · v1
theory

Abstract

Let $W_s=K_1+C_{s-1}$ denote the wheel on $s$ vertices. We give structural proofs that $R(C_{14},W_{11})=27$ and $R(C_{15},W_{11})=29$. Together with the theorem of Chen et al. for $n\ge16$, these equalities give $R(C_n,W_{11})=2n-1$ for every $n\ge14$. The two boundary values were included in an earlier survey announcement. We also give structural proofs of $R(C_8,W_7)=15$, $R(C_9,W_7)=17$, and $R(C_8,W_9)=15$. The common starting point is a Hamilton-connected core lemma. For the eleven-vertex wheel, bounds on vertex connectivity and on the matching number of a bipartite graph associated with a local cycle yield a vertex cut of order nine. Paths with prescribed endpoints then rule out every possible pair of orders of the two remaining vertex sets. For the smaller wheels, we use the structure of critical cycle colorings and local cycle-shortening arguments. We also give complete structural classifications of the $(C_8,C_6)$- and $(C_9,C_6)$-critical colorings, recovering the previously reported counts 24 and 26. All proofs are combinatorial and use no exhaustive graph enumeration.

Closest papers

Nearest neighbours by meaning across the whole index.

Hamilton Cycles in 10-Tough $(2P_2 \cup P_1)$-Free Graphs

cs.DM math.CO ·2026-08-25 ·Qiuyu Chen
theory similarity 0.66
Abstract · 16 pages, no figures

A graph is called 10-tough and $(2P_2 \cup P_1)$-free if every vertex set whose deletion leaves at least two components has cardinality at least ten times the number of those components and if the graph has no induced subgraph consisting of two disjoint edges and an isolated vertex. We prove that every finite simple 10-tough $(2P_2 \cup P_1)$-free graph on at least three vertices is Hamiltonian. The proof splits according to whether some edge has joint neighbourhood of order at most $4n/11$. In the small-neighbourhood case, a matched path-cover is compressed to a prescribed matching. In the large-neighbourhood case, an asymmetric analysis of the two components left by a putative small cut yields the required connectivity bound. A Hamilton cycle through the prescribed edges is then expanded, and a cycle-extension lemma inserts the remaining vertices.

0.09

An Improved Bound for Smith's Longest Cycles Conjecture via a Forbidden Subdivision

cs.DM math.CO ·2026-08-31 ·Douglas M. Chen
hot direction similarity 0.66
Abstract · 9 pages, 2 figures. Comments welcome!

Smith's conjecture asserts that in every $k$-connected graph with $k\geq 2$, any two longest cycles intersect in at least $k$ vertices. In this work, we establish an $Ω(k^{8/11})$ bound for this conjecture, improving upon the $Ω(k^{2/3})$ bound of Ma and Zhao. Our proof combines a Ramsey theoretic refinement of the traditional Turán-type approach with computer search.

0.50

A linear bound for nested cycles without geometric crossings

cs.DM math.CO ·2026-09-02 ·Jiangdong Ai, Gregory Gutin, Yiming Hao
theoryhot direction similarity 0.63
Abstract

Cycles $C_1,\ldots,C_k$ in a graph are called nested without geometric crossings if they are pairwise edge-disjoint, $V(C_k)\subseteq\cdots\subseteq V(C_1)$, and each pair of consecutive cycles induces the same cyclic order on the vertices of the inner cycle, up to reversal. Let $f_k(n)$ be the least number of edges that forces such a family in every $n$-vertex graph. Gil Fernández, Kim, Kim and Liu proved that $f_2(n)=O(n)$, answering a question of Erdős, and asked whether $f_k(n)=O_k(n)$ for every fixed $k$. We prove this for all $k$. The proof selects the inner cycles together with a disjoint subgraph that supplies their external neighbours. A reselection argument gives disjoint paths from every inner-cycle vertex to any sufficiently large target set. Sublinear expansion and a rooted clique minor then allow the vertices to be joined in the required cyclic order.

0.25

Completing the Boundary Case of the Mahmoodian-Mirzakhani Conjecture and 117 New Computational 5-Cycle Decompositions of Complete Tripartite Graphs

cs.DM math.CO ·2026-08-18 ·Roozbeh Pournader
theory similarity 0.62
Abstract · 15 pages; for associated data files, see https://doi.org/10.5281/zenodo.21882725

Let $K_{r,s,t}$, with $r\le s\le t$, denote the complete tripartite graph whose partite sets have sizes $r,s,t$. Mahmoodian and Mirzakhani gave three necessary conditions for $K_{r,s,t}$ to admit a decomposition into 5-cycles and conjectured that these conditions are sufficient. One of the conditions is $t\le 4rs/(r+s)$. We prove the conjecture for every odd triple on the extremal boundary $t = 4rs/(r+s)$. The proof is constructive. After reducing an arbitrary odd boundary triple to $(r,s,t)=(hga,hgb,hab)$, $a+b=4g$, we give an explicit cyclic decomposition of $K_{ga,gb,ab}$ and use the Mahmoodian and Mirzakhani scaling theorem to supply the common factor $h$. Together with the previously known all-even result, this settles the conjecture for every triple satisfying the boundary condition with equality. We also report explicit computer-generated $C_5$-decompositions for 117 odd triples satisfying the necessary conditions, 116 of which are strict-interior cases. To the best of our knowledge, all 117 cases were previously unresolved: no decomposition for any of them had been reported, and none of the 117 triples is covered by earlier existence results, constructions, or their recursive consequences. Moreover, these 117 certificates together with the boundary construction settle every previously unresolved triple satisfying the necessary conditions with fewer than $4400$ edges. Each computation is supplied as a machine-readable cycle-list certificate and can be checked independently by a short Python verifier. We also give a complete human-readable edge-label-matrix certificate for $K_{9,19,23}$.

0.31

Lower bounds for Ramsey numbers: $\mathrm{R}(6,8)\ge 135$ and $\mathrm{R}(8,10)\ge 345$

cs.DM math.CO ·2026-10-08 ·Fritz Cremer
theory similarity 0.59
Abstract · 8 pages, 2 figures

We prove the lower bounds $\mathrm{R}(6,8)\ge 135$ and $\mathrm{R}(8,10)\ge 345$, improving the bounds 134 and 343 listed in the April 2026 revision of Radziszowski's dynamic survey. We give explicit red/blue colorings of $K_{134}$ with no red $K_6$ or blue $K_8$, and of $K_{344}$ with no red $K_8$ or blue $K_{10}$, and verify them with two independently written exhaustive clique checkers. Starting from published colorings, we find these witnesses by adding vertices and repairing the resulting monochromatic cliques through local search. The search uses exact conflict counts, preparation moves aimed at making remaining cliques cheaper to break, and mutations followed by repair. A loss based on the largest monochromatic clique containing each edge yielded a useful intermediate state for the $\mathrm{R}(6,8)$ construction. Guided by the author, an AI coding agent wrote and ran the search code; we describe the methods and document the ancestry of the resulting colorings.

0.11

Fault-tolerant Hamiltonian connectivity of Johnson graphs

cs.DM ·2026-09-11 ·Huazhong Lü, Jinhao Liu
theory similarity 0.59
Abstract

Johnson graphs $J(n,k)$ are a classical family of highly symmetric networks known to be Hamiltonian-connected in the fault-free setting. In this paper, we investigate their Hamiltonian connectivity under three failure models, namely general edge faults, matching faults, and vertex faults. For general edge faults, we prove that $J(n,k)$ remains Hamiltonian-connected after the deletion of any set of at most $k(n-k)-3$ edges for $n\geq4$. Since $J(n,k)$ is $k(n-k)$-regular, this attains the natural degree-based upper bound for Hamiltonian connectivity. We then consider matching faults, which exclude the concentration of multiple faulty links at a single vertex and permit substantially larger fault sets. We show that $J(n,k)$ remains Hamiltonian-connected after the deletion of an arbitrary matching for $n\geq5$, including a perfect matching whenever one exists. For vertex failures, we prove that $J(n,k)$ is $(n-2)$-vertex-fault-tolerant Hamiltonian-connected for $n\geq5$. All three results are constructive and lead to recursive fault-tolerant Hamiltonian routing algorithms. Simulation results on Johnson graphs with up to $12{,}870$ vertices further show that the routing algorithms successfully construct fault-free Hamiltonian paths for all tested source-destination pairs, with measured execution times exhibiting near-linear growth with network size. These results establish a unified fault-tolerant Hamiltonian-connectivity framework for Johnson graphs under different failure patterns.

0.21

A Proof of Albertson's Conjecture

cs.CG math.COcs.DM ·2026-09-01 ·Ankan Sadhu
theory similarity 0.58
Abstract · 29 Pages. This version extends and supersedes the previous v2. Substantially revised proofs and exposition; new terminal-graph argument, exp…

Albertson's conjecture states that every graph of chromatic number r has crossing number at least that of the complete graph K_r. We prove the conjecture for all r. The proof combines new clique-sensitive edge bounds for critical graphs, maximum-clique sampling, and a reserved immersion construction. For graphs of order close to r, we construct edge-disjoint routes while preserving a complete bipartite subgraph whose forced crossings compensate for those introduced when the immersion is smoothed into a drawing. For larger orders, we derive explicit edge bounds using independent-triple deletion and structural properties of critical graphs, then combine them with sampling inequalities that account for crossings within a maximum clique. The remaining numerical inequalities are certified using exact rational arithmetic, with a reproducible certificate and standalone Python verifier.

0.31

A Necessary and Sufficient Hall Condition for Hypergraphs

cs.DM math.COcs.DS ·2026-08-10 ·Xiaoyao Huang
theory similarity 0.58
Abstract · 17 pages, 3 figures; new content in sections 1 and 4

We prove a necessary and sufficient Hall condition for a family $A=(A_e)_{e\in E(G)}$ of hypergraphs indexed by the edges of a forest \(G\). This restriction on the index graph is sharp. The loop-only case recovers the classical Hall's Theorem with multiplicities for arbitrary finite set systems, while the loopless case shows that full rainbow matching is polynomial time solvable under this forest structure, although the problem is NP-complete in general. As another application, we prove every $5$-tough chordal graph is Hamilton-connected, improving toughness bounds of $18$ for Hamiltonicity (1998) and $10$ for Hamilton-connectedness (2017).

0.44