Graphs with the Erdős–Ko–Rado property Original Research Article

For a graph image vertex image of image and integer image, we denote the family of independent r-sets of image by image and the subfamily image by image; such a subfamily is called a star. Then, image is said to be r-EKR if no intersecting subfamily of image is larger than the largest star in image. If every intersecting subfamily of image of maximum size is a star, then image is said to be strictly r-EKR. We show that if a graph image is image-EKR then its lexicographic product with any complete graph is r-EKR. For any graph image, we define image to be the minimum size of a maximal independent vertex set. We conjecture that, if image, then image is r-EKR, and if image, then image is strictly r-EKR. This is known to be true when image is an empty graph, a cycle, a path or the disjoint union of complete graphs. We show that it is also true when image is the disjoint union of a pair of complete multipartite graphs.