Saved in:
| Main Authors: | , , , , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2602.13956 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918339554574336 |
|---|---|
| author | Lim, Jounglag Gossell, James Sather-Wagstaff, Keri Ann Adams, Devin Castro-Tarabulsi, Suzanna Herbert, Aayahna Nguyen, Vi Anh Qian, Yifan Schaller, Matthew Zhou, Zoe Zhuo, Yuyang |
| author_facet | Lim, Jounglag Gossell, James Sather-Wagstaff, Keri Ann Adams, Devin Castro-Tarabulsi, Suzanna Herbert, Aayahna Nguyen, Vi Anh Qian, Yifan Schaller, Matthew Zhou, Zoe Zhuo, Yuyang |
| contents | Let $G$ be a graph with no isolated vertices. A set of vertices $S$ is a total dominating set (TDS) if every vertex in $G$ is adjacent to at least one vertex in $S$. We say $G$ is well-totally dominated (WTD) if every minimal TDS has the same size. In this paper, we present two characterizations of well-totally dominated trees, one being descriptive and the other being constructive. In particular, our characterizations imply that it takes only polynomial time to verify whether a given tree is WTD. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_13956 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Characterization of Well-Totally Dominated Trees Lim, Jounglag Gossell, James Sather-Wagstaff, Keri Ann Adams, Devin Castro-Tarabulsi, Suzanna Herbert, Aayahna Nguyen, Vi Anh Qian, Yifan Schaller, Matthew Zhou, Zoe Zhuo, Yuyang Combinatorics 05C69 (Primary), 05C05, 05C75 Let $G$ be a graph with no isolated vertices. A set of vertices $S$ is a total dominating set (TDS) if every vertex in $G$ is adjacent to at least one vertex in $S$. We say $G$ is well-totally dominated (WTD) if every minimal TDS has the same size. In this paper, we present two characterizations of well-totally dominated trees, one being descriptive and the other being constructive. In particular, our characterizations imply that it takes only polynomial time to verify whether a given tree is WTD. |
| title | Characterization of Well-Totally Dominated Trees |
| topic | Combinatorics 05C69 (Primary), 05C05, 05C75 |
| url | https://arxiv.org/abs/2602.13956 |