Graphoidal covers and graphoidal covering number of a graph (Q1091403)

Given a graph \(G=(V,E)\), a graphoid on G is defined here to be a collection \(\Psi\) of (not necessarily open) paths in G such that (a) every path in \(\Psi\) has at least two points, and (b) every point of G is an internal point of at most one path in \(\Psi\). If, further, (c) every line of G is in some path in \(\Psi\), then we call \(\Psi\) a graphoidal cover of G. The graphoidal covering number of G, denoted \(\gamma\) (G), is then defined to be the minimum cardinality of a graphoidal cover of G. The basic preoccupation of this paper is an attempt to find suitable bounds for \(\gamma\). In the sequel, we obtain a characterization of graphs G which admits a labeling f of the points of g by the numers 1,2,...,n, \(n=| V(G)|\), so that the set of maximal directed paths in the low-to-high orientation of G with respect to f is a graphoidal cover of G. We then discuss the problem of representing a graph as an intersection graph of a graphoidal cover of a graph. Several other key problems are also proposed or indicated.