Characterization of Well-Totally Dominated Trees

arXiv (Cornell University) 2026 Preprint Open access

Read full text
Authors: Jounglag Lim, James Gossell, Keri Ann Sather-Wagstaff, Devin Adams, Suzanna Castro-Tarabulsi, Aayahna Herbert, Vi Anh Nguyen, Yifan Qian, Matthew Schaller, Zoe Zhou, Yuyang Zhuo
DOI: 10.48550/arxiv.2602.13956
Cited by: 0

Abstract

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.

Fields of Study & Subjects

Advanced Graph Theory Research Graph Labeling and Dimension Problems Complexity and Algorithms in Graphs

Publication details

Journal / source
arXiv (Cornell University)
Publication date
15 February 2026
Language
EN
Document type
Preprint