Search

An intriguing concept in convexity theory is the characterization of sets having property Pm,n. A set is said to satisfy property Pm,n if for any collection of m arbitrary points at least n of the (m, 2) line segments determined by the points is contained in the given set. Valentine did the initial work with property P3,1, showing that a set with this property could be expressed as the union of 3 or fewer convex sets. This work was extended by Kay and Guay, who worked with the more general property Pm,n _ Convex: sets and graph theory were linked by Guay, and I have sought to continue this work by combining property P m,n and graph theory. A graph G is said to have property P m,n if given any m arbitrary points in G, there are at least n edges joining these points, n < m. The aim of this paper is to present some results which were obtained while seeking to characterize graphs having property P m,n The maximum diameter of a graph having property P m,n, and the minimum number of edges necessary for property P3,1 have been found. In any graph G, property P m,n can be extended to property P m+1, n+1. Finally, a graph can be generated having no star-complete points. There seem to be several other methods for characterizing graphs having property Pm,n, but I did not have time to study them.