Metraipolis › archive › dc_3beafa5810a3

Claw-Free and Line Graph Edge Deletion on Block Graphs — arXiv:2610.20510

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.20510
License (as archived)
CC0-1.0
Archived
2026-10-15T21:52:55.647Z
SHA-256 of the archived text
c0492a6dfef41eab9ff3189478863680be64dae2e5a17cda5aa4c4a351677a9e
Stable URL of this page
https://metraipolis.com/documento/dc_3beafa5810a3

How to cite

Claw-Free and Line Graph Edge Deletion on Block Graphs — arXiv:2610.20510 — arXiv (en), https://arxiv.org/abs/2610.20510 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_3beafa5810a3 (Metraipolis archive dc_3beafa5810a3, sha256 c0492a6dfef41eab9ff3189478863680be64dae2e5a17cda5aa4c4a351677a9e)
BibTeX
@misc{dc3beafa5810a3,
  title = {Claw-Free and Line Graph Edge Deletion on Block Graphs — arXiv:2610.20510},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.20510},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_3beafa5810a3; sha256 c0492a6dfef41eab9ff3189478863680be64dae2e5a17cda5aa4c4a351677a9e},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.20510. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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$.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Discrete Mathematics (cs.DM); Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2610.20510 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-15T21:37:14.457Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).