Helly type theorem and graphs (Q2707489)

For each vertex \(x\) in a graph \(G\) let \(\Gamma (x)\) be the set of neighbours of \(x\). The authors study the neighbourhood hypergraph \(H_{G}\) of \(G\), which is formed by the sets \(\{x\}\cup \Gamma (x)\). They give a (rather complicated) characterization of the graphs \(G\) such that \(H_{G}\) has the Helly property. (A set system is said to have the Helly property if any subfamily intersecting two by two has a nonempty intersection.) For this characterization the following concept of ``intersecting set'' is used: a set \(X\) of vertices of \(G\) is called intersecting if any pair of vertices from \(X\) is adjacent or has a common neighbour. NEWLINENEWLINENEWLINEFor the case of bipartite graphs, the following simpler characterization is found: \(H_{G}\) has the Helly property if and only if for any intersecting set \(X\) the subgraph of \(G\) induced by the vertices of \(X\) and their neighbours is a tree.NEWLINENEWLINEFor the entire collection see [Zbl 0948.00038].