{"id":"arxiv/2605.10487","url":"https://arxiv.org/abs/2605.10487","tags":["math.CO"],"score":0,"title":"Algorithm for finding vertex-edge domination number on graphs with bounded treewidth and related problems on planar graphs","domain":"math.CO","source":"arxiv","authors":["Yichen Wang","Haixiang Zhang","Mei Lu"],"reviews":0,"subject":"math.CO","summary":"Given a graph $G=(V,E)$, a vertex $u \\in V$ {\\em ve-dominates} all edges incident to any vertex of $N_G[u]$. A set $S \\subseteq V$ is a {\\em ve-dominating set} if for all edges $e\\in E$, there exists a vertex $u\\in S$ such that $u$ ve-dominates $e$. The minimum cardinality among all ve-dominating sets is known as the \\textit{vertex-edge domination number} (or simply ve-domination number) and denoted by $γ_{ve}(G)$. Finding a minimum ve-dominating set was proved to be NP-complete. Restricted to trees, the problem admits a linear-time algorithm. Treewidth is a commonly used parameter for…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-05-11","reactions":{}}