Graphoidal covers and graphoidal covering number of a graph (Q1091403): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 01:21, 31 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Graphoidal covers and graphoidal covering number of a graph |
scientific article |
Statements
Graphoidal covers and graphoidal covering number of a graph (English)
0 references
1987
0 references
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.
0 references
graphoid
0 references
paths
0 references
graphoidal covering number
0 references
bounds
0 references