Browsing by Subject "total domination"

Now showing 1 - 5 of 5

Access status: Open Access ,
An upper bound on the total outer-independent domination number of a tree
(2012) Krzywkowski, Marcin
A total outer-independent dominating set of a graph $G=(V (G), E(G))$ is a set $D$ of vertices of $G$ such that every vertex of $G$ has a neighbor in $D$, and the set $V(G) \setminus D$ is independent. The total outer-independent domination number of a graph $G$, denoted by $\gamma_t^{oi}(G)$, is the minimum cardinality of a total outer-independent dominating set of $G$. We prove that for every tree $T$ of order $n \geq 4$, with $l$ leaves and s support vertices we have $\gamma_t^{oi}(T) \leq (2n + s - l)/3$, and we characterize the trees attaining this upper bound.
Access status: Open Access ,
Augmenting graphs to partition their vertices into a total dominating set and an independent dominating set
(Wydawnictwa AGH, 2025) Haynes, Teresa W.| Henning, Michael A.
A graph $G$ whose vertex set can be partitioned into a total dominating set and an independent dominating set is called a TI-graph. There exist infinite families of graphs that are not TI-graphs. We define the TI-augmentation number $\operatorname{ti}(G)$ of a graph $G$ to be the minimum number of edges that must be added to $G$ to ensure that the resulting graph is a TI-graph. We show that every tree $T$ of order $n \geq 5$ satisfies $\operatorname{ti}(T) \leq \frac{1}{5}n$. We prove that if $G$ is a bipartite graph of order $n$ with minimum degree $\delta(G) \geq 3$, then $\operatorname{ti}(G) \leq \frac{1}{4}n$, and if $G$ is a cubic graph of order $n$, then $\operatorname{ti}(G) \leq \frac{1}{3}n$. We conjecture that $\operatorname{ti}(G) \leq \frac{1}{6}n$ for all graphs $G$ of order $n$ with $\delta(G) \geq 3$, and show that there exist connected graphs $G$ of sufficiently large order $n$ with $\delta(G) \geq 3$ such that $\operatorname{ti}(T) \geq (\frac{1}{6} - \varepsilon) n$ for any given $\varepsilon \gt 0$.
Access status: Open Access ,
Graphs whose vertex set can be partitioned into a total dominating set and an independent dominating set
(Wydawnictwa AGH, 2024) Haynes, Teresa W.; Henning, Michael A.
A graph $G$ whose vertex set can be partitioned into a total dominating set and an independent dominating set is called a TI-graph. We give constructions that yield infinite families of graphs that are TI-graphs, as well as constructions that yield infinite families of graphs that are not TI-graphs. We study regular graphs that are TI-graphs. Among other results, we prove that all toroidal graphs are TI-graphs.
Access status: Open Access ,
Neighbourhood total domination in graphs
(2011) Arumugam, S.; Sivagnanam, C.
Let $G = (V,E)$ be a graph without isolated vertices. A dominating set $S$ of $G$ is called a neighbourhood total dominating set (ntd-set) if the induced subgraph $N(S)$ has no isolated vertices. The minimum cardinality of a ntd-set of $G$ is called the neighbourhood total domination number of $G$ and is denoted by $\gamma _{nt}(G)$. The maximum order of a partition of $V$ into ntd-sets is called the neighbourhood total domatic number of $G$ and is denoted by $d_{nt}(G)$. In this paper we initiate a study of these parameters.
Access status: Open Access ,
The complexity of open k-monopolies in graphs for negative k
(Wydawnictwa AGH, 2019) Peterin, Iztok
Let $G$ be a graph with vertex set $V(G)$, $\delta(G)$ minimum degree of $G$ and $k\in\left\{1-\left\lceil\frac{\delta(G)}{2}\right\rceil,\ldots ,\left\lfloor \frac{\delta(G)}{2}\right\rfloor\right\}$. Given a nonempty set $M\subseteq V(G)$) a vertex $v$ of $G$ is said to be $k$-controlled by $M$ if $\delta_{M}(v) \geq \frac{\delta_{V(G)}(v)}{2}+k$ where $\delta_{M}(v)$ represents the number of neighbors of $v$ in $M$. The set $M$ is alled an open $k$-monopoly for $G$ if it $k$-controls every vertex $v$ of $G$. In this short note we prove that the problem of computing the minimum cardinality of an open k-monopoly in a graph for a negative integer $k$ is NP-complete even restricted to chordal graphs.