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

✍ Scribed by Brian Alspach; C. C. Chen; Katherine Heinrich

• Publisher: John Wiley and Sons
• Year: 1991
• Tongue: English
• Weight: 597 KB
• Volume: 15
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.3190150404

✦ Synopsis

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) = {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.