Total positive influence domination number of trees
Let $G$ be a graph with no isolated vertex. A set $D\subseteq V(G)$ is a total positive influence dominating set of $G$ if $|N_G(v)\cap D|\geq |N_G(v)\setminus D|$ for every vertex $v\in V(G)$, where $N_G(v)$ represents the open neighborhood of $v$. The total positive influence domination number of $G$, denoted by $\gamma_t^+(G)$, is the minimum cardinality among all total positive influence dominating sets of $G$. In this paper we study this parameter in trees. In particular, we obtain tight lower bounds on $\gamma_t^+(T)$ in terms of the number of leaves and the number of vertices of even degree of a tree $T$, and we characterize the trees attaining them. Moreover, we show that $\gamma_t^+(T)\leq 3n/4$ for every tree $T$ of order $n\geq 3$, and we characterize the trees for which the equality holds. We also obtain tight bounds on $\gamma_t^+(T)$ in terms of the number of leaves, the support vertices and the independence number of $T$. Finally, we show that $\lceil n/2\rceil\leq \gamma_t^+(\overline{T})\leq \lfloor n/2\rfloor+1$ for every tree $T$ of order $n$ different from a star, and as a consequence, we obtain Nordhaus--Gaddum type inequalities for this parameter.
Authors
- José Manuel Rodríguez (ORCID: https://orcid.org/0000-0003-2851-7442)
- José María Sigarreta (ORCID: https://orcid.org/0000-0003-4352-5109)
- Sayli Sigarreta (ORCID: https://orcid.org/0000-0001-7426-1682)
- Ismael Rios Villamar (ORCID: https://orcid.org/0009-0007-5190-7058)
Institutions
- Universidad Autónoma de Guerrero (MX)
- Universidad Carlos III de Madrid (ES)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-10-31
- DOI
- https://doi.org/10.5281/zenodo.23841782
- Primary Topic
- Advanced Graph Theory Research
- Type
- preprint