7 papers
Maximum Edge Open Packing on AT-Free, Chordal, and Convex Bipartite Graphs
Gautam K. Das, Kamal Santra
An edge open packing is a set of edges whose endpoints induce a disjoint union of stars. We study the problem of finding a maximum edge open packing in AT-free, chordal, and convex…
Roman Domination on Circular-Convex, Triad-Convex Bipartite Graphs and -Tidy Graphs
Gautam K. Das, Kamal Santra
The Roman Domination Problem (RDP) on a graph \(G=(V,E)\) asks for a labeling function \(f:V\rightarrow\{0,1,2\}\) such that every vertex assigned value \(0\) is adjacent to a vert…
Maximum Edge Open Packing in Permutation, Interval, and Well-Partitioned Chordal Graphs
Gautam K. Das, Kamal Santra
Edge open packing is a relaxation of induced matching in which the selected edges may induce disjoint stars. We study the \textsc{Maximum Edge Open Packing} problem on permutation…
Roman-Type Domination on Convex and Chordal Bipartite Graphs: Algorithms and Hardness
Gautam K. Das, Kamal Santra
Roman domination and its variants form an important family of domination-type graph parameters motivated by protection, fault tolerance, and resource allocation. A Roman dominating…
Roman domination on subclasses of bipartite graphs
Gautam K. Das, Sasmita Rout, Kamal Santra
The Roman Domination Problem (RDP) on a simple, finite, undirected graph \(G=(V,E)\) asks for a labeling function \(f:V\rightarrow\{0,1,2\}\) such that every vertex assigned value…
(Independent) Roman Domination Parameterized by Distance to Cluster
Pradeesha Ashok, Gautam K. Das, Arti Pandey +2
Given a graph , a function is said to be a \emph{Roman Dominating function} (RDF) if for every with , there exists a vertex …
Improved Total Domination and Total Roman Domination in Unit Disk Graphs
Sasmita Rout, Gautam Kumar Das
Let be a simple undirected graph with no isolated vertex. A set is a total dominating set of if is a dominating set, and the set…