Domination in Diameter-Two Graphs and the 2-Club Cluster Vertex Deletion Parameter
<|reference_start|>Domination in Diameter-Two Graphs and the 2-Club Cluster Vertex Deletion Parameter: The s-club cluster vertex deletion number of a graph, or sccvd, is the minimum number of vertices whose deletion results in a disjoint union of s-clubs, or graphs whose diameter is bounded above by s. We launch a study of several domination problems on diameter-two graphs, or 2-clubs, and study their parameterized complexity with respect to the 2ccvd number as main parameter. We further propose to explore the class of problems that become solvable in sub-exponential time when the running time is independent of some input parameter. Hardness of problems for this class depends on the Exponential-Time Hypothesis. We give examples of problems that are in the proposed class and problems that are hard for it.<|reference_end|>
@article{abu-khzam2024domination,
    title={Domination in Diameter-Two Graphs and the 2-Club Cluster Vertex Deletion
  Parameter},
    author={Faisal N. Abu-Khzam and Lucas Isenmann},
    journal={arXiv preprint arXiv:2408.08418},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.08418},
    primaryClass={cs.CC}
}