arXiv Open Access 2023

Orientable total domination in graphs

Sarah E. Anderson Tanja Dravec Daniel Johnston Kirsti Kuenzel
Lihat Sumber

Abstrak

Given a directed graph $D$, a set $S \subseteq V(D)$ is a total dominating set of $D$ if each vertex in $D$ has an in-neighbor in $S$. The total domination number of $D$, denoted $γ_t(D)$, is the minimum cardinality among all total dominating sets of $D$. Given an undirected graph $G$, we study the maximum and minimum total domination numbers among all orientations of $G$. That is, we study the upper (or lower) orientable domination number of $G$, $\rm{DOM}_t(G)$ (or $\rm{dom}_t(G)$), which is the largest (or smallest) total domination number over all orientations of $G$. We characterize those graphs with $\rm{DOM}_t(G) =\rm{dom}_t(G)$ when the girth is at least $7$ as well as those graphs with $\rm{dom}_t(G) = |V(G)|-1$. We also consider how these parameters are effected by removing a vertex from $G$, give exact values of $\rm{DOM}_t(K_{m,n})$ and $\rm{dom}_t(K_{m,n})$ and bound these parameters when $G$ is a grid graph.

Topik & Kata Kunci

Penulis (4)

S

Sarah E. Anderson

T

Tanja Dravec

D

Daniel Johnston

K

Kirsti Kuenzel

Format Sitasi

Anderson, S.E., Dravec, T., Johnston, D., Kuenzel, K. (2023). Orientable total domination in graphs. https://arxiv.org/abs/2311.16307

Akses Cepat

Lihat di Sumber
Informasi Jurnal
Tahun Terbit
2023
Bahasa
en
Sumber Database
arXiv
Akses
Open Access ✓