Claw-Free and Line Graph Edge Deletion on Block Graphs

@misc{adak2026clawfree,
  title = {{Claw-Free and Line Graph Edge Deletion on Block Graphs}},
  author = {Rajat Adak},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.20510},
  eprint = {2610.20510},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.20510},
  note = {CC BY 4.0},
}

TY  - UNPB
TI  - Claw-Free and Line Graph Edge Deletion on Block Graphs
AU  - Rajat Adak
PY  - 2026
DA  - 2026/10/14
PB  - arXiv
DO  - 10.48550/arxiv.2610.20510
UR  - https://arxiv.org/abs/2610.20510
AB  - Edge deletion problems ask for the fewest edges whose deletion gives a graph with a specified property. We study two such problems on block graphs. First making the graph claw-free, and second making it a line graph. Since every line graph is claw-free, the second problem is at least as difficult as the first. We show that on block graphs the two optimum values are always equal, and both are attained by the line graph of a forest. The main step is a completion argument, in which starting from any claw-free solution, we put back edges to get some nice structure inside each block still maintaining the claw-free property. This reduces both edge-deletion problems to the same problem of selecting vertices within the blocks of the input graph. We solve it by dynamic programming in O(n+m) time, which also produces an optimal deletion set and a forest whose line graph is what remains after the completion argument. We also extend the method to K_1,r+1-free edge deletion for every fixed r.
ER  -