Graphoidal covers and graphoidal covering number of a graph
type: Item
instance of: scholarly article
title: Graphoidal covers and graphoidal covering number of a graph
zbMATH Open document ID: 0623.05042
author: E. Sampathkumar
author: B. D. Acharya
published in: Indian Journal of Pure \& Applied Mathematics
publication date: 1987-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 4010564
zbMATH Keywords: graphoid
zbMATH Keywords: paths
zbMATH Keywords: graphoidal covering number
zbMATH Keywords: bounds
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 4010564