2023/11/27 by Anderson, Sarah E., Dravec, Tanja, Johnston, Daniel +1
#05C20 #05C69 #05C76 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2311.16307
Given a directed graph D, a set S ⊆ 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, \rmDOMt(G) (or \rmdomt(G)), which is the largest (or smallest) total domination number over all orientations of G. We characterize those graphs with \rmDOMt(G) =\rmdomt(G) when the girth is at least 7 as well as those graphs with \rmdomt(G) = |V(G)|-1. We also consider how these parameters are effected by removing a vertex from G, give exact values of \rmDOMt(Km,n) and \rmdomt(Km,n) and bound these parameters when G is a grid graph.