note on total co-independent domination in trees

A set $D$ of vertices of a graph $G$ is a total dominating set if every vertex of $G$ is adjacent to at least one vertex in $D$. The total dominating set $D$ is called a total co-independent dominating set if $V(G)\setminus D$ is an independent set and has at least one vertex. The minimum cardinality of any total co-independent dominating set is denoted by $\gamma_{t,coi}(G)$. In this paper, we show that, for any tree $T$ of order $n$ and diameter at least three, $n-\beta(T)\leq \gamma_{t,coi}(T)\leq n-|L(T)|$ where $\beta(T)$ is the maximum cardinality of any independent set and $L(T)$ is the set of leaves of $T$. We also characterize the families of trees attaining the extremal bounds above and show that the differences between the value of $\gamma_{t,coi}(T)$ and these bounds can be arbitrarily large for some classes of trees.

Authors

Institutions

Publication Details

Journal
Contributions to Discrete Mathematics
Published
2024-09-23
DOI
https://doi.org/10.55016/ojs/cdm.v19i3.75096
Citations
4
Primary Topic
Advanced Graph Theory Research
Type
article
Field-Weighted Citation Impact
1.08

Funders

Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

note on total co-independent domination in trees

Abel Cabrera Martínez, José M. Sigarreta, Frank A. Hernández Mira, Ismael G. Yero
4 citations
Contributions to Discrete Mathematics
Advanced Graph Theory Research
1.08
article

note on total co-independent domination in trees

Abel Cabrera Martínez, José M. Sigarreta, Frank A. Hernández Mira, Ismael G. Yero
article en
4 citations

Abstract

A set $D$ of vertices of a graph $G$ is a total dominating set if every vertex of $G$ is adjacent to at least one vertex in $D$. The total dominating set $D$ is called a total co-independent dominating set if $V(G)\setminus D$ is an independent set and has at least one vertex. The minimum cardinality of any total co-independent dominating set is denoted by $\gamma_{t,coi}(G)$. In this paper, we show that, for any tree $T$ of order $n$ and diameter at least three, $n-\beta(T)\leq \gamma_{t,coi}(T)\leq n-|L(T)|$ where $\beta(T)$ is the maximum cardinality of any independent set and $L(T)$ is the set of leaves of $T$. We also characterize the families of trees attaining the extremal bounds above and show that the differences between the value of $\gamma_{t,coi}(T)$ and these bounds can be arbitrarily large for some classes of trees.

Contributions to Discrete MathematicsVol. 19(3)
Universidad de Cádiz (ES), Universitat Rovira i Virgili (ES)
Junta de Andalucía
Openalex Percentile: Top 23%
Advanced Graph Theory Research
1.08
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.