Fix an integer $r\ge 3$. Let $K_r$ denote the complete graph on $r$ vertices and $t_{r-1}(n)$ the Tur\'an number for $K_r$. For each integer $k$ satisfying $0\le k \le \binom{n}{2}-t_{r-1}(n)$, $\rev{\phi_r(n,k)}$ denotes the minimum, over all $n$-vertex graphs with $t_{r-1}(n)+k$ edges, of the maximum size of a $K_r$-...
Garamv\"olgyi, Jord\'an, Kir\'aly and Vill\'anyi [{{\bf Forum Math. Pi} \textbf{13} (2025), Paper No.~e11}] posed two sharp connectivity conjectures for packing rigid spanning subgraphs: one for the equal-dimensional case and the other for the packing of a $d$-rigid spanning subgraph with a spanning tree. We prove a un...
Han-Zhi Bai, Jørgen Bang-Jensen, Jin Yan· 0 citations
Let $G$ be a finite simple graph and let $S\subseteq V(G)$. We prove that the minimum number of vertices meeting every cycle that intersects $S$ is at most the maximum number of vertices of $S$ covered by a collection of vertex-disjoint cycles. This answers a question posed by Bowler, Ghorbani, Gut, Jacobs, and Reich [...
For a graph $G$, let $h(G)$ be the minimum cardinality of a vertex set meeting every maximum independent set of $G$. We establish two complementary reduction principles for the Bollob\'as--Erd\H{o}s--Tuza conjecture: the conjecture for arbitrary graphs is equivalent to its restriction to regular graphs of any fixed pos...
Han-Zhi Bai, Yu-jeong Chang, Jin Yan· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
