12 papers
Almost Empty Monochromatic Polygons in Planar Point Sets
Bhaswar B. Bhattacharya, Sandip Das, Sk Samim Islam +2
For integers , , and , let denote the smallest integer such that any set of at least points in th…
Strong Edge Colouring of Disk Graphs: A 6-Approximation and an Improved Unit-Disk Bound
Sandip Das, Sk Samim Islam, Aashirwad Mohapatra +2
A strong edge colouring of a graph is an edge colouring in which every colour class is an induced matching. The minimum number of colours is the strong chromatic index $χ'_s(G)…
Solving Vertex Integrity Faster than
Sandip Das, Sweta Das, Sk Samim Islam +3
Vertex Integrity is a classical graph parameter measuring the vulnerability of a network to vertex failures. We settle two fundamental questions concerning its exact exponential co…
Large Planar Point Sets Contain 4 Collinear Points or Almost 7-Cliques, and Related Results
Bhaswar B. Bhattacharya, Sandip Das, Sk Samim Islam +2
We prove that every sufficiently large finite planar point set contains either four collinear points or seven points with at most one non-visible pair. More generally, we show that…
An Improved Upper Bound for the Turán Number of the Hexagon
Sandip Das, Sk Samim Islam, Aashirwad Mohapatra +1
For a graph , the Turán number is the maximum number of edges in an -vertex graph containing no copy of . Determining the Turán numbers of even cy…
Minimum eccentricity shortest paths of -minor-free graphs
Dibyayan Chakraborty, Sandip Das, Sk Samim Islam +2
Given a simple, undirected, and unweighted graph , and an integer , the objective of the \textsc{Minimum Eccentricity Shortest Path (MESP)} is to decide whether there exists…
Exact-Distance Domination in Grid Graphs
Sandip Das, Sweta Das, Arpan Sadhukhan
Let be the square grid, and let . A set is an \emph{exact-distance -dominating set} if every vertex has a…
On the Complexity of Hop Domination and 2-Step Domination in Graph Classes
Sandip Das, Sweta Das, Sk Samim Islam
The domination problem is a well-studied problem in graph theory. In this paper, we study two natural variants: the hop domination problem and the -step domination problem. Let…
Parameterized complexity of -Hop, -Step, and -Hop Roman Domination
Sandip Das, Sweta Das, Sk Samim Islam
The \textsc{Dominating Set} problem is a classical and extensively studied topic in graph theory and theoretical computer science. In this paper, we examine the algorithmic complex…
Exact Algorithms for Resource Reallocation Under Budgetary Constraints
Arun Kumar Das, Sandip Das, Sweta Das +2
Efficient resource (re-)allocation is a critical challenge in optimizing productivity and sustainability within multi-party supply networks. In this work, we introduce the \textsc{…
On the Number of Almost Empty Monochromatic Triangles
Bhaswar B. Bhattacharya, Sandip Das, Sk Samim Islam +3
In this paper, we consider the problem of counting almost empty monochromatic triangles in colored planar point sets, that is, triangles whose vertices are all assigned the same co…
Growth Rate of the Number of Empty Triangles in the Plane
Bhaswar B. Bhattacharya, Sandip Das, Sk Samim Islam +1
Given a set of points in the plane, in general position, denote by the number of empty triangles with vertices in . In this paper we investigate by how much $N_…