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