# 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