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) : Hedetniemi,Stephen T.

Report Date : FEB 1967

Pagination or Media Count : 14

Abstract : The point independence number of a graph G, beta sub 0(G), 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 0(G), 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 0(P) and beta sub 0(P), such that for any graph G having p points, alpha sub 0(P) + beta sub 0(P) = p. We also obtain a theorem which specifies a similar class of properties Q of a graph G and corresponding parameters alpha sub 1(Q) and beta sub 1(Q) such that for any graph G having q lines, alpha sub 0(Q) + beta sub 1(Q) = q. (Author)

Descriptors :   (*GRAPHICS, SET THEORY), AUTOMATION, THEOREMS, THEORY

Subject Categories : Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE