Arc-bases and Point-bases: when are they different for finite digraphs?

56 Views Asked by At

Definitions

Given a digraph $D=(X,U)$, a point-basis of a digraph $D$ is a minimal vertex set from which a dipath exist to every vertex in $D$. An arc-basis is a minimal arc-reaching set. A subset $S\subseteq X$ is an arc-reaching set of $D$ if for eevery arc $(x,y)$ there exists a diwalk $W$ originating at a vertex $U\in S$ and containing $(x,y)$. The bases do not necessarily exist for infinite digraphs.

Source is the publication here and the definitions in its abstract.

I am interested in finite digraphs and I cannot yet understand the motivation for arc-bases, whence the question.

My intuition of an arc-reaching set is a vertex set from which a dipath exists to every vertex. By doing so it visits every arc, so is an arc-basis a point-basis?

Breaking this down now into the question and its relevant parts.

When are the arc-bases and point-bases different for finite digraphs?

  1. Is every arc-basis a point-basis?

  2. What is the motivation to define two kinds of bases for digraphs?

  3. Which bases are relevant for finite digraphs?