Browsing by Author "Henning, Michael A."

Now showing 1 - 4 of 4

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 ,
Nordhaus-Gaddum bounds for upper total domination
(Wydawnictwa AGH, 2022) Haynes, Teresa W.; Henning, Michael A.
A set $S$ of vertices in an isolate-free graph $G$ is a total dominating set if every vertex in $G$ is adjacent to a vertex in $S$. A total dominating set of $G$ is minimal if it contains no total dominating set of $G$ as a proper subset. The upper total domination number $\Gamma_{t}(G)$ of $G$ is the maximum cardinality of a minimal total dominating set in $G$. We establish Nordhaus-Gaddum bounds involving the upper total domination numbers of a graph G and its complement $\overline{G}$. We prove that if $G$ is a graph of order n such that both $G$ and $\overline{G}$ are isolate-free, then $\Gamma_t(G) + \Gamma_t(\overline{G}) \leq n + 2$ and $\Gamma_t(G)\Gamma_t(\overline{G}) \leq \frac{1}{4}(n+2)^2$, and these bounds are tight.
Access status: Open Access ,
Spreading in claw-free cubic graphs
(Wydawnictwa AGH, 2025) Brešar, Boštjan; Hedžet, Jaka; Henning, Michael A.
Let $p \in \mathbb{N}$ and $q \in \mathbb{N} \cup \lbrace \infty \rbrace$. We study a dynamic coloring of the vertices of a graph $G$ that starts with an initial subset $S$ of blue vertices, with all remaining vertices colored white. If a white vertex $v$ has at least $p$ blue neighbors and at least one of these blue neighbors of $v$ has at most $q$ white neighbors, then by the spreading color change rule the vertex $v$ is recolored blue. The initial set $S$ of blue vertices is a $(p,q)$-spreading set for $G$ if by repeatedly applying the spreading color change rule all the vertices of $G$ are eventually colored blue. The $(p,q)$-spreading set is a generalization of the well-studied concepts of $k$-forcing and $r$-percolating sets in graphs. For $q \geq 2$, a $(1,q)$-spreading set is exactly a $q$-forcing set, and the $(1,1)$-spreading set is a $1$-forcing set (also called a zero forcing set), while for $q = \infty$, a $(p,\infty)$-spreading set is exactly a $p$-percolating set. The $(p,q)$-spreading number, $\sigma_{(p,q)}(G)$, of $G$ is the minimum cardinality of a $(p,q)$-spreading set. In this paper, we study $(p,q)$-spreading in claw-free cubic graphs. While the zero-forcing number of claw-free cubic graphs was studied earlier, for each pair of values $p$ and $q$ that are not both $1$ we either determine the $(p,q)$-spreading number of a claw-free cubic graph $G$ or show that $\sigma_{(p,q)}(G)$ attains one of two possible values.
Access status: Open Access ,
Total connected domination game
(Wydawnictwa AGH, 2021) Bujtás, Csilla; Henning, Michael A.; Iršič, Vesna; Klavžar, Sandi
The (total) connected domination game on a graph $G$ is played by two players, Dominator and Staller, according to the standard (total) domination game with the additional requirement that at each stage of the game the selected vertices induce a connected subgraph of $G$. If Dominator starts the game and both players play optimally, then the number of vertices selected during the game is the (total) connected game domination number ($\gamma_{\rm tcg}(G)$) $\gamma_{\rm cg}(G)$ of $G$. We show that $\gamma_{\rm tcg}(G) \in \{\gamma_{\rm cg}(G),\gamma_{\rm cg}(G) + 1,\gamma_{\rm cg}(G) + 2\}$, and consequently define $G$ as Class $i$ if $\gamma_{\rm tcg}(G) = \gamma_{\rm cg} + i$ for $i \in \{0,1,2\}$. A large family of Class $0$ graphs is constructed which contains all connected Cartesian product graphs and connected direct product graphs with minumum degree at least $2$. We show that no tree is Class $2$ and characterize Class $1$ trees. We provide an infinite family of Class $2$ bipartite graphs.