ON HEREDITARY PROPERTIES OF GRAPHS.
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 01, 1967
- Accession Number
- AD0649059
Entities
People
- Stephen T. Hedetniemi
Organizations
- University of Michigan