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

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE