18 papers · 2 filters
Sharp connectivity thresholds for mixed rigidity packings and improved bounds for highly connected orientations of graphs
Hanzhi Bai, Jørgen Bang-Jensen, Jin Yan
Garamvölgyi, Jordán, Király and Villányi [{{\bf Forum Math. Pi} \textbf{13} (2025), Paper No.~e11}] posed two sharp connectivity conjectures for packing rigid spanning subgraphs: o…
Hitting Maximum Independent Sets in Dense and Highly Connected Graphs
Hanzhi Bai, Yufei Chang, Jin Yan
For a graph , let be the minimum cardinality of a vertex set meeting every maximum independent set of . We establish two complementary reduction principles for the Bol…
An Exact Dominant Degree Condition for Transitive Tournament Factors in Digraphs
Yufei Chang, Shuo Wei, Jin Yan
Let , let denote the transitive tournament on vertices, and write . We prove that if and an -vertex digraph s…
Paths with Prescribed Endpoints in Semicomplete and Locally Semicomplete Digraphs
Hanzhi Bai, Jin Yan, Jia Zhou
We study two open path problems with prescribed endpoints posed by Bang-Jensen and Gutin. The first asks for a longest -path in a semicomplete digraph. The second asks wheth…
A Chvátal--Erdős type condition for supereulerian digraphs with
Zirui Liu, Jin Yan, Jia Zhou
A digraph is \textbf{supereulerian} if it contains a spanning closed trail. Let denote the maximum cardinality of a vertex set inducing no 2-cycle. In this paper, we chara…
Packing and Covering Cycles Through Prescribed Vertices
Hanzhi Bai, Jin Yan
Let be a finite simple graph and let . We prove that the minimum number of vertices meeting every cycle that intersects is at most the maximum number of ve…