13 papers · 1 filter
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…
Almost Empty Monochromatic Triangles With Many Colors
Bhaswar B. Bhattacharya, Sandip Das, Sk Samim Islam +2
Given integers and , let denote the least integer such that every set of at least points in the plane, no three on a line…
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…
Broadcast Domination Number is at Most Twice the Multipacking Number
Sk Samim Islam
For a graph with a vertex set and an edge set , a function is called a \emph{broadcast} on . For e…
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…
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…
On the complexity of Multipacking
Sandip Das, Sk Samim Islam, Daniel Lokshtanov
A \emph{multipacking} in an undirected graph is a set such that for every vertex and for every integer , the ball of radius around $v…
Multipacking on graphs and Euclidean metric space
Sk Samim Islam
A \emph{multipacking} in an undirected graph is a set such that for every vertex and for every integer , the ball of radius around…
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…