Open Research Index

Counting perfect edge dominating sets: extremal results and linear-time algorithms

Luciano N. Grippo, Min Chih Lin, Verónica Moyano, Camilo Vera

arXivarxiv/2607.03894Jul 4, 2026math.COscore 0

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.

SourceJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2607.03894
curl -X POST /api/v1/records/arxiv/2607.03894/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.03894/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'