Characterization of a class of triangle‐free graphs with a certain adjacency property

Let m and n be nonnegative integers. Denote by P ( m,n ) the set of all triangle‐free graphs G such that for any independent m ‐subset M and any n ‐subset N of V ( G ) with M ∩ N = Ø, there exists a unique vertex of G that is adjacent to each vertex in M and nonadjacent to any vertex in N . We prove that if m ⩾ 2 and n ⩾ 1, then P ( m,n ) = Ø whenever m ⩽ n , and P ( m,n ) = { K m,n + 1 } whenever m > n . We also have P (1,1) = { C 5 } and P (1, n ) = Ø for n ⩾ 2. In the degenerate cases, the class P (0, n ) is completely determined, whereas the class P ( m ,0), which is most interesting, being rich in graphs, is partially determined.