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

Institutions

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
preprint

Total positive influence domination number of trees

José Manuel Rodríguez, José María Sigarreta, Sayli Sigarreta, Ismael Rios Villamar
Zenodo (CERN European Organization for Nuclear Research)
Advanced Graph Theory Research
preprint

Total positive influence domination number of trees

José Manuel Rodríguez, José María Sigarreta, Sayli Sigarreta, Ismael Rios Villamar
preprint en

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
Universidad Autónoma de Guerrero (MX), Universidad Carlos III de Madrid (ES)
Advanced Graph Theory Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon