On Kernels, β-graphs, and β-graph Sequences of Digraphs

Abstract

We begin by investigating some conditions determining the existence of kernels in various classes of directed graphs, most notably in oriented trees, grid graphs, and oriented cycles. The question of uniqueness of these kernels is also handled. Attention is then shifted to $\gamma$-graphs, structures associated to the minimum dominating sets of undirected graphs. I define the $\beta$-graph of a given digraph analogously, involving the minimum absorbant sets. Finally, attention is given to iterative construction of $\beta$-graphs, with an attempt to characterize for what classes of digraphs these $\beta$-sequences terminate.