Arpan Sadhukhan

activity

20242026

collaborators

6 papers

math.CO2026

Exact-Distance Domination in Grid Graphs

Sandip Das, Sweta Das, Arpan Sadhukhan

Let $G_{n}$ be the $n \times n$ square grid, and let $k \geq 2$ . A set $D \subseteq V (G_{n})$ is an \emph{exact-distance $k$ -dominating set} if every vertex $v \in V (G_{n}) ∖ D$ has a…

math.CO2026

A proof of Seymour's second neighborhood conjecture for oriented graphs with minimum out-degree equal to 7

Arpan Sadhukhan, R. B. Sandeep, Sagnik Sen

We prove Seymour's second neighborhood conjecture on oriented graphs whose minimum out-degree is equal to $7$ . This gives, to our knowledge, the first improvement of the minimum ou…

math.CO2025

The structure of $I^ (1, 2, 2)$ -free tournaments

Seokbeom Kim, Taite LaGrange, Mathieu RundstrÃ¶m +2

We extend the list of tournaments $S$ for which the complete structural description for tournaments excluding $S$ as a subtournament is known. Specifically, let $I^ (1, 2, 2)$ be a…

cs.DS2024

Stable Approximation Algorithms for Dominating Set and Independent Set

Mark de Berg, Arpan Sadhukhan, Frits Spieksma

We study the Dominating set problem and Independent Set Problem for dynamic graphs in the vertex-arrival model. We say that a dynamic algorithm for one of these problems is $k$ -sta…

cs.CG2024

On Stable Approximation Algorithms for Geometric Coverage Problems

Mark de Berg, Arpan Sadhukhan

Let $P$ be a set of points in the plane and let $m$ be an integer. The goal of Max Cover by Unit Disks problem is to place $m$ unit disks whose union covers the maximum number of p…

math.CO2024

Shift Graphs, Chromatic Number and Acyclic One-Path Orientations