Accession Number:
AD0649059
Title:
ON HEREDITARY PROPERTIES OF GRAPHS.
Descriptive Note:
Technical rept.,
Corporate Author:
MICHIGAN UNIV ANN ARBOR LOGIC OF COMPUTERS GROUP
Personal Author(s):
Report Date:
1967-02-01
Pagination or Media Count:
14.0
Abstract:
The point independence number of a graph G, beta sub 0G, is the maximum number of points in a set S such that no two points in S are adjacent in G. The point covering number, alpha sub 0G, is the minimum number of points in a set S such that every line of G contains a point of S. In 1959, Gallai proved the following very simple result. Theorem 1. For any graph G having p points, point covering number alpha sub 0 and point independence number beta sub 0, alpha sub 0 beta sub 0 p. This paper obtains several generalizations of this theorem which specify broad classes of properties p of a graph G corresponding to which there exist parameters alpha sub 0P and beta sub 0P, such that for any graph G having p points, alpha sub 0P beta sub 0P p. We also obtain a theorem which specifies a similar class of properties Q of a graph G and corresponding parameters alpha sub 1Q and beta sub 1Q such that for any graph G having q lines, alpha sub 0Q beta sub 1Q q. Author
Descriptors:
Subject Categories:
- Theoretical Mathematics