{"id":"arxiv/2607.03894","url":"https://arxiv.org/abs/2607.03894","tags":["math.CO"],"score":0,"title":"Counting perfect edge dominating sets: extremal results and linear-time algorithms","domain":"math.CO","source":"arxiv","authors":["Luciano N. Grippo","Min Chih Lin","Verónica Moyano","Camilo Vera"],"reviews":0,"subject":"math.CO","summary":"An edge of a graph \\emph{dominates} itself and each edge adjacent to it. A \\emph{perfect edge dominating set} is a subset of edges such that each edge outside the subset is dominated by exactly one edge of the subset. In this article, we characterize the extremal graphs on $n$ vertices in the classes of trees, forests, and chordal graphs with respect to the number of perfect edge dominating sets. Moreover, we derive linear-time algorithms for counting perfect edge dominating sets and for counting dominating induced matchings in generalized series-parallel graphs and chordal graphs.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-04","reactions":{}}