7 papers · 1 filter
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…
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 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…