Premium
Characterization of a class of triangle‐free graphs with a certain adjacency property
Author(s) -
Alspach Brian,
Chen C. C.,
Heinrich Katherine
Publication year - 1991
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190150404
Subject(s) - combinatorics , mathematics , vertex (graph theory) , adjacency list , class (philosophy) , graph , discrete mathematics , artificial intelligence , computer science
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.