On neighborhood-Helly graphs

Abstract

A family F of subsets of some set is intersecting when sets of F pairwise intersect. The family F is Helly when every intersecting subfamily of it contains a common element. In this paper we examine the families of vertex neighborhoods of a graph, with the aim of determining whether or not they are Helly, and also whether or nor they are hereditary Helly, that is, each of the induced subgraphs of the graph is Helly. We examine the cases where the neighborhoods are all open, or all closed, or mixed, that is, some open and some closed. For mixed neighborhoods there are two different kinds of choice of the neighborhood of each vertex to be considered: fixed or arbitrary choice. By fixed mixed neighborhood, we mean that the choice, open or closed, for the neighborhood of a vertex is known in advance, that is part of the input. On the other hand, an arbitrary choice implies that the choice can be made along the process. For the cases of open, closed and fixed mixed neighborhoods, we describe characterizations, both for the neighborhoods to be Helly and hereditary Helly. The characterizations are of two types: based on the concept of extensions, or, for the hereditary cases, by forbidden induced subgraphs. Polynomial time recognition algorithms follow directly from the characterizations. In contrast, for arbitrary mixed neighborhoods, we prove that it is NP-complete to decide whether the family of neighborhoods is Helly or hereditary Helly.