CS Paper Radar

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

Qiuyu Chen

cs.DM math.CO ·submitted 2026-08-25 04:14 UTC · v1
theory

Abstract

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.

Comment
16 pages, no figures

Closest papers

Nearest neighbours by meaning across the whole index.

Fault-tolerant Hamiltonian connectivity of Johnson graphs

cs.DM ·2026-09-11 ·Huazhong Lü, Jinhao Liu
theory similarity 0.70
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 Necessary and Sufficient Hall Condition for Hypergraphs

cs.DM math.COcs.DS ·2026-08-10 ·Xiaoyao Huang
theory similarity 0.69
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

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

cs.DM math.CO ·2026-09-30 ·Zehui Shao, Hanxin Jiang
theory similarity 0.66
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.

0.19

The Complexity of Hamiltonian Cycles and Paths with Prescribed Walk Lengths

cs.DS ·2026-10-13 ·Hitendra Kumar, Mathieu Mari, R. B. Sandeep
theory similarity 0.66
Abstract · added acknowledgement

Fix a set $S$ of positive integers. An $S$-Hamiltonian cycle is a cyclic ordering of all vertices of a graph such that each consecutive pair is joined by a walk whose length belongs to $S$. We study the complexity of deciding whether an input graph admits such an ordering, together with the corresponding path variants with prescribed or unrestricted endpoints. We complete the complexity classification for undirected graphs. In particular, we prove NP-completeness for every finite nonempty set of odd lengths, resolving an open problem posed by Amarilli, Lombardo, and Monet (WG 2026). For digraphs, all three problems are NP-complete for every fixed finite nonempty $S$ and admit linear-time algorithms when $S$ is cofinite. For other fixed infinite sets $S$, we establish NP-complete and undecidable cases, with undecidability occurring even when $S$ is recursive.

0.23

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.65
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

Hamiltonian Cycle Construction in Rectangular Grid Graphs with Three-Stacked Triangular Holes

cs.CG ·2026-10-30 ·Cecilia Chen, Dianna Xu
similarity 0.65
Abstract · 19 pages, 21 figures

The Hamiltonian cycle problem is NP-complete for general grid graphs, while several structured classes admit efficient construction algorithms. In this paper, we investigate Hamiltonian cycle construction in rectangular grid graphs containing a three-stacked right-triangular hole. We explore two complementary approaches based on the geometric structure of the hole and the parity properties of rectangular subgraphs. The first approach constructs a Hamiltonian path in the complementary reversed staircase region, extends it into an inner Hamiltonian cycle, and merges it with a cycle in the surrounding graph. The second approach partitions the graph into six rectangular subgraphs and constructs a global Hamiltonian cycle by merging local cycles along compatible boundaries. When odd-sized rectangular subgraphs prevent direct cycle construction, we develop parity-based repartitioning techniques that transform selected configurations into even-sized rectangles. We provide constructions for adjacent and nonadjacent odd-sized configurations and investigate reductions for cases involving multiple odd-sized regions. These results establish a constructive framework for Hamiltonian cycles in grid graphs with staircase-shaped holes and identify the remaining cases requiring further analysis.

0.21

On the Complexity of Extending Prescribed Linear Forests to Hamiltonian Cycles in Hypercubes

cs.CC math.CO ·2026-11-08 ·Huazhong Lü, Tingzeng Wu
theory similarity 0.65
Abstract

Let $Q_n$ be the $n$-dimensional hypercube, and let $P\subseteq E(Q_n)$ be a set of prescribed edges. It is known that, for $n\ge 2$, every such set $P$ with $|P|\leq 2n-3$ whose edges form a linear forest is contained in a Hamiltonian cycle of $Q_n$. This bound is sharp for general linear forests. The computational complexity of deciding whether a prescribed edge set of a hypercube can be extended to a Hamiltonian cycle was posed as an open question by Dvořák [SIAM J. Discrete Math. 19 (2005) 135--144]. We prove that the problem is NP-complete even when the prescribed edges form a spanning linear forest with no isolated vertices. We give a polynomial-time reduction from a restricted 3-SAT problem, using local spanning path-forest gadgets for variables and clauses that are uniformly embedded in the hypercube. The same reduction therefore establishes NP-hardness of two versions of Hamiltonian-cycle extension problems for general prescribed edge sets.

0.19

Perfect Italian Domination on and Near Split Graphs: Algorithms, Hardness, and Approximation

cs.DM ·2026-10-07 ·Anand Babu N B, Ashwin Jacob, Manjusha M S, Renjith P
similarity 0.64
Abstract · Submitted to CALDAM 2027

A perfect Italian dominating function assigns a label from $\{0,1,2\}$ to each vertex so that the labels in the neighborhood of every zero-labeled vertex sum to exactly two. Although the associated decision problem (PID) is NP-complete on chordal graphs, the complexity status on split graphs remains open. We give an $O(n^4)$ time algorithm for split graphs on $n$ vertices. We note that this is in contrast to Roman, Italian, and perfect Roman domination, which are NP-complete on split graphs. We further show that this tractability boundary is tight: PID is NP-hard on graphs at deletion distance one from split graphs. We also provide dichotomy results for PID on restricted extensions of split graphs formed by attaching pendant stars, and establish inapproximability results for the same.

0.09