Extremal $k$-forcing sets in oriented graphs
Abstrak
This article studies the \emph{$k$-forcing number} for oriented graphs, generalizing both the \emph{zero forcing number} for directed graphs and the $k$-forcing number for simple graphs. In particular, given a simple graph $G$, we introduce the maximum (minimum) oriented $k$-forcing number, denoted $\MOF_k(G)$ ($\mof_k(G)$), which is the largest (smallest) $k$-forcing number among all possible orientations of $G$. These new ideas are compared to known graph invariants and it is shown that, among other things, $\mof(G)$ equals the path covering number of $G$ while $\MOF_k(G)$ is greater than or equal to the independence number of $G$ -- with equality holding if $G$ is a tree or if $k$ is at least the maximum degree of $G$. Along the way, we also show that many recent results about $k$-forcing number can be modified for oriented graphs.
Topik & Kata Kunci
Penulis (3)
Yair Caro
Randy Davila
Ryan Pepper
Akses Cepat
- Tahun Terbit
- 2017
- Bahasa
- en
- Sumber Database
- arXiv
- Akses
- Open Access ✓