7 papers · 1 filter
Hardness of Burning Number Problem on Regular Graphs
Dhanyamol Antony, L. Sunil Chandran, Anita Das +3
The Burning Number Problem (BNP) models the spread of information or contagion in a network through a discrete-time process on a graph. At each step, one new vertex is selected as…
Parameterized algorithms for -Inversion
Dhanyamol Antony, L. Sunil Chandran, Dalu Jacob +1
Inversion of a directed graph with respect to a vertex subset is the directed graph obtained from by reversing the direction of every arc whose endpoints both lie in $Y…
Switching Classes: Characterization and Computation
Dhanyamol Antony, Yixin Cao, Sagartanu Pal +1
In a graph, the switching operation reverses adjacencies between a subset of vertices and the others. For a hereditary graph class , we are concerned with the maximum…
Total Domination, Separated Clusters, CD-Coloring: Algorithms and Hardness
Dhanyamol Antony, L. Sunil Chandran, Ankit Gayen +2
Domination and coloring are two classic problems in graph theory. The major focus of this paper is the CD-COLORING problem which combines the flavours of domination and colouring.…
Algorithms for subgraph complementation to some classes of graphs
Dhanyamol Antony, Sagartanu Pal, R. B. Sandeep
For a class of graphs, the objective of \textsc{Subgraph Complementation to} is to find whether there exists a subset of vertices of the input graph…
Cutting a tree with Subgraph Complementation is hard, except for some small trees
Dhanyamol Antony, Sagartanu Pal, R. B. Sandeep +1
For a graph property , Subgraph Complementation to is the problem to find whether there is a subset of vertices of the input graph such that modifying by complem…
On subgraph complementation to H-free graphs
Dhanyamol Antony, Jay Garchar, Sagartanu Pal +3
For a class of graphs, the problem SUBGRAPH COMPLEMENT TO asks whether one can find a subset of vertices of the input graph such that complement…