Disimplicial arcs, transitive vertices, and disimplicial eliminations
Martiniano Roberto Eguía, Francisco Juan Soulignac
Abstract
In this article we deal with the problems of finding the disimplicial
arcs of a digraph and recognizing some interesting graph classes
defined by their existence. A diclique of a digraph is a pair
V →W of sets of vertices such that v
→w is an arc for every v ∈V and w
∈W. An arc v →w is disimplicial
when it belongs to a unique maximal diclique. We show that the
problem of finding the disimplicial arcs is equivalent, in terms of
time and space complexity, to that of locating the transitive
vertices. As a result, an efficient algorithm to find the
bisimplicial edges of bipartite graphs is obtained. Then, we develop
simple algorithms to build disimplicial elimination schemes, which can
be used to generate bisimplicial elimination schemes for bipartite
graphs. Finally, we study two classes related to perfect disimplicial
elimination digraphs, namely weakly diclique irreducible digraphs and
diclique irreducible digraphs. The former class is associated to
finite posets, while the latter corresponds to dedekind complete
finite posets.
Full Text: PDF