Maximum Oriented Forcing Number for Complete Graphs

Abstract

The \emph{maximum oriented $k$-forcing number} of a simple graph $G$, written $\MOF_k(G)$, is the maximum \emph{directed $k$-forcing number} among all orientations of $G$. This invariant was recently introduced by Caro, Davila and Pepper in~\cite{CaroDavilaPepper}, and in the current paper we study the special case where $G$ is the complete graph with order $n$, denoted $K_n$. While $\MOF_k(G)$ is an invariant for the underlying simple graph $G$, $\MOF_k(K_n)$ can also be interpreted as an interesting property for tournaments. Our main results further focus on the case when $k=1$. These include a lower bound on $\MOF(K_n)$ of roughly $\frac{3}{4}n$, and for $n\ge 2$, a lower bound of $n - \frac{2n}{\log_2(n)}$. We also consider various lower bounds on the maximum oriented $k$-forcing number for the closely related complete $q$-partite graphs.

Keywords

• tournaments
• maximum oriented forcing
• zero forcing
• k-forcing