On Relations between Neighborhoods of Threshold and Ferrers Digraphs

Abstract

Ferrers digraphs have linearly nested in- and out-neighborhoods that define two rankings on the vertices. Removing the loops turns Ferrers into threshold digraphs in which the neighborhoods are no longer nested in general. We show that the two vertex rankings of a Ferrers digraph must preserve two strict vertex preorders of its underlying threshold digraph, which are equivalent to vertex relations similar to neighborhood inclusion. The vertex relations obtained in this way offer the possibility to complete the classification of threshold digraphs based on neighborhood-inclusion criteria. In line with existing criteria, we introduce medial and hierarchical Ferrers digraphs, whose rankings are identical (up to reversal). We characterize threshold digraphs where either all or none of the corresponding Ferrers digraphs of a single threshold digraph are medial or hierarchical. These characterizations are found to be consistent with previous work on uniquely ranked threshold digraphs. Our results therefore affirm the validity of the neighborhood-inclusion criteria defined for simple digraphs.