The Graphs Determined By an Adjacency Property

Abstract

We determine all graphs $G$ of order at least $k+1$, $k\ge 3$, with the property that for any $k$-subset $S$ of $V(G)$ there is a unique vertex $x,x\in V(G)–S$, which has exactly two neighbours in $S$. Such graphs have exactly $k+1$ vertices and consist of a family of vertex-disjoint cycles. When $k=2$ it is clear that graphs with this property are the so-called friendship graphs.