On Well-VE-Dominated Graphs
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917144596316160 |
|---|---|
| author | Büyükçolak, Yasemin |
| author_facet | Büyükçolak, Yasemin |
| contents | Given a graph G=(V, E), a vertex is said to ve-dominate an edge if it is either incident with the edge or adjacent to one of its endpoints. A set of vertices is a ve-dominating set if it ve-dominates every edge of the graph. We introduce the class of well-ve-dominated graphs, defined as graphs in which all minimal ve-dominating sets have the same cardinality. After establishing several general structural properties of well-ve-dominated graphs, we show that recognizing whether a graph belongs to this class is co--NP--complete, highlighting the computational difficulty of the problem. Our main result is a complete structural characterization of well-ve-dominated trees, which yields a simple linear-time recognition algorithm and a constructive description of all trees in this class. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_12231 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On Well-VE-Dominated Graphs Büyükçolak, Yasemin Combinatorics Discrete Mathematics 05C69, 05C75 Given a graph G=(V, E), a vertex is said to ve-dominate an edge if it is either incident with the edge or adjacent to one of its endpoints. A set of vertices is a ve-dominating set if it ve-dominates every edge of the graph. We introduce the class of well-ve-dominated graphs, defined as graphs in which all minimal ve-dominating sets have the same cardinality. After establishing several general structural properties of well-ve-dominated graphs, we show that recognizing whether a graph belongs to this class is co--NP--complete, highlighting the computational difficulty of the problem. Our main result is a complete structural characterization of well-ve-dominated trees, which yields a simple linear-time recognition algorithm and a constructive description of all trees in this class. |
| title | On Well-VE-Dominated Graphs |
| topic | Combinatorics Discrete Mathematics 05C69, 05C75 |
| url | https://arxiv.org/abs/2512.12231 |