Characterization of a class of triangle‐free graphs with a certain adjacency property
Brian Alspach, C. C. Chen, Katherine Heinrich · Journal of Graph Theory · 1991
Abstract 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) = {Km,n+1} whenever m > n. We also have P(1,1) = {C5} 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.