CS Paper Radar

Distance-$2$ isolation of connected graphs

Peter Borg, Pawaton Kaemawichanurat

cs.DM math.CO ·submitted 2026-11-14 12:02 UTC · v1
hot direction

Abstract

If $\mathcal{F}$ is a set of graphs and $F$ is a copy of a graph in $\mathcal{F}$, then we call $F$ an $\mathcal{F}$-graph. Let $G$ be a connected $n$-vertex graph. For a subset $D$ of the vertex set $V(G)$, let $N^2[D]$ denote the second closed neighbourhood of $D$. Let $ι_2(G, \mathcal{F})$ denote the size of a smallest subset $D$ of $V(G)$ such that $N^2[D]$ intersects the $\mathcal{F}$-graphs contained by $G$ (equivalently, $G - N^2[G]$ contains no $\mathcal{F}$-graph). For $k \geq 0$, let $\mathcal{E}_k$ denote the set of connected graphs that have at least $k$ edges (and at least one vertex if $k = 0$). By a well-known result of Meir and Moon, $ι_2(G, \mathcal{E}_0) \leq n/3$ if $n \geq 3$. We show that $ι_2(G, \mathcal{E}_1) \leq n/4$ if $n \neq 2$, $n \neq 3$ and $G$ is not a $7$-cycle. Hua and Liu recently showed that if $G$ is not a $4$-vertex path or a $4$-cycle or a $9$-cycle, then there exists a subset $D$ of $V(G)$ such that $|D| \leq n/5$ and each component of $G-N^2[D]$ has a universal vertex. We strengthen this result by showing that $ι_2(G, \mathcal{E}_2) \leq n/5$ if $n \neq 3$, $n \neq 4$ and $G$ is not an $8$-cycle or one of five $9$-vertex graphs. It follows that $ι_2(G, \mathcal{E}_3) \leq n/5$ if $G$ is not a $3$-cycle or a $4$-vertex graph or a $9$-cycle. This also implies the result of Hua and Liu, and that if $\mathcal{C}$ is the set of cycles, then $ι_2(G, \mathcal{C}) \leq n/5$ unless $G$ is a $3$-cycle or a $4$-vertex graph containing a cycle. All these bounds are sharp.

Comment
15 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Mutual-visibility k-colouring is NP-complete for every fixed diameter

cs.DM cs.CCmath.CO ·2026-10-31 ·Siddhesh Chaubal
similarity 0.62
Abstract · 9 pages, 1 figure. v2: extended to any fixed number k of colours; new title

A mutual-visibility set in a graph G is a set S of vertices such that any two vertices of S are connected by a shortest path with no internal vertex in S, and the mutual-visibility chromatic number $χ_μ(G)$ is the minimum number of mutual-visibility sets needed to partition V(G). Babu, Di Stefano and Lakshmanan showed that it is NP-complete to decide whether $χ_μ(G)\le 2$ for graphs of diameter four. We show that the problem remains NP-complete for graphs of diameter d, for every fixed $d\ge2$; diameter two is the smallest diameter for which the problem is non-trivial. More generally, for all fixed $k\ge2$ and $d\ge2$, it is NP-complete to decide whether $χ_μ(G)\le k$ for graphs of diameter d. The proof rests on a reformulation of $χ_μ(G)\le 2$ for diameter-two graphs as the 2-colourability of an associated hypergraph, and on a reduction from 2-colourability of 3-uniform hypergraphs without short cycles.

0.24

Exploring Minimal Blocking Sets for Kernelization Lower Bounds for $\mathcal{F}$-Minor Deletion

cs.DS cs.CC ·2026-10-13 ·Ahmed Ghazy, Jakob Greilhuber, Tim A. Hartmann
similarity 0.61
Abstract · Full version of an IPEC 2026 contribution. Abstract has been shortened for arXiv

For Vertex Cover, a minimal blocking set of a graph $G$ is an inclusion-wise minimal vertex set contained in no minimum vertex cover of $G$. Bougeret et al. [SIDMA 2022] showed that, for all minor-closed graph classes $\mathcal{G}$, Vertex Cover has a polynomial kernel parameterized by the distance to $\mathcal{G}$ if and only if $\mathcal{G}$ has bounded minimal blocking sets. In this work, we explore how far this connection between minimal blocking sets and kernelization extends to $\mathcal{F}$-Minor Deletion parameterized by the deletion distance to $\mathcal{G}$. A minimal $\mathcal{F}$-blocking set of $G$ is a minimal vertex set not contained in any optimal $\mathcal{F}$-Minor Deletion solution of $G$. For connected families $\mathcal{F}$, we show that if some graph class $\mathcal{G}$ closed under disjoint union has unbounded minimal $\mathcal{F}$-blocking sets, then $\mathcal{F}$-Minor Deletion parameterized by the deletion distance to $\mathcal{G}$ has no polynomial kernel. This generalizes a result of Hols et al. [SIDMA 2022] for Vertex Cover. We then show that this criterion does not capture all kernelization lower bounds for $\mathcal{F}$-Minor Deletion, even for minor-closed graph classes. Motivated by the work of Dekker and Jansen [Discrete Appl. Math. 2024], we study the more general notion of extended $\mathcal{F}$-blocking sets and the kernelization lower bounds they yield. For every fixed integer $η\geq 1$, Pw-$η$ Deletion is the problem of deleting at most $k$ vertices to reduce the pathwidth to at most $η$. We show that it has no polynomial kernel parameterized by the distance to graphs with pathwidth at most $η+1$. Moreover, for connected families $\mathcal{F}$, we show that $\mathcal{F}$-Minor Deletion parameterized by the distance to graphs with pathwidth at most $\max_{F\in\mathcal{F}} pw(F)+1$ has no polynomial kernel.

0.26

Diameter-two graphs whose mutual-visibility chromatic number equals their chromatic number

cs.DM math.CO ·2026-10-29 ·Siddhesh Chaubal
similarity 0.60
Abstract · 8 pages, 3 figures. Submitted to Aequationes Mathematicae

A set $S$ of vertices of a graph $G$ is a mutual-visibility set if every pair of vertices of $S$ is joined by a shortest path whose internal vertices avoid $S$, and the mutual-visibility chromatic number $χ_μ(G)$ is the least number of mutual-visibility sets into which $V(G)$ can be partitioned. Klavžar, Kuziak, Valenzuela Tripodoro and Yero (2025) proved that $χ_μ(G)\leχ(G)$ whenever $G$ has diameter two, observed that equality holds for complete bipartite graphs, and asked whether there are any other diameter-two graphs attaining equality. We answer this question in the affirmative. We construct a graph $G_{11}$ of order 11 and diameter two with $χ_μ(G_{11})=χ(G_{11})=3$, and an infinite family of such graphs obtained from $G_{11}$ by replacing one vertex with pairwise non-adjacent copies of it.

0.56

On the Parameterized Complexity of Conflict-Free Edge Cut in Undirected Graphs

cs.DS cs.DM ·2026-10-05 ·Sourav Das, Ashwin Jacob, Arpit Kumar, Diptapriyo Majumdar
theory similarity 0.60
Abstract · 26 pages

In this paper, we study CONFLICT-FREE EDGE CUT (CF-CUT), which is a recently introduced conflict-free version of the MIN-CUT problem that asks to find the minimum number of edges to disconnect a connected graph. The CF-CUT takes as input a connected undirected graph G = (V, E), a conflict graph $\widehat{G}$ such that $E(G) = V(\widehat{G})$, and the objective is to decide whether there exists $F \subseteq E(G)$ such that $G - F$ is disconnected and $F$ is an independent set in $\widehat{G}$. Rauch et. al. [IPL-2025] proved that CF-CUT is NP-Complete and also provided some results on the parameterized complexity of CF-CUT. A related variant MIN CONFLICT-FREE EDGE CUT (MIN-CF-CUT) takes a connected graph $G$, a conflict graph $\widehat{G}$ such that $V(\widehat{G}) = E(G)$, and an integer $k$ as input and asks if there is a set $F$ of at most $k$ edges such that $G - F$ is disconnected and $F$ is an independent set in $\widehat{G}$. In this paper, we extend the work of Rauch et al. [IPL-2025] and provide a systematic study on the CF-CUT and MIN-CF-CUT from the perspective of parameterized complexity and polynomial kernelization. We prove that CF-CUT is NP-hard when the dissociation number of the input graph is at most two. We also complement it by proving that CF-CUT is poly-time solvable when the dissociation number of an input graph is at most one. Additionally, for MIN-CF-CUT, we consider both solution size and various structural parameters of the input graph as parameters, and provide fixed-parameter tractability and W[1]-hardness results when the conflict graph is restricted to various graph classes. We also prove that unless NP $\subseteq$ coNP/poly, MIN-CF-CUT admits no polynomial kernel when parameterized by the vertex cover number of the input graph; and also when parameterized by the sum of the solution size and the vertex integrity of the input graph.

0.44

An approximate cactus-decomposition for vertex-connectivity

cs.DM math.CO ·2026-11-01 ·Romain Bourneuf, Johannes Carmesin, Jan Kurkofka, Tim Planken
theory similarity 0.59
Abstract

The classical cactus theorem of Dinitz, Karzanov and Lomonosov from 1976 states that the minimum edge-cuts of a connected graph are displayed by a cactus. For vertex-separations, Tutte's theorem gives an exact cactus-decomposition for connectivity $2$, but exact cactus-decompositions fail for higher connectivity. Extending earlier approximate cactus-decomposition results for connectivities $3$ and $4$ by Carmesin and Kurkofka [FOCS 2023] and Kurkofka and Planken [SODA 2026] to all connectivities, we prove that for every $k\in\mathbb{N}$ there is a constant $d=d(k)$ such that every $k$-connected graph $G$ admits a cactus-decomposition displaying $k$-separations such that every $k$-separation of $G$ has edit-distance at most $d$ to a displayed separation. Our proof develops tools that may be useful beyond this result. The first is a three-dimensional version of the classical corner-diagram method, which we use to show that triples of crossing $k$-separations have a controlled two-dimensional behaviour. The second is a covering-space approach for studying local crossing patterns from a global perspective. Third, we advance the theory of flowers, which originated in matroid theory.

0.30

Large diameter for $(Δ+2)$-colouring reconfiguration

cs.DM math.CO ·2026-11-12 ·Wouter Cames van Batenburg
similarity 0.58
Abstract · 15 pages, 2 figures

Given a graph $G$ and an integer $k$, the reconfiguration graph $\mathcal{R}_{k}(G)$ has the proper $k$-colourings of $G$ for vertices, two of which are adjacent if and only if they differ on precisely one vertex of $G$. In $2022$, Cambie, Cranston and the author proved that the diameter of $\mathcal{R}_{Δ+2}(G)$ is at most $n+2μ$, and put forth a collection of conjectures that in its strongest and most beautiful form would imply that the diameter of $\mathcal{R}_{Δ+2}(G)$ is precisely equal to $n + μ$, for every graph $G$ with $n$ vertices, matching number $μ$ and maximum degree $Δ$. Here we disprove most of those conjectures. Our constructions have reconfiguration diameter at least $n+\frac{3}{2}μ-2$. We also provide counterexamples that are $Δ$-regular, we show that every graph has reconfiguration diameter at least $n+\frac{1}{2} μ$, and we advertise an extension to hypergraphs. It is now much more mysterious how the diameter behaves, so we propose a number of open problems.

0.25

Isolation of $k$-cliques in uniform hypergraphs

cs.DM math.CO ·2026-11-12 ·Mattea Baluci, Peter Borg
theory similarity 0.58
Abstract · 13 pages

A copy of a hypergraph $F$ is called an $F$-copy. For any integers $k$ and $r$ with $2 \leq r \leq k$, let $K_k^r$ denote the complete $r$-uniform hypergraph whose vertex set is $[k] = \{1, 2, \dots, k\}$ (that is, the edges of $K_k^r$ are the $r$-element subsets of $[k]$). Given an $r$-uniform $m$-edge hypergraph $H$, the $K_k^r$-isolation number of $H$, denoted by $ι(H, K_k^r)$, is the size of a smallest subset $D$ of the vertex set of $H$ such that the closed neighbourhood $N[D]$ of $D$ intersects the vertex sets of the $K_k^r$-copies contained by $H$ (equivalently, $H-N[D]$ contains no $K_k^r$-copy). We prove that if $H$ is connected and not a $K_k^r$-copy, then $$ι(H, K^r_k) \le \left \lfloor \frac{(r-1)m + 1}{(r-1)(\binom{k}{r}+1) + 1} \right \rfloor.$$ The bound is best possible. This is a solution to a problem of Li, Zhang and Ye. We also provide an alternative proof for $r < k$. Both proofs introduce new ideas for establishing bounds on isolation parameters.

0.26

Sharp bounds and extremal structure of minimally strongly $k$-connected digraphs

cs.DM math.CO ·2026-10-10 ·Junran Yu, Gregory Gutin, Hong-Jian Lai, Xiaoyan Zhang
theory similarity 0.58
Abstract

Let $D$ be a finite simple minimally strongly $k$-connected digraph, where $k\ge 2$, and let $n=|V(D)|$. Mader proved in 1985 that $|A(D)|\le 2k(n-k)$ for all sufficiently large $n$, with equality if and only if $D\cong \overleftrightarrow{K}_{k,n-k}$ (JCTB 1985). We prove that this bound holds whenever $n\ge 3k-1$ and that the order threshold $3k-1$ is best possible. Moreover, if $n\ge 3k$, then equality holds if and only if $D\cong \overleftrightarrow{K}_{k,n-k}$. The threshold $3k$ is also best possible. These results resolve the conjecture of Mader in (JCTB 1985).

0.21