Browsing by Subject "vertex partitions"

Now showing 1 - 2 of 2

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.